Constraint-based local search makes it possible to build local search algorithms compositionally, to separate modeling from search, to promote reuse across many applications, and to exploit problem structure to achieve high performance. As a result, Comet may dramatically simplify the design and implementation of (stochastic) local search algorithms, while preserving the efficiency of low-level, problem-specific, implementations.

 

The computational model underlying constraint-based local search uses constraints and objectives to drive the search procedure toward feasible or high-quality solutions. Constraints incrementally maintain their violations, and objectives their values. Moreover, constraints and objectives are differentiable and can be queried to evaluate the effect of moves on their violations and values.

 

Some of the main scientific contributions of CBLS and Comet are invariants, differentiable objects, search controllers, advanced control structures such as events and neighbors, and the underlying computational model.