
Linearization of Global Constraints
 Meinolf Sellmann, Brown University
abstract

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 pairwise 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 contextfree grammar constraints and
binary constraint problems with bounded treewidth.

