Both the Artificial Intelligence (AI) community and the
Operations Research (OR) community are interested in
developing techniques for solving hard combinatorial
problems. OR has built heavily on mathematical programming
formulations such as integer and linear programming, while AI
has developed constrained-based search and inference methods.
Recently, we have seen a convergence of ideas, drawing on the
individual strengths of these paradigms. Problem structure and
randomization are overarching themes in the study of these
approaches.
I'll discuss how the study of the structure of combinatorial
search problems and related phenomena is changing the way we
characterize the computational complexity of combinatorial
problems, beyond the worst-case complexity notion. Topics
covered will include constrainedness, phase transition
phenomena, and backbone structure.
In the second part I'll talk about randomized algorithms, the
best current methods for solving computationally hard
problems. In particular, I'll describe recent results on the
characterization of the probability distributions of complete
randomized search methods that have led to novel strategies to
dramatically boost combinatorial search methods, with
applications in planning and scheduling.
Copyright. All Rights Reserved.