Tech Report CS-04-07
Constraint-Based Combinators for Local Search
Pascal Van Hentenryck, Laurent Michel, Liyuan Liu
April 2004
Abstract:
One of the most appealing features of constraint programming is its rich constraint language for expressing combinatorial optimization problems. This paper demonstrates that traditional combinators from constraint programming have natural counterparts for local search, although their underlying computational model is radically different. In particular, the paper shows that constraint combinators, such as logical and cardinality operators, reification, and first-class expressions can all be viewed as differentiable objects. These combinators naturally support elegant and efficient modelings, generic search procedures, and partial constraint satisfaction techniques for local search. Experimental results on a variety of applications demonstrate the expressiveness and the practicability of the combinators.(complete text in pdf or gzipped postscript)
| Page Owner: John Bazik | Last Modified: Fri Feb 9 17:44:31 2007 |