Jean-Charles Régin, Ph.D.
Director Constraint Programming
ILOG Sophia Antipolis, France
Photos: CP class; Dinner with class; After dinner; CSE Colloquium; Pioneers Park .

Biographical information:

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.

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 400 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. He has designed new CP methods for solving complex combinatorial applications such as sports scheduling, car sequencing, network design and maximum-clique 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.

A CSE Colloquium Distinguished Speaker

Tuesday, April 22, 2008.

Refreshments 3:30 p.m.
348 Avery Hall

Talk: 4:00--5:00 p.m.
115 Avery Hall

Constraint Programming (CP) is a general and powerful approach for solving many combinatorial problems. This approach has been successfully used to solve a large range of real-life applications (e.g., rostering, time-tabling, car manufacturing, and scheduling), which can be inherently different in practice.

CP is on the borderline between Artificial Intelligence (AI) and Operations Research (OR). It inherits from AI the language aspects (that is, the easy way to define a problem), the flexibility (that is, the fact that problems can be easily modified), and the ability to exploit the knowledge of the application domain in order to improve the resolution of the problem. Operations Research brings to CP a wealth of useful and powerful algorithms, adding to the computational tools of CP needed for solving some real-world problems.

In this talk, I will introduce the general principles of CP. I will insist on its originality and on its flexibility, and will illustrate its strengths and its weaknesses. In particular, I will discuss how some OR algorithms are used and why the types of constraints that can be considered are not restricted. I will also compare CP to several other approaches, such as MIP, Greedy Algorithm, and Local Search, 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.

Monday, April 21, 2008

From 3:30 pm to 4:45 pm.
Informal discussion with speaker: 5:00 pm to 5:50 pm

Avery Hall 111.

In this talk, we present a network design problem. The resolution of this problem was the subject of a French project named Rococo, involving University of Versailles, France Telecom (the main French telecommunication company) and ILOG. We show the complexity of a real-world problem and present the different methods we used to solve it. Then, we discuss some reflections about the way real-world problems are usually solved.

Slides of talk (will be made available at some point)

Required reading for class:
Robust and Parallel Solving of a Network Design Problem ( PS, PDF).