Abstract
Weighted Constraint Satisfaction Problems (WCSPs) provide a robust framework for modeling optimization problems where constraints are "soft" and associated with costs. This paper introduces Existential Directional Arc Consistency (EDAC*), a novel local consistency property that bridges the gap between weak properties like AC and overly strong ones like Full Arc Consistency (FAC). By ensuring that every variable has at least one "fully supported" value across all constraints, EDAC enables solvers to derive significantly tighter lower bounds. Our evaluation demonstrates that maintaining EDAC (MEDAC) leads to speedups of up to an order of magnitude over previous state-of-the-art methods like FDAC.
Introduction
In a standard Constraint Satisfaction Problem (CSP), the objective is to find any assignment that satisfies all constraints. In contrast, WCSPs assign costs to constraint violations, and the goal is to find an assignment that minimizes the total cost. Since finding the global minimum is NP-hard, solvers rely on local consistency techniques to prune the search space. These techniques use "projection" and "extension" operations to shift costs between constraints and variables, thereby increasing the global lower bound ($C_\emptyset$). If this lower bound exceeds the current best solution's cost, the branch is pruned.
Existing properties like AC (Arc Consistency) and FDAC (Full Directional Arc Consistency) are widely used but often fail to capture all possible cost-saving opportunities. Conversely, FAC* (Full Arc Consistency) is too computationally expensive and may not even converge. This paper proposes EDAC as a "sweet spot"—stronger than FDAC but guaranteed to exist and efficient to enforce.
Methodology: Existential Arc Consistency
The authors introduce two primary concepts:
- Existential Arc Consistency (EAC*): A variable $i$ is EAC* if there exists at least one value $a$ in its domain such that its unary cost is zero and it is "fully supported" (has zero cost) in every constraint it participates in.
- EDAC: This property combines the directional strengths of FDAC with the new EAC* requirement.
The enforcement of EDAC* is handled by a sophisticated propagation engine that utilizes three priority queues to manage different consistency levels. This ensures that when a cost movement repairs one property but breaks another, the affected constraints are efficiently revisited and repaired.
Experimental Evaluation
The performance of MEDAC (Maintained EDAC) was compared against MFDAC* across several distinct benchmarks:
- Random Max-SAT: 80-variable 2-SAT and 40-variable 3-SAT instances with varying clause densities.
- Random Max-CSP: Binary problems ranging from sparse to complete connectivity.
- Uncapacitated Warehouse Location Problem (UWLP): Standard benchmarks from the OR Library and challenging MO-MP instances.
Key Results
The results demonstrate that the additional pruning power of EDAC* far outweighs its computational overhead in most scenarios.
- Max-SAT: MEDAC achieved up to a 5.1x speedup* on Max-2SAT problems.
- Max-CSP: Speedups ranged from 2.0x to 9.5x, with the most significant gains seen in "Sparse-Tight" problems where constraint graphs are less dense.
- UWLP: For large-scale warehouse problems, MEDAC was orders of magnitude faster, solving instances in fractions of a second that took MFDAC over a minute.
- Competitive with MILP: MEDAC* proved competitive with commercial solvers like CPLEX 9.0 on specific optimization domains, highlighting the viability of WCSP techniques for traditional Mixed-Integer Linear Programming tasks.
Conclusion
EDAC* represents a significant advancement in local consistency for WCSPs. By focusing on "existential" support rather than universal support, it provides a powerful pruning mechanism that is both robust and efficient. Future work includes extending these properties to native n-ary constraints and exploring "lazy" enforcement strategies to further reduce overhead in simpler problem instances.
Summary updated