Efficient Reformulations of Half-reified Global Constraints using Auxiliary Variables

Abstract

Background: In declarative constraint solving, a user formulates a constraint model in terms of variables and constraints, and uses a generic, off-the-shelf solver to solve the problem. Constraint Programming (CP) is one such constraint-solving paradigm, which has a wide support for many types of constraints, including global constraints. Global constraints capture complex relations between several decision variables, and CP solvers have specialized propagators to solve them efficiently.

Objectives: While CP solvers support a wide range of global constraints, few solvers support them in a reified or even halfreified context. Hence, for most CP solvers, reified global constraints must be decomposed into non-global constraints. This bypasses the global constraint propagator, which can considerably slow the solving process, suppressing one of the key benefits of modeling with global constraints: a faster solve-time. This is a problem for generic CP-modeling, as reified constraints are often introduced by the modeling system during translation and flattening of compound constraints. Additionally, half-reified global constraints are also used extensively in eXplainable Constraint Programming techniques (XCP). Therefore, XCP techniques suffer from scalability issues when global constraints occur in the model. In this paper, we aim to alleviate this bottleneck, allowing the use of the propagators of global constraints when modeling their half-reification, for all CP-solvers.

Methods: We propose a set of reformulation rules that allow the use of half-reification of a global constraint with any CP solver that supports the “normal” global constraint propagator. This is achieved by introducing auxiliary variables for the decision variables in the global constraint and the use of a reified channeling constraint, which most CP solvers support. Additionally, we show how to reduce the overhead of these auxiliary variables, by limiting the number of variables introduced, and by fixing their value when unconstrained. Finally, we prove the propagation strength of our reformulation for a variety of global constraint families.

Results: We experimentally evaluate the reformulations on a variety of global constraints and applications where reified constraints can occur. Our results show that this reformulation is much faster compared to decomposing the global constraint, and in some cases, even outperforms solver-level propagation routines for reified global constraints.

Conclusions: Using the reformulations proposed in this paper, we make the use of reified global constraints easily available for any CP solver. Hence, we expand the range of available solvers and constraint models that can be used in XCP techniques or for solving CSPs with compound constraints.