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_selectand_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.
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.
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