Large Neighbourhood Search for Anytime MaxSAT Solving

Randy Hickey, Fahiem BacchusIJCAI 2022 · DOI

TL;DR

This paper introduces a novel application of Large Neighbourhood Search (LNS) to improve anytime MaxSAT solvers. By intelligently selecting neighbourhoods to explore, their LNS-based approach can significantly enhance the quality of solutions found by existing anytime solvers, pushing the state-of-the-art in incomplete MaxSAT solving.

What Problem Does This Paper Address?

Maximum Satisfiability (MaxSAT) is a crucial problem in discrete optimization, with applications ranging from computer-aided design to timetabling. While complete MaxSAT solvers aim for optimal solutions, they can be too slow for many real-world problems. This has led to a growing interest in incomplete MaxSAT solvers, which prioritize finding good solutions quickly, even without optimality guarantees. These are particularly useful in "anytime" contexts where solutions are needed within a time limit. However, existing anytime solvers can still be improved. This paper addresses the challenge of further enhancing the performance of these anytime MaxSAT solvers by leveraging the strengths of Large Neighbourhood Search (LNS), a powerful technique for incomplete optimization that, surprisingly, had not been directly applied to MaxSAT solving before.

Methods

The core of this work is the integration of Large Neighbourhood Search (LNS) into an anytime MaxSAT solving framework. The proposed method, outlined in Algorithm 1, works as follows:

  1. Initial Solution: An existing anytime MaxSAT solver (AT_MaxSlv) is used to generate an initial feasible solution within a given time bound.
  2. Neighbourhood Selection: This is the novel contribution. Instead of a generic approach, the paper proposes a sophisticated policy (Algorithm 2) for selecting a "neighbourhood" to explore. This involves:
  3. Literal Weighting: Assigning weights to literals in the current solution based on how much they contribute to satisfying soft clauses or how costly it is to falsify them. This weighting is made exponential for better discrimination.
  4. Propagation: Incorporating unit propagation to fix not only the selected literals but also any literals implied by them due to hard clauses. This helps to control the size of the search space.
  5. Dynamic Neighbourhood Size: The size of the neighbourhood (controlled by a parameter δ) is dynamically adjusted. It starts larger and shrinks if no improvement is found, eventually leading to a full search by the complete solver if necessary.
  6. Neighbourhood Search: A complete MaxSAT solver (MaxHS) is used to exhaustively search the selected neighbourhood for a better solution.
  7. Iteration: Steps 2 and 3 are repeated until the time limit is reached, always keeping track of the best solution found so far.

The key novelty lies in the intelligent, probabilistic, and propagation-guided neighbourhood selection policy, which aims to efficiently guide the search towards better solutions.

Datasets

The experiments were conducted using benchmark instances from the 2020 and 2021 MaxSAT Evaluation competitions. This includes both weighted and unweighted instances. The authors specifically mention using the 2020 benchmarks for initial tuning to avoid overfitting and then the union of 2020 and 2021 benchmarks for final evaluation.

Key Insights and Ideas

  • LNS is a natural fit for anytime MaxSAT: Despite its absence in prior work, LNS's ability to leverage complete solvers for incomplete search makes it a promising technique for improving anytime MaxSAT solvers.
  • Intelligent neighbourhood selection is crucial: A well-designed neighbourhood selection policy is key to LNS's effectiveness. The proposed probabilistic and propagation-guided approach significantly outperforms simpler methods.
  • LNS excels at improving good solutions: While LNS can improve solutions across the board, it shows a particular advantage in refining already high-quality solutions (those with scores > 0.75). This suggests a "portfolio" approach where an anytime solver finds a good solution, and LNS then fine-tunes it.
  • Poor initial solutions are challenging for LNS: LNS can get "stuck" exploring neighbourhoods close to the initial solution. For very poor initial solutions, other anytime solvers might be better at making initial large jumps in quality.
  • A small investment in LNS yields significant gains: Even a short period of LNS (around 50 seconds) applied to the best solution found by an anytime solver can lead to substantial performance improvements.

Key Results

  • The proposed LNS algorithm, when applied to the best solutions found by three state-of-the-art anytime MaxSAT solvers (TT-Open-WBO, Loandra, and satlike), consistently improved their performance.
  • For the 2020 and 2021 MaxSAT Evaluation benchmarks, the LNS-enhanced solvers achieved higher average scores than their base counterparts. For example, LNS-TT-Open-WBO achieved a total score of .865 compared to TT-Open-WBO's .854.
  • The LNS approach was able to improve the best-known solution for 95 instances across the 2020 and 2021 datasets, with average improvements of 3.7% and 4.8% respectively.
  • Experiments showed that running LNS for a portion of the total time (e.g., 50 seconds) after an anytime solver had run for the remainder (e.g., 250 seconds) yielded better results than running either solver for the full duration. This highlights the benefit of a hybrid approach.

Limitations and Future Work

  • Handling poor initial solutions: The paper acknowledges that LNS is less effective at turning very poor initial solutions into good ones compared to other anytime solvers.
  • Incremental MaxSAT solving: The current LNS implementation calls the complete solver repeatedly, re-processing the instance each time. Developing an incremental MaxSAT framework to reuse learned information (like cores or clauses) could lead to significant speedups.
  • Tighter integration: The current approach uses LNS once to improve a solution. Future work could explore tighter integration, where the anytime solver might invoke LNS periodically or adjust its search based on LNS-improved solutions.
  • Adaptive neighbourhood selection: The paper suggests exploring adaptive strategies for neighbourhood selection, similar to those used in adaptive large neighbourhood search, to prevent the solver from getting stuck in local optima.
  • Parameter tuning: Further fine-tuning of LNS parameters or exploring multiple LNS runs on different solutions from the base solver could yield additional improvements.

Summary updated

BibTeX
@inproceedings{hickey2022large,
  author = {Randy Hickey and Fahiem Bacchus},
  title = {{Large Neighbourhood Search for Anytime MaxSAT Solving}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/253},
}
Figure