Synthesizing Search in Comet
Comet implements the vision
Combinatorial Optimization = Model + Search
stating that the combinatorial optimization must be expressed in terms of a model and a search component. The models are expressed in a rich language featuring global/combinatorial constraints, logical and cardinality operators, and table constraints to name a few. The search component helps guide the solver towards feasible or high-quality solutions.
The design of search components typically requires expertise precise knowledge of the underlying constraint solvers and the application domains. To remedy this limitation, the Comet system provides some search synthesizers which derive advanced search components from the model and the instance data.
Such search synthesis is possible because Comet models are high-level and convey the structure of the applications. As a result, the synthesizer can exploit the structure to derive search components tailored to the application at hand and the instance data.
The Comet system includes search synthesizers for constraint-based local search, in particular for tabu-search and variable-neighborhood search. The synthesizer also relies on constraint annotations (that is, whether a constraint is hard or soft) to help in the neighborhood selection. The experimental results on a variety of models have shown that the resulting search procedures compare well with tailored search components. The challenge now is to push this technology to increasingly complex models and to constraint programming.
