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 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.