Existential arc consistency: Getting closer to full arc consistency in weighted CSPs

Simon de Givry, Federico Heras, Matthias Zytnicki, Javier LarrosaIJCAI 2005

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:

  1. 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.
  2. EDAC: This property combines the directional strengths of FDAC with the new EAC* requirement.
Illustration of cost projection and extension in a constraint triangle to reach higher consistency levels.

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.

Performance comparison between MFDAC* and MEDAC* on Max-SAT instances showing CPU time vs number of clauses.
  • 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

BibTeX
@inproceedings{givry2005existential,
  author = {Simon de Givry and Federico Heras and Matthias Zytnicki and Javier Larrosa},
  title = {{Existential arc consistency: Getting closer to full arc consistency in weighted CSPs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure