Enhancements of Branch and Bound Methods for the Maximal Constraint Satisfaction Problem

AAAI 1996

TL;DR

This paper introduces two novel techniques to significantly speed up solving over-constrained problems (where not all constraints can be satisfied). By improving the initial upper bound using heuristic repair and enhancing lower bound calculations with directed arc consistency, the authors demonstrate substantial reductions in search effort, making previously intractable problems more manageable.

What Problem Does This Paper Address?

Constraint Satisfaction Problems (CSPs) involve assigning values to variables subject to certain constraints. However, many real-world problems are "over-constrained," meaning no assignment can satisfy all conditions. In such cases, the goal shifts to finding an assignment that satisfies the most constraints, or equivalently, minimizes the number of violated constraints. This is known as the Maximal Constraint Satisfaction Problem (MAX-CSP). Traditional CSP solvers struggle with MAX-CSPs because the cost function (number of violated constraints) is additive, unlike the Boolean AND used in standard CSPs, making pruning less effective. This paper aims to improve the performance of complete search methods, specifically branch and bound algorithms, for solving these challenging MAX-CSPs.

Methods

The paper proposes two main enhancements to branch and bound algorithms for MAX-CSPs:

  1. Improved Upper Bounds via Heuristic Repair: Before initiating the main branch and bound search, a heuristic repair procedure (like hill-climbing) is run to quickly find a good, though not necessarily optimal, solution. The cost (number of violated constraints) of this heuristically found solution is used as the initial upper bound for the branch and bound search. This tighter initial bound allows the search to prune branches more aggressively.
  2. Enhanced Lower Bounds with Cascaded Directed Arc Consistency (DACCs): This method extends directed arc consistency preprocessing. DACCs count inconsistencies for variable values based on future variables in a search order. The "cascaded" aspect involves inferring tighter lower bounds by propagating these DACC counts backward through the search order. This process uses information about how supporting and non-supporting values in future variables contribute to the cost, allowing for more accurate lower bound estimates early in the search.

Datasets

The paper evaluates its methods on randomly generated MAX-CSP instances. These instances are categorized into:

  • Type 1 problems: Defined by fixed density and varying domain size and constraint tightness.
  • Type 2 problems: More homogeneous, with elements included with a fixed probability, allowing for controlled variation of density and constraint tightness.

The experiments were conducted on 15-variable and 30-variable problems, and later on 40-variable problems to assess scalability.

Key Insights and Ideas

  • The Power of a Good Initial Guess: Even a heuristically derived upper bound that is "close" to the optimal solution can dramatically reduce search effort. The closer the initial bound is to the optimum, the greater the reduction, but significant gains are still observed even when the bound is slightly above optimal.
  • Cascading Information for Deeper Pruning: Propagating inconsistency information backward through the search order (cascaded DACCs) allows for more informed pruning decisions early in the search, especially for difficult problems. This is more effective than standard DACCs alone.
  • Complementary Techniques: The upper bound improvement (heuristic repair) and lower bound enhancement (cascaded DACCs) are independent and can be combined for even greater performance gains.
  • Problem Size Matters: The benefits of these enhancements appear to become more pronounced as problem size increases, suggesting their utility for larger, more complex MAX-CSPs.

Key Results

  • Using an initial upper bound equal to the optimal distance reduced search effort by a factor of 1.5-6 for 15-variable problems.
  • Even when the initial upper bound was slightly above the optimum (e.g., 2-3 units away), significant reductions in search effort were observed.
  • For 30-variable problems, the cascaded DACC method, combined with variable and value ordering, showed substantial improvements, especially at higher densities.
  • Heuristic repair methods (weak commitment search, min-conflicts, breakout) could find solutions close to optimal within seconds, providing valuable initial upper bounds.
  • Combining heuristic repair for initial upper bounds with cascaded DACCs for lower bounds led to dramatic improvements, with some problems becoming solvable with very few or no constraint checks during the exhaustive search phase. For 40-variable problems, this combination reduced search effort by an order of magnitude in some cases.

Limitations and Future Work

  • Heuristic Repair Tradeoff: The paper acknowledges the tradeoff between the effort spent on heuristic repair to find a good initial upper bound and the subsequent reduction in branch and bound search effort. The optimal cutoff time for heuristic repair needs careful consideration.
  • Problem Dependence: The effectiveness of DACCs is dependent on the presence of arc consistency violations.
  • Future Work: The authors suggest that these methods become more useful as problem size increases, implying further investigation into their scalability and application to even larger instances. The paper also hints at the potential for combining these techniques with other search strategies.

Summary updated

BibTeX
@inproceedings{1996enhancements,
  title = {{Enhancements of Branch and Bound Methods for the Maximal Constraint Satisfaction Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure