Abstract
Solving overconstrained problems requires finding a maximal partial solution that satisfies the greatest number of constraints. This paper presents conjunctive width heuristics that integrate graph connectivity with domain-specific consistency measures to optimize Branch and Bound search. By prioritizing variables with high "width" (connectivity to assigned variables) and using Arc Consistency Counts (ACC) as tie-breakers, the proposed methods achieve up to a 10,000-fold reduction in constraint checks on sparse problem instances.
Introduction
In artificial intelligence, Constraint Satisfaction Problems (CSPs) typically involve finding a single assignment of values to variables that satisfies all constraints. However, real-world applications like machine vision and complex scheduling are often overconstrained, meaning no perfect solution exists. In these scenarios, the goal shifts to finding a Maximal CSP solution—one that maximizes the number of satisfied constraints.
Finding optimal partial solutions is an optimization task usually handled by Branch and Bound (B&B) algorithms. The efficiency of B&B depends heavily on the ability to prune the search tree using a tight lower bound on the number of violations. Weak estimates lead to exhaustive exploration of unproductive branches. This paper introduces variable-ordering heuristics designed to force the lower bound to rise rapidly, thereby accelerating the search process.
Conjunctive Width Heuristics
The core contribution is the development of Conjunctive Width Heuristics. Unlike traditional heuristics that rely on a single metric, this approach uses a tiered strategy:
- Width at a Node: The primary criterion selects the variable sharing the most constraints with already-assigned variables. This focuses the search on the most densely connected sub-graphs.
- Tie-breaking with Domain Info: When widths are equal, secondary factors such as Minimum Domain Size or Mean Arc Consistency Counts (ACC) are employed.
- Preprocessing: ACCs are pre-calculated to identify how many values in adjacent domains are incompatible with specific assignments.
As shown in Figure 5, the choice of variable ordering significantly impacts how consistency information is accumulated during search. The "Width/Dom" heuristic ensures that significant constraint information is processed early, which is critical for raising the lower bound and pruning the search tree.
Experimental Methodology
The heuristics were evaluated using randomly generated sparse constraint graphs, which mirror the structure of many real-world problems.
- Problem Size: 10, 15, and 20 variables.
- Graph Density: Focused on sparse graphs with an average degree of 3.
- Heterogeneity: Varied domain and constraint sizes to simulate non-uniform real-world conditions.
- Algorithm Integration: The heuristics were implemented within the RPO (Retrospective, Prospective, and Ordering) algorithm, which utilizes backmarking to eliminate redundant constraint checks.
Results and Discussion
The experimental results demonstrate a dramatic improvement in search efficiency. On 20-variable sparse problems, the conjunctive width heuristics outperformed basic Branch and Bound by four to five orders of magnitude.
As illustrated in Figure 1, the number of constraint checks for the RPO-w/d method remains relatively low (approximately $10^4$) even as problem size increases, whereas traditional methods like P-BB escalate toward $10^8$. This 10,000x speedup highlights the synergy between graph-based width and domain-specific information. The "one-two punch" of high width (increasing current cost) and small domain size (increasing estimated future cost) allows the algorithm to exceed the current upper bound much earlier in the search.
Conclusion
Conjunctive width heuristics provide a powerful mechanism for solving sparse Maximal CSPs. By combining structural graph properties with local consistency measures, these heuristics enable Branch and Bound algorithms to prune search spaces with unprecedented efficiency. While the advantage is most pronounced in sparse graphs (average degree ≤ 4), the principles of synergistic variable ordering remain a cornerstone for modern optimization solvers. Future work may explore scaling these techniques to massive industrial problems and extending them to non-binary constraints.
Summary updated