A Model-Oriented Approach for Lifting Symmetry-Breaking Constraints in Answer Set Programming

Alice TarzariolIJCAI 2022 · DOI

TL;DR

This paper introduces a novel, model-oriented approach to automatically generate "symmetry-breaking constraints" for Answer Set Programming (ASP) problems. By leveraging Inductive Logic Programming (ILP), the authors aim to create generalizable constraints that significantly speed up solving complex combinatorial problems, overcoming limitations of existing instance-specific methods.

What Problem Does This Paper Address?

Solving complex combinatorial problems with Answer Set Programming (ASP) can be computationally challenging, especially when the number of potential solutions explodes. Many of these solutions are "symmetric," meaning they are essentially the same problem solution just permuted. Manually identifying and encoding constraints to break these symmetries (Symmetry-Breaking Constraints or SBCs) is a difficult and time-consuming task for programmers. Existing automated approaches are often "instance-specific," meaning they generate SBCs for a single problem instance and these constraints don't transfer to other instances or more advanced encodings. This leads to limitations like non-transferability, difficulty in interpretation, and potential redundancy. The authors aim to bridge this gap by developing a "model-oriented" approach that learns general, first-order SBCs applicable across a distribution of problem instances.

Methods

The core of the proposed method is a model-oriented approach that uses Inductive Logic Programming (ILP) to learn first-order symmetry-breaking constraints for ASP. Specifically, they leverage the ILASP system, an ILP system designed for learning Answer Set Programs.

The process involves:

  1. Instance Analysis: Using an existing tool called SBASS, they compute ground SBCs for a set of small, satisfiable, and representative problem instances from a target ASP problem.
  2. ILP Task Formulation: This information (ground SBCs and problem characteristics) is then encoded as an ILP task.
  3. Learning First-Order Constraints: ILASP learns first-order constraints that effectively remove symmetric solutions while ensuring that the original problem instances remain satisfiable.

The authors also discuss extending this framework iteratively (RG 2) to speed up learning and applying it to more complex problems with multi-dimensional predicates (RG 3).

Datasets

Not discussed in the paper. The paper focuses on a general framework and its application to "simple ASP programs with common characteristics" and "advanced combinatorial problems," rather than specific, named datasets.

Key Insights and Ideas

  • Model-Oriented SBCs are Crucial: The paper highlights the significant limitations of instance-specific SBCs and argues for the necessity of model-oriented approaches that learn generalizable constraints.
  • ILP as a Powerful Tool for Constraint Generation: Inductive Logic Programming, particularly systems like ILASP, offers a promising avenue for automatically discovering and formulating complex, first-order symmetry-breaking constraints.
  • Generalization is Key: The goal is to learn constraints that are not tied to a single instance but can be applied to a distribution of instances, leading to more robust and efficient solvers.
  • Iterative Learning for Efficiency: The idea of applying the learning framework iteratively (RG 2) suggests a path towards more efficient constraint generation, breaking down complex learning tasks into smaller, manageable sub-tasks.

Key Results

The paper describes research goals and contributions rather than presenting definitive quantitative results.

  • RG 1 Contribution: A framework for learning first-order constraints that speed up solving for a distribution of ASP instances has been developed and its application to simple ASP programs was published in 2021.
  • RG 2 Contribution: Techniques for iteratively learning constraints have been outlined and formalized.
  • RG 3 Contribution: Work is underway to extend the framework to advanced combinatorial problems, which was submitted for publication in early 2022.

Limitations and Future Work

  • Limitations of Current Framework (RG 1): The current framework is primarily applied to simple ASP programs with common characteristics. Its applicability to more complex problems with multi-dimensional predicates is still under investigation (RG 3).
  • Parameter Selection (RG 4): Automating parameter selection for the learning framework is an ongoing research goal. This is crucial for simplifying the framework's usage and ensuring correct and performant constraint generation.
  • Optimization Problems (RG 5): Extending the framework to handle optimization problems, which often involve weak constraints not supported by SBASS, is a significant future direction. This is particularly important as symmetry breaking is critical for the performance of optimization solvers.
  • User Experience: The authors aim to develop a tool that helps non-expert ASP users improve their encodings by learning efficient constraints tailored to their problem instances.

Summary updated

BibTeX
@inproceedings{tarzariol2022model,
  author = {Alice Tarzariol},
  title = {{A Model-Oriented Approach for Lifting Symmetry-Breaking Constraints in Answer Set Programming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/840},
}
Figure