Improving Repair-Based Constraint Satisfaction Methods by Value Propagation

Nobuhiro Yugami, Yuiko Ohta, Hirotaka HaraAAAI 1994

Introduction

Constraint Satisfaction Problems (CSPs) are fundamental to many areas of artificial intelligence, including scheduling, planning, and design. These problems involve finding assignments for a set of variables that satisfy a collection of constraints. A popular approach to solving CSPs is the use of repair-based methods, such as Min-Conflicts Hill Climbing (MCHC) or GSAT. These algorithms begin with a random initial assignment and iteratively "repair" it by changing variable values to reduce the number of violated constraints.

While efficient for many instances, repair-based methods frequently encounter the "local minimum trap." A local minimum is a state where any single-variable change increases the total number of conflicts, yet the current state is not a solution. Traditional solvers often address this by performing a random restart, which can be highly inefficient for large, complex problems where the search space is vast and local minima are prevalent.

The EFLOP Procedure

This paper introduces EFLOP (Escaping From Local Optima by Propagation), a meta-procedure designed to help solvers navigate out of local minima more effectively than random restarts. Instead of discarding the current state, EFLOP performs a coordinated "jump" to a new region of the search space by propagating value changes through satisfied constraints.

When a solver becomes stuck in a local minimum, EFLOP is triggered:

  1. Initial Perturbation: A variable involved in a conflict is selected and assigned a new random value.
  2. Value Propagation: This change likely violates constraints that were previously satisfied. EFLOP attempts to restore these constraints by changing the values of other variables involved in them.
  3. Recursive Ripple: This process continues, propagating changes through the network of satisfied constraints. To ensure efficiency and prevent infinite loops, each variable is changed at most once during a single escape attempt.
  4. Heuristic Selection: When multiple variables could be changed to satisfy a constraint, EFLOP employs a heuristic to choose the one that minimizes the introduction of new conflicts.

Conceptual Framework: Islands of Consistency

The core intuition behind EFLOP is that local minima often consist of "islands" of consistency—sub-problems where all internal constraints are satisfied, but which are in conflict with each other. A single-variable change is often insufficient to resolve these inter-island conflicts without breaking internal consistency.

Figure 1: Local minima often arise from conflicting sub-problems or "islands of consistency." To escape, an entire sub-problem must be reconfigured.

As illustrated in Figure 1, changing a single variable in "sub-problem 1" might break multiple internal constraints. EFLOP uses propagation to shift an entire "island" to a new configuration that is more likely to be compatible with the rest of the problem.

Experimental Evaluation

The authors evaluated EFLOP across three NP-complete domains: Graph 3-Colorability, Random Binary CSPs, and Propositional Satisfiability (SAT). In all cases, the addition of EFLOP significantly reduced the search effort required to find a solution.

For Random Binary CSPs, the difficulty of the problem is often tied to the "strength" of the constraints (the ratio of forbidden to permitted value pairs). Search effort typically peaks at a phase transition point where the probability of solvability is approximately 50%.

Figure 2: Comparison of search effort (hill climbing steps) between standard MCHC and MCHC+EFLOP across varying constraint strengths.

As shown in Figure 2, MCHC+EFLOP dramatically outperforms standard MCHC, particularly at the hardest instances (strength ≈ 0.64). For 60-variable binary CSPs, the version with EFLOP was more than 10 times faster. Similar results were observed in other domains:

  • Graph Coloring: For 150-node graphs, search steps dropped from ~334,000 (MCHC) to ~4,000 (MCHC+EFLOP).
  • SAT: For complex 5-SAT problems, GSAT+EFLOP achieved a 10x speedup over basic GSAT.

Conclusion

EFLOP provides a powerful, domain-independent mechanism for escaping local minima in repair-based CSP solvers. By leveraging the structure of satisfied constraints to propagate changes, it performs more intelligent "jumps" than random restarts. While the current implementation uses a simple conflict-minimization heuristic, future work could explore more sophisticated propagation strategies. Furthermore, the authors suggest that EFLOP may be particularly effective for structured real-world problems, such as AI planning, where strong functional dependencies between variables are common.

Summary updated

BibTeX
@inproceedings{yugami1994improving,
  author = {Nobuhiro Yugami and Yuiko Ohta and Hirotaka Hara},
  title = {{Improving Repair-Based Constraint Satisfaction Methods by Value Propagation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure