Greedy or Not? Best Improving versus First Improving Stochastic Local Search for MAXSAT

L. Darrell Whitley, Adele E. Howe, Doug HainsAAAI 2013 · DOI

Introduction

In the realm of combinatorial optimization, the Maximum Satisfiability (MAXSAT) problem stands as a cornerstone with significant industrial implications, ranging from hardware verification to complex scheduling. To tackle these problems, researchers often employ Stochastic Local Search (SLS). A fundamental design choice in SLS is the move selection strategy: should the solver greedily pick the "best improving" move from all possibilities, or settle for the "first improving" move encountered?

Historically, the consensus was that this choice mattered little for small-scale problems. However, as industrial instances have scaled to millions of variables, the "greedy" approach may actually be a hindrance. This paper investigates whether being less greedy leads to better long-term outcomes in modern, large-scale MAXSAT landscapes.

Methodology: Bridging the Gap

Comparing these strategies fairly requires addressing the computational overhead of greedy selection. Finding the absolute best move typically requires $O(n)$ time, where $n$ is the number of variables. To level the playing field, the authors developed Best-13, an approximate best-improving algorithm. By using 13 buffers to track moves of varying quality, this method identifies near-optimal moves in constant time ($\Theta(1)$), matching the speed of first-improving strategies.

The researchers also introduced a two-stage analysis to dissect the search process:

  1. The Sprint: The initial descent toward the first local optimum.
  2. The Marathon: The subsequent heuristic exploration of "plateaus" where no single move immediately improves the objective function.

The Greedy Trap and Critical Variables

A key finding is that industrial problems often contain "critical variables"—those appearing in a disproportionately high number of clauses. A greedy "best improving" strategy flips these variables almost immediately to secure a large initial reduction in unsatisfied clauses.

However, this early "fixing" of critical variables often traps the solver in a suboptimal region of the search space. In contrast, a "first improving" strategy tends to preserve these high-impact moves, allowing for more flexible navigation of the search landscape later in the process.

Search progress comparison: First-SLS (solid line) eventually achieves lower unsatisfied clause counts than the greedy Best-13 approach (dashed line).

Key Results

The experimental results reveal a striking "reversal" in performance. While greedy strategies often lead the "sprint" to the first local optimum, they frequently stagnate during the "marathon" phase. As the search progresses, the first-improving strategy (First-SLS) eventually overtakes the greedy approach (Best-13).

In a comparison across 13 large-scale problems, First-Improving outperformed Best-Improving on 11 instances after five minutes of CPU time. Furthermore, the Best-13 buffered approach proved to be one to two orders of magnitude faster than traditional greedy implementations like GSAT, demonstrating that sophisticated data structures can make "greedy" search computationally viable, even if it remains strategically inferior for large industrial problems.

Performance comparison across industrial (i0-i9) and random (s1-s3) instances, showing the efficiency of First-SLS and Best-13 over standard GSAT.

Conclusion

The research challenges the intuition that more greediness is always better. For large-scale industrial MAXSAT problems, a first-improving strategy avoids the "greedy trap" of prematurely fixing critical variables, leading to superior long-term performance and periodic "bursts" of progress. Future work will delve deeper into the mathematical properties of these critical variables to further optimize search scheduling.

Summary updated

BibTeX
@inproceedings{whitley2013greedy,
  author = {L. Darrell Whitley and Adele E. Howe and Doug Hains},
  title = {{Greedy or Not? Best Improving versus First Improving Stochastic Local Search for MAXSAT}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8668},
}

Loading related content...

Figure