Combining local and global search in a constraint programming environment

This paper presents several case studies which illustrate how constraint programming can benefit from the combination of global and local search techniques, offering a flexible and efficient platform for the design of combinatorial optimisation applications. For job-shop scheduling, we relate experi...

Full description

Saved in:
Bibliographic Details
Published in:Knowledge engineering review 2001-03, Vol.16 (1), p.41-68
Main Authors: CASEAU, YVES, LABURTHE, FRANÇOIS, LE PAPE, CLAUDE, ROTTEMBOURG, BENOÎT
Format: Article
Language:English
Subjects:
Algorithms
Alliances
Case studies
Decision making
Heuristic
Job shops
Linear programming
Neighborhoods
Propagation
Scheduling
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents several case studies which illustrate how constraint programming can benefit from the combination of global and local search techniques, offering a flexible and efficient platform for the design of combinatorial optimisation applications. For job-shop scheduling, we relate experiments with local search procedures that use global search to intensively explore a given neighbourhood, in the spirit of “shuffle” methods. For preemptive job-shop scheduling, two basic search strategies, Depth-First Search and Limited Discrepancy Search, are compared. For Vehicle Routing we report an Incremental Local Optimisation heuristic, combined with Limited Discrepancy Search. Finally, we show how ad hoc algebras can considerably enhance the design of heuristics based on local and global search within a constraint-programming environment. Experiments on vehicle routing will enlighten how such a language for “search and insert” control can enable automated tuning and discovery of new strategies adapted to the instances typology of the problem at stake.
ISSN:0269-8889
1469-8005
DOI:10.1017/S0269888901000078