Nice, France, April 19, 2004
In conjunction with CP-AI-OR'04

Graph Theory is an extremely wide research area involving Mathematics and Operations Research. Graph Theory concerns both algorithms for problems arising on graphs and applications whose underlying structure can be represented thorough a graph. Results coming from graph theory have been always successfully applied to Mathematical Programming and, more recently, they become crucial also in the Constraint Programming (CP) area. For instance, many Graph Theory algorithms have been used as filtering algorithms in global constraints and many applications based on the graph representation have been solved through CP.

The Master Class is mainly intended for PhD students, researchers and practitioners and it is aimed at presenting the state-of-the-art of the integration between Graph Theory and Constraint Programming.

In particular, the class will give an overview of Graph Theory classical and recent results which have been applied in the Constraint Programming context as filtering algorithms and to discuss Graph Theory applications which has been solved using hybrid methods involving Constraint Programming. An introduction to Graph Theory algorithms will be given as a first step.

The Master Class day is organized as follows: after an introduction on Graph Theory, the rest of the morning will be devoted to Graph Theory results embedded into global constraints, while the afternoon will concern Graph Theory applications.

For attending the Master Class, a Constraint Programming background is required.

Soon after the Master Class, the CP-AI-OR conference will take place, a major forum on the Integration of OR and AI techniques in CP.


We are gratefull to the authors who gave us access to the material used for their talk. However, please, note that this material is the property of their authors and that any reuse of this material, or of any part of this material should be properly referenced.

Monday 19th

8h30-9h00: Registration

9h00-9h15: Welcome

9.15-10.45 Filtering Algorithms based on Graph Theory
Jean-Charles Regin, ILOG S.A., France

10h45-11h00: Coffee break

11h00-12h00 Assignment-based relaxation in CP
Andrea Lodi, Bologna University, Italy

12h00-12h45 Temporal Graphs in Scheduling (second part)
Philippe Laborie, ILOG S.A., France

12h45-14h15: Lunch

14h15-15h00 Temporal Graphs in Scheduling (second part)
Philippe Laborie, ILOG S.A., France

15h00-16h00 Human solvers are still better than CP solvers ? The case of the bandwidth problem
Alberto Caprara, Bologna University, Italy

16h00-16h15: Coffee break

16h15-17h45 Constraint Applications using Graph Theory Results (bibliography)
Helmut Simonis, Parc Technologies Ltd., UK


Andrea Lodi
DEIS - University of Bologna
V.le Risorgimento 2
40136 Bologna

Michela Milano
DEIS - University of Bologna
V.le Risorgimento 2
40136 Bologna

Local Organization

Claude Michel
University of Nice-Sophia Antipolis