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:
- The Sprint: The initial descent toward the first local optimum.
- 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.
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.
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