An Efficient Global-Search Strategy in Discrete Lagrangian Methods for Solving Hard Satisfiability Problems

AAAI 2000

TL;DR

This paper introduces a novel global-search strategy for solving difficult Satisfiability (SAT) problems, which are notoriously hard for existing algorithms. By penalizing the search for revisiting previously explored regions in the search space, their Discrete Lagrangian Method (DLM-2000-SAT) significantly improves performance on challenging benchmarks, outperforming previous methods.

What Problem Does This Paper Address?

Satisfiability (SAT) problems are fundamental in computer science and have wide-ranging applications in areas like AI, design automation, and planning. The challenge lies in finding a truth assignment for a set of Boolean variables that satisfies a given formula. While many algorithms exist, "hard" SAT instances, often characterized by numerous "traps" (local minima in the search space) and repetitive exploration of similar regions, remain a significant hurdle. Existing methods, including earlier Discrete Lagrangian Methods (DLM), struggle with these hard instances, getting stuck in traps or inefficiently exploring the search space. This paper aims to address this by developing a more robust global-search strategy that can effectively navigate these difficult landscapes.

Methods

The core of this paper is the introduction of a new global-search strategy integrated into a Discrete Lagrangian Method (DLM). The DLM framework itself formulates SAT as a constrained optimization problem, minimizing the number of unsatisfied clauses. The novelty lies in the distance penalty term added to the Lagrangian function. This penalty is calculated based on the Hamming distance between the current search point and a history of previously visited points.

Here's a breakdown:

  • Discrete Lagrangian Method (DLM): This is the foundation. It uses Lagrange multipliers to transform a constrained optimization problem into an unconstrained one, iteratively adjusting multipliers to guide the search.
  • Distance Penalty: This is the key innovation. It penalizes the search for revisiting regions of the search space that have been explored before. This is achieved by adding a term to the Lagrangian that increases as the current point gets closer (in Hamming distance) to historical points.
  • Historical Point Queue: To manage memory and computation, a fixed-size queue (FIFO) is used to store recent historical points instead of the entire trajectory.
  • Trap Escaping: The distance penalty naturally helps escape traps. When a trajectory is stuck in a trap, points within the trap are close to each other, leading to a significant penalty and pushing the search out. However, it's more general than just trap-escaping, as it also discourages revisiting any region, even outside traps.
  • DLM-2000-SAT Algorithm: The paper presents a specific algorithm (Figure 2) that incorporates this strategy, including heuristics for selecting variables to flip, maintaining a tabu list, and updating Lagrange multipliers based on flat moves (moves that don't improve the objective).

Datasets

The paper evaluates its proposed DLM-2000-SAT algorithm on benchmark SAT instances from the DIMACS archive and SATLIB. These benchmarks represent various classes of SAT problems, including artificially generated random-3-SAT, inductive inference problems, learning parity functions, circuit fault analysis, and graph coloring problems. The authors specifically highlight their performance on "hard" instances that were previously difficult to solve.

Key Insights and Ideas

  • Revisiting is Bad: The fundamental insight is that for hard SAT problems, simply avoiding local minima (traps) isn't enough. The search also needs to actively avoid revisiting regions of the search space it has already explored, as this often leads to unproductive cycles.
  • Hamming Distance as a Global Navigator: Using Hamming distance to measure similarity between search points provides an effective way to quantify "revisiting" in the discrete search space.
  • Generalization Beyond Traps: The distance penalty strategy is more general than specific trap-escaping heuristics because it discourages repetition across the entire search landscape, not just within identified traps.
  • Balancing Constraints and Exploration: The DLM framework, with its dynamic adjustment of Lagrange multipliers, combined with the distance penalty, offers a sophisticated way to balance satisfying constraints and exploring the search space efficiently.

Key Results

The DLM-2000-SAT algorithm demonstrated significant improvements on hard SAT instances:

  • 100% Success Ratio: The algorithm achieved a 100% success ratio on all tested benchmark instances, including those previously problematic for other methods.
  • Speedup on Hard Instances: It solved instances from the f2000, par16-, hanoi4, and g-class categories much faster than previous DLM implementations and comparable or better than other state-of-the-art algorithms like WalkSAT, GSAT, and DLM-99-SAT. For example, it solved f2000 in 19.2 seconds with 1,102,816 flips, significantly outperforming DLM-99-SAT's adjusted CPU time of 16.2 seconds (though direct comparison is complex due to different hardware).
  • Competitive Performance: On graph coloring problems, DLM-2000-SAT outperformed the LSDL heuristic-repair method, using up to 60% less CPU time on certain instances.
  • Simpler Parameter Tuning: Compared to prior DLM versions, DLM-2000-SAT is simpler and requires fewer parameters to tune.

Limitations and Future Work

  • Computational Overhead: The paper acknowledges that the new strategy incurs more overhead per flip due to the search for a suitable variable and the distance penalty calculation. However, this is offset by the overall reduction in CPU time due to more effective exploration.
  • Queue Management Complexity: For very simple problems, the complexity of maintaining the historical point queue can lead to a slight disadvantage in CPU time compared to simpler methods.
  • Future Work: While not explicitly detailed, the success of this global-search strategy suggests that further exploration of penalty functions and queue management strategies could lead to even more efficient and robust SAT solvers. The authors' focus on hard instances implies that extending this to even more complex or larger-scale SAT problems would be a natural next step.

Summary updated

BibTeX
@inproceedings{2000efficient,
  title = {{An Efficient Global-Search Strategy in Discrete Lagrangian Methods for Solving Hard Satisfiability Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2000},
}
Figure