Large-Neighbourhood Search for Optimisation in Answer-Set Solving

Thomas Eiter, Tobias Geibinger, Nelson Higuera Ruiz, Nysret Musliu, Johannes Oetsch, Daria Stepanova

Abstract

This paper introduces a novel framework that integrates Large-Neighbourhood Search (LNS)—a powerful metaheuristic for optimization—into the Answer-Set Programming (ASP) paradigm. By leveraging "multi-shot" solving to avoid redundant grounding and computations, the authors demonstrate that LNS can significantly outperform standard ASP solvers on notoriously difficult optimization problems, such as industrial scheduling and combinatorial puzzles. The framework, implemented as clingo-lns, allows for both declarative and imperative neighborhood definitions, providing a flexible tool for high-performance logic-based optimization.

Introduction

Answer-Set Programming (ASP) has emerged as a premier declarative language for solving complex constraint satisfaction and logic problems. While ASP solvers are highly efficient at finding feasible solutions, they often struggle with optimization tasks, particularly those involving large search spaces or high degrees of symmetry. Standard solvers typically rely on branch-and-bound algorithms which can become trapped in local optima, unable to find better bounds or prove optimality within practical time limits.

To address this, the authors propose bringing Large-Neighbourhood Search (LNS) to ASP. LNS is a metaheuristic that improves an initial solution through iterative "destroy and reconstruct" cycles. By relaxing a portion of the current solution and re-solving for those variables, the solver can "jump" to better regions of the search space that might be unreachable through standard local search.

Methodology

The core of the proposed framework is clingo-lns, built upon the Potassco solver suite. The implementation addresses the primary bottleneck of integrating metaheuristics with ASP: the cost of grounding. In traditional ASP, changing a constraint often requires re-processing the entire logic program.

Key Innovations

  • Multi-shot Solving: The framework maintains the solver's internal state and learned constraints across iterations. This "warm start" approach ensures that the solver does not waste time re-learning the fundamental structure of the problem.
  • Solving under Assumptions: By using the "assumptions" feature of clingo, the framework can temporarily fix parts of a solution without permanently altering the underlying logic. This allows for rapid experimentation with different neighborhoods.
  • Declarative Neighborhoods: A unique strength of this approach is that users can define which parts of a solution to "destroy" using simple ASP predicates like _lns_select and _lns_fix. This allows domain expertise to be encoded directly into the search strategy without complex imperative programming.

Experimental Evaluation

The authors evaluated clingo-lns against standard solvers across a variety of benchmarks, including the Traveling Salesperson Problem (TSP), the Social Golfer Problem (SGP), Sudoku puzzle generation, and real-world industrial scheduling.

Industrial Scheduling and TSP Results

In the context of parallel machine scheduling—a challenging task from semiconductor production—the combination of LNS with a greedy construction heuristic significantly outperformed the state-of-the-art clingo-dl approach. As shown in the performance distribution below, LNS consistently finds tighter makespan bounds.

Comparison of makespan bounds for industrial scheduling across different solver configurations.

For the Traveling Salesperson Problem, LNS demonstrated a consistent ability to find better solution bounds than plain clingo. Across twenty standard instances, the framework achieved an average improvement of 34% in solution quality, as detailed in the following table.

Comparison of solution quality (lower is better) between standard clingo and clingo-lns on TSP instances.

Key Insights

  • Efficiency of Randomness: Even a simple "random relaxation" strategy (destroying 20% of the solution at random) often yields significant improvements over baseline solvers without requiring custom logic.
  • Symmetry Breaking: LNS is particularly effective for highly symmetric problems like the Social Golfer Problem. By forcing the solver to focus on specific sub-structures, it bypasses the global symmetries that typically cause symbolic solvers to stall.
  • Hybrid Flexibility: The framework supports Python plugins, allowing users to combine the declarative power of ASP with imperative heuristics, such as using a greedy algorithm to generate the initial seed solution.

Conclusion and Future Work

The integration of LNS into ASP provides a robust path forward for solving large-scale industrial optimization problems that were previously out of reach for purely symbolic methods. While LNS cannot prove absolute optimality, its ability to find high-quality solutions quickly makes it an invaluable tool for practical applications. Future research will focus on self-adaptive LNS, where the system automatically tunes neighborhood sizes and destruction strategies based on real-time performance metrics.

Summary updated

Abstract

While Answer-Set Programming (ASP) is a prominent approach to declarative problem solving, optimisation problems can still be a challenge for it. Large-Neighbourhood Search (LNS) is a metaheuristic for optimisation where parts of a solution are alternately destroyed and reconstructed that has high but untapped potential for ASP solving. We present a framework for LNS optimisation in answer-set solving, in which neighbourhoods can be specified either declaratively as part of the ASP encoding, or automatically generated by code. To effectively explore different neighbourhoods, we focus on multi-shot solving as it allows to avoid program regrounding. We illustrate the framework on different optimisation problems, some of which are notoriously difficult, including shift planning and a parallel machine scheduling problem from semi-conductor production which demonstrate the effectiveness of the LNS approach.
BibTeX
@inproceedings{eiter2022large,
  author = {Thomas Eiter and Tobias Geibinger and Nelson Higuera Ruiz and Nysret Musliu and Johannes Oetsch and Daria Stepanova},
  title = {{Large-Neighbourhood Search for Optimisation in Answer-Set Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20502},
}
Figure