Publications

Info

This page lists all scientific outputs from our project. All publications will be available for download as soon as they are released. Our first results are currently in preparation and will appear here soon.

Previous publications

Lifting symmetry breaking constraints with inductive logic programming
  • Authors: Alice Tarzariol, Martin Gebser, Konstantin Schekotihin
  • Journal: Machine Learning
  • Date: Apr 19, 2022
  • Abstract Efficient omission of symmetric solution candidates is essential for combinatorial problem-solving. Most of the existing approaches are instance-specific and focus on the automatic computation of Symmetry Breaking Constraints (SBCs) for each given problem instance. However, the application of such approaches to large-scale instances or advanced problem encodings might be problematic since the computed SBCs are propositional and, therefore, can neither be meaningfully interpreted nor transferred to other instances. As a result, a time-consuming recomputation of SBCs must be done before every invocation of a solver. To overcome these limitations, we introduce a new model-oriented approach for Answer Set Programming that lifts the SBCs of small problem instances into a set of interpretable first-order constraints using the Inductive Logic Programming paradigm. Experiments demonstrate the ability of our framework to learn general constraints from instance-specific SBCs for a collection of combinatorial problems. The obtained results indicate that our approach significantly outperforms a state-of-the-art instance-specific method as well as the direct application of a solver.
  • Access: [PDF]
Learning to break symmetries for efficient optimization in answer set programming
  • Authors: Alice Tarzariol, Martin Gebser, Konstantin Schekotihin, Mark Law
  • Conference: Proceedings of the AAAI Conference on Artificial Intelligence
  • Date: Jun 26, 2023
  • Abstract The ability to efficiently solve hard combinatorial optimization problems is a key prerequisite to various applications of declarative programming paradigms. Symmetries in solution candidates pose a significant challenge to modern optimization algorithms since the enumeration of such candidates might substantially reduce their performance. This paper proposes a novel approach using Inductive Logic Programming (ILP) to lift symmetry-breaking constraints for optimization problems modeled in Answer Set Programming (ASP). Given an ASP encoding with optimization statements and a set of small representative instances, our method augments ground ASP programs with auxiliary normal rules enabling the identification of symmetries using existing tools, like SBASS. Then, the obtained symmetries are lifted to first-order constraints with ILP. We prove the correctness of our method and evaluate it on real-world optimization problems from the domain of automated configuration. Our experiments show significant improvements of optimization performance due to the learned first-order constraints.
  • Access: [PDF]
Efficient lifting of symmetry breaking constraints for complex combinatorial problems
  • Authors: Alice Tarzariol, Martin Gebser, Mark Law, Konstantin Schekotihin
  • Journal: Theory and Practice of Logic Programming
  • Date: May 14, 2022
  • Abstract Many industrial applications require finding solutions to challenging combinatorial problems. Efficient elimination of symmetric solution candidates is one of the key enablers for high-performance solving. However, existing model-based approaches for symmetry breaking are limited to problems for which a set of representative and easily solvable instances is available, which is often not the case in practical applications. This work extends the learning framework and implementation of a model-based approach for Answer Set Programming to overcome these limitations and address challenging problems, such as the Partner Units Problem. In particular, we incorporate a new conflict analysis algorithm in the Inductive Logic Programming system ILASP, redefine the learning task, and suggest a new example generation method to scale up the approach. The experiments conducted for different kinds of Partner Units Problem instances demonstrate the applicability of our approach and the computational benefits due to the first-order constraints learned.
  • Access: [PDF]