Tech Report CS-01-02

Localizer++: An Open Library for local Search

Laurent Michel and Pascal Van Hentenryck

January 2001

Abstract:

Local search is one of the fundamental approaches to tackle large combinatorial optimization problems. Yet relatively little support is available to facilitate the design and implementation of local search algorithms. This paper introduces Localizer++, an extensible object-oriented library for local search. Localizer++ supports both declarative abstractions to describe the neighborhood and high-level search constructs to specify local moves and meta-heuristics. It also supports a variety of features typically found only in modeling languages and its extensibility allows for an easy integration of new, user-defined, abstractions. Of particular interest is the conciseness and readability of Localizer++ statements and the efficiency of the Localizer++ implementation.

(complete text in pdf or gzipped postscript)