Learning to Break Symmetries for Efficient Optimization in Answer Set Programming

Alice Tarzariol, Martin Gebser, Konstantin Schekotihin, Mark LawAAAI 2023 · DOI

TL;DR

This paper introduces a novel method to automatically learn symmetry-breaking constraints for optimization problems in Answer Set Programming (ASP). By augmenting ASP programs with auxiliary rules and leveraging Inductive Logic Programming (ILP), the approach effectively prunes symmetric solutions, leading to significant speedups in finding optimal solutions for complex combinatorial problems.

What Problem Does This Paper Address?

Combinatorial optimization problems are ubiquitous in various fields, and Answer Set Programming (ASP) offers a powerful declarative paradigm for modeling and solving them. A major hurdle in solving these problems efficiently is the presence of symmetries in solution candidates. These symmetries mean that many different but structurally identical solutions exist, which can drastically slow down optimization algorithms as they explore redundant parts of the search space. While techniques exist to break symmetries, they often struggle with optimization statements in ASP, where solutions are ranked by weights. Existing methods for learning symmetry-breaking constraints can mistakenly discard optimal solutions if they are not lexicographically the smallest among symmetric ones. This paper addresses this gap by developing a method that learns symmetry-breaking constraints specifically for ASP optimization problems, ensuring that optimal solutions are preserved.

Methods

The core of this paper lies in extending existing ILP-based symmetry-breaking constraint learning for ASP. The key innovation is the introduction of auxiliary rules, denoted as $O_p$, which are added to the original ASP program $P$. These rules are designed to augment the program's dependency graph in a way that preserves the quality of solutions determined by weak constraints. Specifically, $O_p$ introduces auxiliary atoms that help SBASS (a tool for identifying symmetries) to partition solutions into cells where all solutions within a cell have the same optimization value.

The process involves:

  1. Augmenting the Program: Adding auxiliary rules $O_p$ to the ground ASP program $P$ to create $P \cup O_p$. This step is crucial for correctly identifying symmetries in the context of optimization.
  2. Symmetry Identification: Using SBASS on $P \cup O_p$ to identify symmetries. The auxiliary atoms ensure that these symmetries respect the optimization criteria.
  3. ILP Task Generation: Generating positive and negative examples for an Inductive Logic Programming (ILP) task. This is done by adapting the "full-SBCs" approach. For optimization problems, a modified algorithm (Algorithm 1) is proposed that considers the optimal value found in a pre-solving step. It prioritizes identifying optimal solutions as positive examples and non-optimal symmetric solutions as negative examples.
  4. Learning Constraints: Using an ILP system (ILASP) to learn first-order constraints from these examples. These learned constraints are then used to prune the search space for the original optimization problem.

The paper also discusses variations like "scalable full-SBCs" and "opt-scalable full-SBCs" to handle instances with a large number of solutions, and introduces mechanisms for ordering answer sets to better guide the learning process for optimization.

Datasets

The paper evaluates its framework on several benchmark combinatorial optimization problems:

  • Fastfood Problem: A standard ASP benchmark where the goal is to select a subset of restaurants as depots to minimize supply distances.
  • Pigeon-hole Problem and its extensions: Including color and owner assignments.
  • House-configuration Problem.
  • Partner Units Problem (PUP): Including instance families denoted by double, doublev, and triple.

The authors used small, representative instances for training and more challenging instances for evaluation. They also mention using the "advanced PUP encoding" from Dodaro et al. (2016) for comparison.

Key Insights and Ideas

  • Symmetries are not just structural: The paper highlights that for optimization problems, symmetries are not solely about structural equivalence but also about preserving optimization values. Simply breaking all structural symmetries can lead to discarding optimal solutions.
  • Auxiliary rules are key: The introduction of auxiliary atoms and rules ($O_p$) is a critical step. These rules effectively "tag" atoms based on their role in weak constraints, allowing symmetry detection tools to distinguish between structurally similar but optimization-wise different solutions.
  • Preserving optimality is paramount: The modified learning algorithm (Algorithm 1) explicitly aims to identify optimal solutions as positive examples, a crucial departure from previous methods that might treat any representative solution as positive.
  • ILP as a powerful tool for optimization: The work demonstrates that ILP can be effectively adapted to learn constraints that respect optimization objectives, going beyond its traditional use for satisfiability problems.

Key Results

  • The proposed method significantly improves the performance of ASP solvers on optimization problems by learning effective first-order symmetry-breaking constraints.
  • Experiments show that the learned constraints prune symmetries of optimization problems, leading to speedups in finding optimal solutions.
  • For the Partner Units Problem (PUP), the learned constraints helped CLINGO prove optimality for all instances of the "double" and "doublev" families, whereas the baseline encoding struggled significantly.
  • The learning performance (time to learn constraints) was comparable between decision and optimization versions of the benchmark problems, suggesting the overhead of handling optimization is manageable.

Limitations and Future Work

  • Scalability for very large instances: While scalable versions of the learning algorithm are discussed, exhaustively exploring all solutions for training can still be challenging for extremely large problem instances.
  • Instance-specific symmetry breaking: The authors suggest exploring alternative instance-specific approaches for constructing ground SBCs and their lifting to first-order constraints.
  • Integration with other tools: Future work may involve evaluating the approach with tools like BREAKID, which handles weight rules and minimization statements, potentially uncovering more symmetries.
  • Beyond weak constraints: The paper mentions that other forms of optimization statements (e.g., ASO programs, LPODs) could potentially be addressed with similar techniques.

Summary updated

BibTeX
@inproceedings{tarzariol2023learning,
  author = {Alice Tarzariol and Martin Gebser and Konstantin Schekotihin and Mark Law},
  title = {{Learning to Break Symmetries for Efficient Optimization in Answer Set Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25804},
}
Figure