General Principles of Constraint Programming

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.

Speaker Details

Jean©Charles R¨¦gin received in 1995 a Ph.D. in Computer Science from the University of Montpellier II (France) and a `Habilitation ¨¤ Diriger des Recherches` in 2004 at the University of Nice©Sophia Antipolis. He joined ILOG in 1995 as a developer of the ILOG Solver product, was promoted to Ilog Solver manager two years later, becoming the
Director of Constraint Programming at Ilog in 2001. He left the company in October 2008 and he is now Professor at
the University of Nice©Sophia Antipolis.

R¨¦gin is a pioneer of the research on global constraints, currently one of the most active fields of Constraint
Programming (CP). Most notably, he has proposed the famous filtering algorithm of the alldiff constraint in one of
the most cited papers in CP (with more than 550 references on Google Scholar) also widely known in the Artificial
Intelligence and Operations Research communities. He is the author of several global constraints, and has also
contributed to the improvement of the classical arc©consistency algorithm and the study of over©constrained
problems for which he introduced the concept of soft global constraints. He has designed new CP methods for
solving complex combinatorial applications such as sports scheduling, car sequencing, network design and
maximum©ļique problems. He has published more than 50 papers while working at the industry.
R¨¦gin has taught at the most prestigious French engineering schools (Ecole Polytechnique and Ecole Centrale in
Paris). In 2005 he spent a sabbatical year at Cornell University. He was the Chair of the CPAIOR conference in 2004,
and is the co©editor , with Pascal Van Hentenryck, of the Constraint Programming Letters.

Date:
Speakers:
Jean-Charles Regin
Affiliation:
University of Nice-Sophia Antipolis

    • Portrait of Jeff Running

      Jeff Running