In constraint programming, a solver’s efficiency depends on its ability to "prune" the search space—identifying and removing values from variable domains that cannot possibly participate in a solution. While complex logical requirements are often modeled using global constraints (which capture high-level patterns like "all these variables must be unique"), solvers frequently break these down into simpler, primitive constraints to improve per-step speed or compatibility.
However, this process of decomposition introduces a significant "pruning gap." As Bessiere et al. establish, decomposing a computationally hard global constraint into simpler, polynomial-time sub-constraints necessarily results in a loss of deductive power. The solver gains speed in each iteration but loses the ability to see the "big picture," leading to an exponential explosion in the number of search steps required to find a solution.
The Loss of Holistic Reasoning
The primary reason decomposition fails is that it discards the global structural information of the problem. When a complex constraint is broken into independent units, the solver loses the ability to propagate logical implications across those boundaries. Sang et al. note that this lack of cross-component reasoning prevents solvers from identifying contradictions early, forcing them to explore unproductive search branches.
Consider the difference between a specialized global propagator and a set of binary constraints:
- Global Propagator: A single algorithm (like the one for multiset ordering introduced by Frisch et al.) looks at the entire set of variables simultaneously. It can detect that a partial assignment is impossible even if every individual pair of variables looks fine.
- Decomposition: The solver only sees local relationships. As Bessiere et al. argue in the context of ranking constraints, these local views fail to capture global structural requirements, leading to redundant search steps and a failure to identify inconsistent assignments until much later in the process.
This loss of "deductive strength" is a recurring theme. Narodytska et al. show that for problems involving both uniqueness and ordering (like scheduling), decomposing the logic into binary constraints prevents the solver from enforcing the same level of consistency as a unified global propagator.
The Communication Barrier
Decomposition also creates a communication barrier between different parts of the problem logic. In many real-world problems, symmetry-breaking rules and problem-specific constraints are treated as independent entities. Narodytska et al. demonstrate that when these constraints are prevented from "talking" to each other during the propagation phase, the solver fails to prune large areas of the search space that a holistic view would have immediately flagged as infeasible.
Similarly, Huertas and Van Hentenryck observe that decoupling assignment decisions from scheduling logic hinders the solver's ability to eliminate infeasible branches early. This lack of integration forces the search process to rediscover the same contradictions repeatedly across different components.
Preserving Power through Smart Decompositions
The research direction is not merely about avoiding decomposition, but about finding ways to decompose without losing intelligence. Bessiere et al. demonstrate that some complex constraints, like ALL-DIFFERENT, can be broken into arithmetic parts that still maintain their full pruning power, provided the decomposition is designed to preserve the underlying logic.
For example, Narodytska et al. introduced a "pyramid" decomposition for the NVALUE constraint. By carefully structuring the sub-constraints, they achieved bound consistency—a high standard of pruning—while allowing the constraint to be used in general-purpose SAT and Integer Programming solvers.
Structural Complexity and Scalability
The overhead of decomposition also manifests in how solvers handle problem structure. Traditional decomposition methods like primal treewidth often fail when a single global constraint links a large number of variables, causing the structural complexity to explode. Ganian et al. argue that new parameters are needed to handle these "messy" global interactions that traditional tree-based techniques cannot resolve.
Ultimately, the choice to decompose is a trade-off between the simplicity of the solver's components and the efficiency of the search. As Winter et al. show with string edit distance, specialized global propagators that leverage techniques like dynamic programming can outperform decompositions by orders of magnitude precisely because they maintain a unified, global view of the problem's constraints.
Key Foundational Work
Multiset Ordering Constraints (2003) — contributed 2 concept elements to this direction.
The Symmetric Alldiff Constraint (1999) — contributed 1 concept elements to this direction.
The Difference All-Difference Makes (1999) — contributed 1 concept elements to this direction.