Trap Escaping Strategies in Discrete Lagrangian Methods for Solving Hard Satisfiability and Maximum Satisfiability Problems

AAAI 1999

TL;DR

This paper introduces "trap escaping strategies" for discrete Lagrangian methods (DLMs) to solve challenging Satisfiability (SAT) and Maximum Satisfiability (MAX-SAT) problems. By implicitly remembering and penalizing "traps" where search algorithms get stuck, their improved DLM (DLM-99-SAT) significantly outperforms previous methods on notoriously difficult benchmarks, even solving some previously unsolved instances.

What Problem Does This Paper Address?

Solving large-scale Satisfiability (SAT) and Maximum Satisfiability (MAX-SAT) problems is a fundamental challenge in computer science with applications in areas like artificial intelligence, circuit design, and operations research. Traditional methods like resolution and backtracking struggle with the combinatorial explosion of possibilities in large instances. Local search methods, while more scalable, often get stuck in "traps" – configurations where any small change to the variable assignments leads to a worse (or equally bad) objective function value, preventing them from reaching a satisfying solution. This paper specifically targets these hard-to-satisfy instances where existing local search algorithms, including their own prior DLM implementation (DLM-98-BASIC-SAT), fail to find solutions.

Methods

The core of the paper builds upon Discrete Lagrangian Methods (DLMs), which reformulate SAT/MAX-SAT as discrete constrained optimization problems. The key innovation here is the development of trap escaping strategies within the DLM framework.

  • Discrete Lagrangian Formulation: SAT is framed as minimizing the number of unsatisfied clauses, subject to all clauses being satisfied. This is achieved by introducing Lagrange multipliers ($\lambda_i$) for each clause, aiming to minimize a Lagrangian function $L_d(x, \lambda) = N(x) + \sum \lambda_i U_i(x)$, where $N(x)$ is the number of unsatisfied clauses and $U_i(x)$ is an indicator for clause $i$ being unsatisfied.
  • Identifying Traps: A trap is identified as a state where any single variable flip increases the Lagrangian value. This means the search is stuck in a local minimum with respect to single-variable moves.
  • Trap Escaping Strategy (DLM-99-SAT):
    • Implicit Trap Memory: Instead of explicitly storing trap configurations, the algorithm implicitly remembers traps by increasing the Lagrange multipliers ($\lambda_i$) of unsatisfied clauses that are frequently encountered in traps. This makes these clauses "more expensive" to leave unsatisfied, guiding the search away from such configurations.
  • SPECIAL-INCREASE Procedure: To prevent an "out-of-balance" situation where a few clauses dominate the weights, a special procedure is introduced. It monitors the ratio of the largest clause weight to the average weight. If this ratio exceeds a threshold, it selectively increases the Lagrange multipliers of clauses with the largest weights, aiming to force them into satisfaction and restore balance.
  • Other Heuristics: The method also incorporates tabu lists to avoid recently visited states and allows for "flat" and "up-hill" moves (moves that don't decrease or even increase the Lagrangian) to help escape local minima.

Datasets

The paper evaluates its approach on the DIMACS SAT benchmarks, specifically focusing on difficult and previously unsolved satisfiable instances like hanoi4, hanoi4-simple, par16-1 through par16-5, f2000, and par32-1-c through par32-3-c. They also test on MAX-SAT benchmarks from the DIMACS archive. No new benchmarks were introduced.

Key Insights and Ideas

  • Traps are a major bottleneck: The paper provides empirical evidence (Figure 2) showing that certain clauses are disproportionately trapped, highlighting this as a critical issue for local search.
  • Implicit memory is effective: The strategy of implicitly remembering traps by adjusting Lagrange multipliers is shown to be a powerful way to guide the search away from problematic regions without the computational overhead of explicit history storage.
  • Balancing weights is crucial: The introduction of the SPECIAL-INCREASE procedure demonstrates the importance of managing the Lagrange multiplier updates to avoid creating new imbalances that could hinder the search.
  • DLMs offer a principled approach: The paper reiterates that DLMs provide a solid mathematical foundation for local search heuristics, explaining why simpler methods might work in practice.

Key Results

  • Solving previously unsolved problems: DLM-99-SAT successfully solves several hard SAT benchmarks (f2000, par16-1-c to par16-5-c, par16-1 to par16-5, hanoi4) that were not well-handled by previous methods, including their own earlier DLM.
  • Improved performance on MAX-SAT: The algorithm also improves upon previous results for MAX-SAT benchmarks, finding optimal solutions for all tested problems within a limited number of runs and flips.
  • Reduced trap frequency: Figure 4 shows a significant reduction in the disparity of clause trap frequency after applying the SPECIAL-INCREASE procedure, indicating better control over trap occurrences.
  • High success ratios: For many difficult benchmarks, DLM-99-SAT achieves very high success ratios, demonstrating its robustness.

Limitations and Future Work

  • Unsolved instances: The authors acknowledge that they were unable to find solutions for eight satisfiable problems in the DIMACS archive (hanoi5, par32-4-c to par32-5-c, and par32-1 to par32-5). However, they did find assignments with only one unsatisfied clause for some of these, which is still a promising result.
  • MAX-SAT performance: While improved, the MAX-SAT success rate was slightly lower than another method (Mills & Tsang 1999), potentially because the algorithm was primarily designed for SAT.
  • Parameter tuning: The performance of DLM-99-SAT relies on carefully chosen parameters (e.g., $\delta_0, \delta_\alpha, \delta_\omega, \theta_1, \theta_2, \theta_3$). Future work could explore more adaptive or automated parameter tuning strategies.
  • Generalizability: While effective for SAT and MAX-SAT, exploring the application of these trap-escaping strategies to other discrete optimization problems could be a fruitful direction.

Summary updated

BibTeX
@inproceedings{1999trap,
  title = {{Trap Escaping Strategies in Discrete Lagrangian Methods for Solving Hard Satisfiability and Maximum Satisfiability Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure