Constraint Programming in Comet
Comet supports constraint programming over finite domains, a concept pioneered in the CHIP language at ECRC. CHIP was designed and implemented by Pascal Van Hentenryck in the mid-80s.
Constraint programming contributed two fundamental innovations. At the language level, it implemented the vision
Combinatorial Optimization = Model + Search
for the first time. 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 is typically a nondeterministic program, implemented using various search strategies such depth-first or discrepancy search.
Computationally, constraint programming over finite domains implements a novel problem-solving paradigm for optimization in which the focus is on feasibility. Constraints are used to reduce the search space by pruning from the variable domains values that cannot appear in any solution. Search procedures use feasibility-based heuristics for branching.
The implementation of constraint programming in Comet features some fundamental innovations. Comet separates the search implementation into a nondeterministic program which specify the search tree and a search controller which describes the exploration strategy, i.e.,
Search Procedures = Nondeterministic Program + Search Controller
Comet has also shown how to use search controllers to transparently parallelize constraint programs.
