Constraint Programming Winter School
Topic outline
-
General
-
If you continue to work on the labs and you have questions, you can push your code in the lab so we can access it and contact us:
- Hadrien: hadrien.cambazard@grenoble-inp.fr
- Arnaud: arnaud.malapert@univ-cotedazur.fr
- Charles: charles.prudhomme@imt-atlantique.fr
-
Search in Focus: The Yang to Modeling's Yin in Constraint Programming (P. Schaus, UCLouvain)This lecture explain the pivotal role of search strategies in Constraint Programming (CP). We start by unpacking the 'first fail' principle, a fundamental strategy shaping numerous advanced techniques in CP. Our focus then shifts to expert-designed search strategies, particularly in complex areas like scheduling and vehicle routing, highlighting their practical applications. We'll discuss strategies to accelerate searches, including dominance and symmetry breaking, essential for streamlining the search process. The lecture progresses to advanced successfull black box search methods like conflict-based, activity-based, impact-based, and weighted degree approaches, all derivatives of the first fail principle. We then cover restart-based methods addressing the heavy-tail phenomenon in CP searches and Large Neighborhood Search (LNS) for quickly finding high-quality solutions. Finally, we touch on search parallelization, exploring how multiple processors can be utilized for more efficient problem-solving in CP.Search algorithms for combinatorial optimization: a guided tour (Luc Libralesso, AlmaSCOP)Search has been used for a long time and is present in multiple tools, including constraint programming, mixed integer programming, AI planning, branch-and-bounds of all sorts, and even shortest path algorithms.
While each tool has its own way of conceptualizing search, they also share many similar components. The goal of this lecture is to identify these similar components, and present how they can be combined with each other.
We will start with some simple examples (shortest path algorithms), then move on to some combinatorial optimization problems (a vehicle routing problem, a scheduling problem, and a 2D rectangle packing problem). For each of them, we will combine several search components and obtain state-of-the-art algorithms, showcasing how search can be used effectively.