Linearization of Global Constraints
- Meinolf Sellmann, Brown University
||Global constraints in CP are important modeling tools as they capture
entire substructures of combinatorial problems. A famous example for
global constraints is the AllDifferent constraint which requires that a
set of integer variables that must take pair-wise different values. The
advantage of global constraints, from a modeling perspective, is that
the user must not formulate a problem as a set of linear inequalities
anymore. Especially for inexperienced users, the latter often leads to
semantically correct but computationally difficult integer programs. We
can facilitate modeling in mathematical programming by providing
algorithms which automatically reformulate global constraints. In this
talk I will show how to linearize context-free grammar constraints and
binary constraint problems with bounded tree-width.
Last updated: November 7, 2009.