Constraint-based Local Search

Pascal Van Hentenryck
Brown university
Friday, 23 April, 2004 (All day)
Louvain-la-Neuve University (UCL)

We present an overview of Comet, an object-oriented language specifically designed to simplify the implementation of local search algorithms in combinatorial optimization. The main novelty in Comet is its constraint-based architecture organized around two main components: a declarative component which models the application in terms of differentiable objects such as constraints, and a search component which describes the heuristic and meta-heuristic in terms of high-level control abstractions such as events. The architecture enables local search algorithms to be extremely high-level, compositional, and modular, often decreasing development time by orders of magnitude. We report experimental results on a variety of applications in scheduling and logistics, where Comet was instrumental in closing open problems and discovering novel, more effective, algorithms. (Joint work with Laurent Michel)