|Abstract:||Since the inception of constraints in AI for modeling and solving combinatorial problems in the 1960’s, constraint programming (CP) has emerged both as a scientific field as well as an array of successful techniques and tools for solving difficult real-life problems. Its applications are ubiquitous and include configuration, design, computational biology, diagnosis, logistics, planning, routing, and scheduling. The progress of CP is due to its multidisciplinary nature which includes fields such as AI, programming languages and systems, logics, operations research, and algorithmics.|
In this talk, I attempt to give you the basic setup of CP for solving real-life combinatorial optimization problems. I will take you on several gentle excursions that shed light on the what, why, and how of CP for real: capturing structure in combinatorial problems by constraints that ease modeling and aid solving and CP as an amazingly flexible and powerful toolbox of constraints as reusable software components. During that journey, I will relate CP to other techniques such as SAT, linear programming, and the original model of constraint satisfaction that emerged from AI and point out its strengths and weaknesses.