Abstract
The alldifferent constraint is a cornerstone of Constraint Satisfaction Problems (CSPs), yet its propagation is often computationally wasteful. In many real-world scenarios, the majority of propagator calls fail to prune any values. This paper presents a novel approach to identify "useless" propagation early by leveraging a new "Theorem of Unimportant Edges." By integrating this logic into standard graph algorithms, the authors achieve significant performance gains, with speedups reaching up to 5x on major benchmarks.
Introduction
In automated reasoning, solvers use constraint propagation to narrow the search space by removing values that cannot satisfy specific rules. The alldifferent constraint—requiring a set of variables to take distinct values—is ubiquitous in scheduling, Sudoku, and industrial optimization. While achieving Generalized Arc Consistency (GAC) is the gold standard for this constraint, it is often inefficient. Research indicates that 80% to 90% of propagator calls in complex problems result in zero pruning. This "useless propagation" consumes vast computational resources. Previous attempts to mitigate this often introduced overhead that negated any gains.
Methodology: The Theorem of Unimportant Edges
The standard approach for alldifferent constraints, established by Régin, treats the problem as a bipartite matching between variables and values. The algorithm finds a Maximum Matching and then identifies Strongly Connected Components (SCCs) in a directed graph to find inconsistent edges.
The authors introduce the Theorem of Unimportant Edges, which posits that if a variable-value pair (an edge) is removed but was part of an "alternating cycle" of other available assignments, the graph's overall consistency remains unchanged.
Instead of a full SCC analysis, the authors modified Tarjan’s SCC algorithm to include "Early Detection." During the Depth-First Search (DFS), the algorithm tracks cycles. If recently deleted edges are found to be contained within these cycles, the algorithm terminates immediately. This "fail fast" mechanism operates with minimal overhead by utilizing information already collected during the DFS.
Experimental Evaluation
The algorithm was tested on 93 benchmark instances across eight domains, including Langford’s number, Golomb rulers, Quasigroup existence, and Sports scheduling. Synthetic bipartite graphs with up to 16,000 nodes were also used to evaluate scalability.
Key Results
- Performance Gains: The new propagator outperformed state-of-the-art methods by 1x to 5x.
- Efficiency in Dense Graphs: The technique is most effective in dense graphs where alternative paths (cycles) are abundant, making removed edges more likely to be "unimportant."
- Scalability: Unlike many algorithms that struggle with scale, this method becomes more effective as problem size increases because the likelihood of finding redundant cycles grows.
- Quantified Uselessness: In domains like Sports Scheduling, the authors confirmed that over 90% of propagator calls were useless and could be successfully bypassed or terminated early.
Conclusion and Future Work
This research provides a seamless way to optimize the alldifferent constraint by baking early detection into the core of the SCC algorithm. While highly effective for large and dense problems, future work may extend this logic to other global constraints, such as cardinality constraints, and explore its interaction with modern non-chronological search strategies.
Summary updated