# Efficient lifting of symmetry breaking constraints for complex combinatorial problems

arXiv: https://arxiv.org/abs/2205.07129 · HTML: https://mlsanity.com/paper/2205.07129/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 36 references that are in the map.
- First posted on arXiv 14 May 2022.

## Builds on (most cited first, 10 of 10)

- [Inductive logic programming at 30: a new introduction](https://mlsanity.com/paper/2008.07912/) (2020)
- [Learning programs by learning from failures](https://mlsanity.com/paper/2005.02259/) (2020)
- [Turning 30: New Ideas in Inductive Logic Programming](https://mlsanity.com/paper/2002.11002/) (2020)
- [The ILASP system for Inductive Learning of Answer Set Programs](https://mlsanity.com/paper/2005.00904/) (2020)
- [Inductive Learning of Answer Set Programs from Noisy Examples](https://mlsanity.com/paper/1808.08441/) (2018)
- [claspfolio 2: Advances in Algorithm Selection for Answer Set Programming](https://mlsanity.com/paper/1405.1520/) (2014)
- [Combining Answer Set Programming and Domain Heuristics for Solving Hard Industrial Problems (Application Paper)](https://mlsanity.com/paper/1608.00730/) (2016)
- [Conflict-driven Inductive Logic Programming](https://mlsanity.com/paper/2101.00058/) (2020)
- [On Local Domain Symmetry for Model Expansion](https://mlsanity.com/paper/1608.02688/) (2016)
- [Lifting Symmetry Breaking Constraints with Inductive Logic Programming](https://mlsanity.com/paper/2112.11806/) (2021)

## Built on by (most cited first, 2 of 2)

- [A Model-Oriented Approach for Lifting Symmetries in Answer Set Programming](https://mlsanity.com/paper/2208.03095/) (2022)
- [Streamliners for Answer Set Programming](https://mlsanity.com/paper/2604.19251/) (2026)

## Abstract (arXiv)

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.