General Principles of Constraint Programming

Опубликовано 7 сентября 2016, 17:56

Constraint programming (CP) is a general and powerful method to solve some combinatorial problems. This method has been successfully used to solve a large range of real-life applications (rostering, time-tabling, car manufacturing, scheduling etc...), which can be quite different. CP is on the borderline of AI and OR. CP inherits from IA the language aspect (that is the easy way to define a problem), the flexibility (that is the fact that problems can be easily modified) and the possibility to benefit from the knowledge of the application domain to improve the resolution of a problem. Operational Research brings to CP a lot of nice and powerful algorithms which gives to CP the computational aspect needed to solve some real world problems. In this talk we will introduce the general principles of this method. We will insist on its originality and on its flexibility. We will show its strength and its weakness. Notably, we will detail how some OR algorithms are used and why no restriction is made on the type of constraints that can be considered. We will also compare CP to several other approaches (like MIP, Greedy Algorithm, Local Search etc...) and explain how all these methods are often combined thanks to CP in order to solve real world applications. Some computational results will be given.