To increase the interaction among researchers, there will be no parallel sessions at the workshop. The plenary stream will consist of:
Four tutorial sessions (1h):
Pascal Van Hentenryck (Brown Univ, USA)
Constraint-Based Local Search
Constraint-based local search is a marriage between constraint programming and local search. It borrows from constraint programming rich declarative language for stating high-level and compositional models and an expressive languague for controling search. It inherents from local search an effective computational model for finding high-quality solution to large and complex combinatorial optimization problems. This tutorial describes the foundations of constraint-based local and its implementation in the Comet system, and it argues that this marriage is more than the sum of its parts. It also describes many applications of constraint-based local search in resource allocation and scheduling.
Michela Milano (Univ. Bologna, IT)
Mixing CP and IP for propagation and search
The talk will focus on two well known and widely used methods for solving combinatorial optimization problems: Constraint programming and Integer Programming. The two paradigms differ in some features and share others. They have been used separately and have only recently been merged obtaining promising results. The talk will outline some successful hybrid approaches that help propagation and search for solving combinatorial optimization problems.
Eric Bourreau (Univ. Montpellier, FR)
Global, Local and Meta Search : a framework based on keyword patterns
After picking in the literature a selected panel of solving strategies, we will formalize several levels in a structured search:
- Global search with both a strategic level and an exploration level,
- Local search with one or multiple schemes
- Meta Level strategy
We will derive some classic patterns from these different notions and suggest a more general framework based on keyword patterns.
It will be possible in the first place to express most of the existing strategies and in the second place to build (manually or automatically) new ones.Patrick Siarry (Univ. Paris 12, FR)
Some contributions to the adaptation of discrete metaheuristics for continuous optimization
In this tutorial, we firstly present the general frame of "difficult" continuous optimization : after a short description of a few typical applications, we point out the difficulties peculiar to continuous problems. Then we describe some pitfalls of adapting metaheuristics to continuous variable problems. In a second part, we present, as an illustration, the methods that we have proposed to adapt some metaheuristics : simulated annealing, tabu search, genetic algorithms and ant colony algorithms. We outline some perspectives or works in progress, particularly dealing with particle swarm optimization. Lastly, we show, as an example, an application in the field of biomedical engineering of a continuous ant colony algorithm : the registration of retinal angiograms.
Twelve technical sessions (1/2h):
Twelve of the submitted papers have been selected for presentation in a technical session. The objective of the technical sessions is to cover as broadly as possible the field of MLS+CP. Papers are selected on the basis of their outstanding quality and the fact that they discuss a topic not discussed in another technical session.
Overview Schedule:
Monday 28 November 2005
| 10:15 | Welcome desk |
| 10:45 | Opening session |
| 11:00 | Tutorial 1 (1h) [LS+CP] |
| Constraint-Based Local Search -
P. Van Hentenryck |
| 12:00 | Regular session 1 (2* 1/2 h) [Neighborhood search] |
| Cost-based Large Neighborhood Search (.pdf) -
T. Carchrae, J. C. Beck |
| A CSP model and LNS approach for the railway saturation problem (.pdf) -
F. Degoutin, H. Cambazard |
| 13:00 | Lunch |
| 14:30 | Tutorial 2 (1h) [IP+CP] |
| Mixing CP and IP for propagation and search -
M. Milano |
| 15:30 | Coffee break |
| 16:00 | Regular session 2 (3 * 1/2h) [Advanced Techniques] |
| The Branch & Move algorithm: Improving Global Constraints Support by Local Search (.pdf) -
T. Benoist |
| Consistent Neighbourhood in a Tabu Search (.pdf) -
A. Dupont, M. Vasquez and D. Habet |
| Using Constraint Programming and Local Search for Scheduling of Electricite de France Nuclear Power Plant Outages (.pdf) -
M.O.I. Khemmoudj, M. Porcheron, H. Bennaceur |
| Dynamic Distributed Double Guided Genetic Algorithm for Constrained Problems -
S. Bouamama, K. Ghedira |
| 18:00 | End for Monday |
Tuesday 29 November 2005
| 09:00 | Tutorial 3 (1h) [meta] |
| Some contributions to the adaptation of discrete metaheuristics for continuous optimization -
P. Siarry |
| 10:00 | Regular session 3 (2* 1/2h) [meta] |
| Metaheuristics for the integrated operational transportation planning problem: An Overview (.pdf) -
M. Krajewska, H. Kopfer |
| Combining a Unit propagation with Genetic Algorithms to Solve max-SAT Problems (.pdf) +
A scatter Search Variant to Solve max-SAT Problems (.pdf) -
D. Boughaci, H. Drias, B. Benhamou |
| 11:00 | Coffee break |
| 11:30 | Regular session 4 (3 * 1/2h) [ACO/EA] |
| ACO with Lookahead Procedures for Solving Set Partitioning and Covering Problems (.pdf) -
B. Crawford, C. Castro |
| Applying Evolutionary Search To Generate Robust Constraint Programming Search Strategies (.pdf) -
R. Dumeur, J.-F. Puget, P. Shaw |
| A methodology coupling evolutionary algorithm and constraint logic programming in project
management -
S. Rochet, C. Baron |
| 13:00 | Lunch |
| 14:30 | Tutorial 4 (1h) [applications] |
| Global, Local and Meta Search : a framework based on keyword patterns -
E. Bourreau |
| 15:30 | Regular session 5 (2 * 1/2h) [Scheduling; applications] |
| The RENAULT Car Sequencing Problem: a Constraint Programming benchmark revisited and
a new playground for metaheuristics and local search algorithms (.pdf) -
A. Nguyen |
| MLS+CP for the hybrid flowshop scheduling problem (.pdf) -
M. Sevaux, A. Jouglet, C. Oguz |
| 16:30 | Discussion and closing session |
| 17:00 | End for Tuesday |
