# A Model-Oriented Approach for Lifting Symmetries in Answer Set
Programming††thanks: This PhD work is conducted under the supervision of
professors Martin Gebser and Konstantin Schekotihin.

Alice Tarzariol Alpen-Adria-Universität
Klagenfurt, Austria<EMAIL_ADDRESS>
###### Abstract

When solving combinatorial problems, pruning symmetric solution candidates
from the search space is essential. 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 a form of machine learning called Inductive Logic Programming. After
targeting simple combinatorial problems, we aim to extend our method to be
applied also for advanced decision and optimization problems.

##  1 Introduction and Problem Description

A common approach for solving combinatorial problems is modelling them using
declarative programming paradigms, e.g., Answer Set Programming (ASP) [15, 16,
3]. In general, defining such models is relatively simple, and the obtained
encodings are easy to understand. However, although correct, a trivial
encoding might become useless because of its performance when solving non-
trivial instances. Indeed, the solving phase turns infeasible when the size of
input instances and, correspondingly, the number of possible solution
candidates start to grow [11]. In many cases, these candidates are symmetric,
i.e., one candidate can easily be obtained from another by renaming constants.
Therefore, the ability to encode Symmetry Breaking Constraints (SBCs) in a
program becomes an essential skill for programmers as they prune a consistent
part of the search space. Nevertheless, identifying symmetric solutions and
formulating constraints that remove only them might be a time-consuming and
challenging task. As a result, various tools emerged for avoiding the
computation of symmetric solutions. A popular approach consists in
automatically detecting and introducing a set of SBCs using properties of
permutation groups [25]. The system sbass [12] implements this type of
approach for ground ASP programs.

Unfortunately, the computational advantages derived from sbass or, more
generally, from any _instance-specific_ symmetry breaking approach, do not
carry forward to large-scale instances or advanced encodings. Indeed,
instance-specific approaches often require as much time as it takes to solve
the original problem. Moreover, ground SBCs generated approaches are  _(i)_
not transferable, since the knowledge obtained is limited to a single
instance;  _(ii)_ usually hard to interpret and comprehend because they are
not expressed with a symbolic representation;  _(iii)_ derived from
permutation group generators, whose computation is itself a combinatorial
problem; and  _(iv)_ often redundant and might result in a degradation of the
solving performance.  In particular, when solving instances sharing similar
characteristics, the identified symmetries follow the same structure for the
whole set. Thus, the instance-specific approaches require extra computation
time to identify the same symmetries applied to every single instance.
Assuming we consider a combinatorial ASP program and a distribution of similar
problem instances, in our work, we aim to overcome the limitations of
instance-specific approaches by lifting ground symmetries using a form of
machine learning called Inductive Logic Programming (ILP) [7]. The resulting
first-order constraints can be applied to any instance drawn from the
considered distribution, and they should speed up the identification of
satisfiable/unsatisfiable instances.

##  2 Background and Existing Literature

In this section, we will briefly introduce the concepts considered in our
work, i.e., Answer Set Programming, Inductive Logic Programming and Symmetry
Breaking techniques.

###  2.1 Answer Set Programming

ASP is a declarative programming paradigm that applies non-monotonic reasoning
and relies on the stable model semantics [17]. Over the past decades, it has
attracted considerable interest thanks to its elegant syntax, expressiveness,
and efficient system implementations. It showed promising results in numerous
domains, including industrial, robotics, or biomedical applications [13].

#### Syntax.

An ASP program $P$ is a set of rules $r$ of the form:

$a_{\\_}0\leftarrow
a_{\\_}1,\dots,a_{\\_}m,\mathit{not}\,a_{\\_}{m+1},\dots,\mathit{not}\,a_{\\_}n$

where $\mathit{not}$ stands for default negation and $a_{\\_}i$, for $0\leq
i\leq n$, are atoms. An atom is an expression of the form $p(\overline{t})$,
where $p$ is a predicate, $\overline{t}$ is a possibly empty vector of terms,
and the predicate $\bot$ (with an empty vector of terms) represents the
constant false. Each term $t$ in $\overline{t}$ is either a variable or a
constant. A literal $l$ is an atom $a_{\\_}i$ (positive) or its negation
$\mathit{not}\,a_{\\_}i$ (negative). The atom $a_{\\_}0$ is the head of a rule
$r$, denoted by $H(r)=a_{\\_}0$, and the body of $r$ includes the positive or
negative, respectively, body atoms $B^{+}(r)=\\{a_{\\_}1,\dots,a_{\\_}m\\}$
and $B^{-}(r)=\\{a_{\\_}{m+1},\dots,a_{\\_}n\\}$. A rule $r$ is called a fact
if $B^{+}(r)\cup B^{-}(r)=\emptyset$, and a constraint if $H(r)=\bot$.

#### Semantics.

The semantics of an ASP program $P$ is given in terms of its ground
instantiation $P_{\\_}{\mathit{grd}}$, which is obtained by replacing each
rule $r\in\nolinebreak P$ with its instances obtained by substituting the
variables in $r$ by constants occurring in $P$. Then, an interpretation
$\mathcal{I}$ is a set of (true) ground atoms occurring in
$P_{\\_}{\mathit{grd}}$ that does not contain $\bot$. An interpretation
$\mathcal{I}$ satisfies a rule $r\in P_{\\_}{\mathit{grd}}$ if
$B^{+}(r)\subseteq\mathcal{I}$ and $B^{-}(r)\cap\mathcal{I}=\emptyset$ imply
$H(r)\in\mathcal{I}$, and $\mathcal{I}$ is a model of $P$ if it satisfies all
rules $r\in P_{\\_}{\mathit{grd}}$. A model $\mathcal{I}$ of $P$ is stable if
it is a subset-minimal model of the reduct $\\{H(r)\leftarrow B^{+}(r)\mid
r\in P_{\\_}{\mathit{grd}},B^{-}(r)\cap\mathcal{I}=\emptyset\\}$, and we
denote the set of all stable models, also called answer sets, of $P$ by
$\mathit{AS}(P)$.

###  2.2 Inductive Logic Programming

ILP is a form of machine learning whose goal is to learn a logic program that
explains a set of observations in the context of some pre-existing knowledge.
The most expressive ILP system for ASP is _Inductive Learning of Answer Set
Programs_ (ilasp) [21, 22], which can be used to solve a variety of ILP tasks.
A learning task $\langle B,E^{+},E^{-},H_{\\_}M\rangle$ is defined by four
elements: a background knowledge $B$, a set of positive and negative examples,
respectively $E^{+}$ and $E^{-}$, and lastly a hypothesis space $H_{\\_}M$,
which defines the rules that can be learned. Each example $e\in E^{+}\cup
E^{-}$ is a pair $\langle e_{\\_}{\mathit{pi}},C\rangle$ called Context
Dependent Partial Interpretation, where  _(i)_ $e_{\\_}{\mathit{pi}}$is a
Partial Interpretation defined as pair of sets of atoms $\langle T,F\rangle$,
called inclusions ($T$) and exclusions ($F$), respectively, and  _(ii)_ $C$is
an ASP program defining the context of $e_{\\_}{\mathit{pi}}$.  Given a
(total) interpretation $\mathcal{I}$ of a program $P$ and a partial
interpretation $e_{\\_}{\mathit{pi}}$, we say that $\mathcal{I}$ extends
$e_{\\_}{\mathit{pi}}$ if $T\subseteq\mathcal{I}$ and
$F\cap\mathcal{I}=\emptyset$. Given an ASP program $P$, an interpretation
$\mathcal{I}$, and an example $e=\langle e_{\\_}{\mathit{pi}},C\rangle$, we
say that $\mathcal{I}$ is an accepting answer set of $e$ with respect to $P$
if $\mathcal{I}\in\mathit{AS}(P\cup C)$ such that $\mathcal{I}$ extends
$e_{\\_}{\mathit{pi}}$.

Each hypothesis $H\subseteq H_{\\_}M$ learned by ilasp must respect the
following criteria:  _(i)_ for each positive example $e\in E^{+}$, there is
some accepting answer set of $e$ with respect to $B\cup H$; and  _(ii)_ for
any negative example $e\in E^{-}$, there is no accepting answer set of $e$
with respect to $B\cup H$.  If multiple hypotheses satisfy the conditions, the
system returns one of those with the lowest cost. By default, the cost
$c_{\\_}{r}$ of each rule $r\in H_{\\_}M$ corresponds to its number of
literals [19]; however, the user can define a custom scoring function for
defining the rule costs. Ilasp allows to define learning tasks with noisy
examples [20]. With this setting, if an example $e$ is not covered, i.e.,
there is an accepting answer set for $e$ if it is negative, or none if $e$ is
positive, the corresponding weight is counted as a penalty. If no dedicated
weight is specified, the example’s weight is infinite, thus forcing the system
to cover the example. Therefore, the learning task becomes an optimization
problem with two goals: minimize the cost of $H$ and minimize the total
penalties for the uncovered examples. In our work, we use the most recent
version of ilasp (v4.1.2), which implements the search approach Conflict
Driven ILP [18].

###  2.3 Symmetry Breaking

Modern symmetry breaking approaches can be split into two families: _instance-
specific_ and _model-oriented_ approaches [25, 31]. The former identify
symmetries for a particular instance at hand by obtaining a ground program,
computing ground SBCs, composing a new extended program, and solving it [24,
5, 12]. The system sbass [12] implements this type of approach for ground ASP
programs. As mentioned in Section 1, when applied to large-scale instances or
advanced encodings, the _instance-specific_ symmetry breaking approaches may
struggle to compute the symmetries in a reasonable time, or the resulting SBCs
are redundant, leading to more drawbacks than benefits for the solver.
Moreover, the ground SBCs are often difficult to understand as they are not
expressed in symbolic representation; e.g., the SBCs produced by sbass are
represented in smodels format [26].

In contrast, _model-oriented_ approaches aim to find general SBCs that depend
less on a particular instance. The method presented in [10] uses local domain
symmetries of a given first-order theory. SBCs are generated by identifying
argument positions in atoms of a formula that comprise object variables
defined over the same subset of a domain given in the input. As a result, the
computation of lexicographical SBCs is very fast. However, the method
considers each first-order formula separately and cannot reliably remove
symmetric solutions, as it requires the analysis of several formulas at once.
The method of [23] computes SBCs by generating small instances of parametrized
constraint programs, and then finds candidate symmetries using saucy [4, 9] –
a graph automorphism detection tool. Next, the algorithm removes all candidate
symmetries that are valid only for some of the generated examples as well as
those that cannot be proven to be parametrized symmetries using heuristic
graph-based techniques. This approach can be seen as a simplified learning
procedure that utilizes only negative examples represented by the generated
SBCs.

##  3 Current Research

This section describes the research goals targeted for my PhD, and the current
state of my work.

###  3.1 Goal of the Research

To the best of our knowledge, currently there are no _model-oriented_ systems
that lift ground SBCs for ASP programs. Therefore, we aim to introduce a novel
_model-oriented_ method that generalizes the process of discarding redundant
solution candidates for ASP instances of a target domain using ILP. More
precisely, we identify and lift SBCs of small problem-instances, obtaining a
set of interpretable first-order constraints. Such constraints cut the search
space while preserving the satisfiability of a problem for the considered
instance distribution, which improves the solving performance, especially in
the case of unsatisfiability. After targeting simple combinatorial problems,
we aim to extend our method to be applied also for advanced decision and
optimization problems.

The research goals of this work are the following:

  * RG 1

Given an ASP combinatorial program and a target instances distribution, define
a learning framework capable of obtaining first-order constraints that speed
up the solving of satisfiable and unsatisfiable instances.

  * RG 2

Develop an approach capable of applying the learning framework iteratively.

  * RG 3

Investigate how the framework can be extended to enable learning first-order
constraints for advanced combinatorial problems.

  * RG 4

Design and implement systems that automate parameter selection for the
framework for guiding the learning of first-order constraints that speed up
solving.

  * RG 5

Extend the expressiveness of the learning framework to analyse the symmetries
on optimization problems.

For the research goal RG 1, we assume that the instances analyzed for a given
ASP combinatorial problem $P$ follow a specific distribution. Moreover, we can
easily provide a set of simple instances (i.e., such that the total number of
solutions can be managed by sbass, clingo111In our work, to find the solutions
of ASP programs, we use the system clingo, consisting of the grounding and
solving components gringo and clasp. and ilasp) that entail the symmetries of
the whole target distribution. Our framework defines the set of examples of an
ILP task such that ilasp learns first-order constraints that remove symmetric
solutions while preserving the satisfiability of the instances in the
considered distribution. To do so, the framework relies on sbass to compute
the SBCs of a set of small, satisfiable, and representative problem-instances,
identified with $S$. More precisely, for each instance $i\in S$, we find its
symmetries expressed as a set of irredundant generators, $\mathit{IG(i)}$, and
we enumerate the set of its answer sets, $AS(i)$. Then, for each
interpretation $\mathcal{I}\in AS(i)$, we define an example where
$\mathit{IG(i)}\cap\mathcal{I}$ and $\mathit{IG(i)}\setminus\mathcal{I}$ are
the inclusions and exclusions of a partial interpretation and using $i$ as
context. If $\mathcal{I}$ is dominated, i.e., $\mathcal{I}$ can be mapped to a
lexicographically smaller, symmetric answer set by means of some irredundant
generator in $\mathit{IG(i)}$, the example is labelled as negative, otherwise,
positive. Together with $S$, we use another set of instances $\mathit{Gen}$,
where each $g\in\mathit{Gen}$ defines a single positive example with empty
inclusions and exclusions and $g$ as context. These examples guarantee that
the learned constraints generalize for the target distribution since they
force the constraints to preserve some solution for each $g\in\mathit{Gen}$.
The two sets of instances, $S$ and $Gen$, and the language bias for the ILP
task are defined by the user, while $P$ is used as background knowledge. After
the learning phase, a validation set of satisfiable instances, $V$, is used to
check whether the learn constraints in $ABK$ are correct. If there is a
satisfiable instance $v\in V$ for which no solution is found, we discard the
learned constraints and add $v$ in $Gen$. Subsequently, we rerun our framework
and repeat the procedure until all the instances in the validation set are
satisfiable.

The research goal RG 2 consists of identifying techniques that can speed up
the learning phase for the tasks analysed in RG 1 as the learning time
represent a critical aspect on ILP [8]. To do so, we define a procedure that
applies our framework iteratively to learn the first-order constraints
incrementally. More precisely, we outline a criterion for splitting the
framework inputs to create sub-learning tasks. This approach speeds up the
computation of first-order constraints, especially when the program contains
symmetries independent from each others. To do so, we introduce an auxiliary
ASP file called Active Background Knowledge or $ABK$, containing the
constraints learned so far. By including $ABK$ in the background knowledge, we
can rerun our framework taking into account the constraints previously
learned.

The current definition of our framework yields a number of examples
proportional to the number of solutions for each problem-instance in $S$.
Therefore, if it gets difficult to compute all the solutions for an instance
in $S$ to analyze, the resulting formulation of the ILP task to learn
constraints can become prohibitive. The research goal RG 3 consists of
overcoming the limitations of the current framework, in order to apply it to
advanced combinatorial problems. With the term “advanced”, we refer to
problems whose solutions rely on atoms of multi-dimensional instead of just
unary predicates, so that there might be no trivial instances to analyse. An
example of this kind of problems is the Partner Units Problem (PUP) [2, 30],
which is an abstract representation of configuration problems occurring in
railway safety or building security systems. Considering the smallest PUP
instance representing a class of building security systems named double by
[2], clingo finds $145368$ solutions, $98.9\%$ of which can be identified as
symmetric by sbass (for instance, by renaming the units of a solution). Thus,
the enumeration of symmetries for PUP instances is problematic, even for the
smallest and simplest ones. To overcome this problem, we need to revise the
framework’s approach such that it manages to cope with any number of solutions
of the analyzed instances, for example, by sampling a subset of answer sets.
To be effective, the sample size must be small while containing an adequate
number of positive and negative examples. Besides, two further limitations
need to be addressed concerning ilasp’s searching technique. The former is the
inefficiency of the default ilasp’s conflict analysis techniques222A key
component of Conflict-Driven ILP. when applied to positive examples producing
many solutions (i.e., the examples generated from the PUP instances in $Gen$).
The second issues concerns the optimal criterion for the learned hypothesis,
which considers only the length of the constraints and not the nature of the
predicates. To overcome both issues, we aim to devise a specific conflict
analysis technique that exploit the nature of the learning task (namely,
constraints learning) and a custom scoring function for ilasp that provides
further information for learning efficient333Namely, constraints with a
limited number of variables and, possibly, containing some predicates that are
simplified during grounding. constraints.

For the research goal RG 4, we aim to identify appropriate inputs to our
framework automatically. So far the inputs must be chosen by the user,
however, we would like to provide guidelines or automate the process of
selecting the framework inputs. First, the selection method of our framework
needs to assess the properties of candidate inputs. Then, the method should
determine parameters leading to correct and performant first-order
constraints. That is, it aims to find constraints preserving at least one
solution for satisfiable instances and cutting down the solving time for
unsatisfiable instances.

Lastly, the research goal RG 5 is to extend the applicability of our framework
to optimization problems. The tool sbass, used in our framework, can analyse
most of the ASP rules as normal rules, choice rules, aggregates, and hard
constraints; however, it does not support weak constraints. Therefore, we aim
to define a reduction from programs with weak constraints to an equivalent
representation that can be processed by sbass. More specifically, we aim to
introduce new (normal) rules that respect the symmetries of the optimisation
rules. As a consequence, when running sbass on the extended program, we get a
finer partition of the solutions. Namely, it could be that two solutions,
which were considered symmetric from the analysis of the original program, can
be identified as non-symmetric after the introduction of the new rules.

###  3.2 Results Accomplished

We devised and implemented the learning framework of RG 1 and a rough idea of
RG 2 in a conference paper [28]; subsequently, we formalised the method to
split the learning task in a journal paper [29]. We applied the framework to
simple ASP programs, namely, the pigeon-hole problem and two its extensions
that consider also the assignments of colors and owners. Moreover, we tested
the house-configuration problem [14]. For all the addressed problems, we
suggested some guidelines to define the framework inputs, $S$, $Gen$,
$H_{\\_}M$, and $ABK$. Table 3.2 contains the solving times for the house-
configuration problem; the satisfiable instances are shown in grey rows, while
the white rows contain unsatisfiable instances. The column base refers to
clingo (v5.5.0) run on the original encoding, while abk reports results for
the original encoding augmented with first-order constraints learned with our
framework. The time required by sbass to compute ground SBCs is given in the
corresponding column, and claspπ provides the solving time obtained with these
ground SBCs. Therefore, the total time required for the online usage of sbass
is the sum of base and claspπ. Runs that did not finish within the time limit
of 900 seconds are indicated by TO entries.

The running times in the table show the limits of sbass both in the pre-
solving phase, when computing the symmetries (obtaining a timeout for all the
satisfiable instances), and when solving a program extended with redundant
constraints (the performance degradation is visible with the instance
p5-c6-t13). The base encoding is quicker than sbass+claspπ to solve
satisfiable instances, although it takes considerably longer for unsatisfiable
ones. On the other hand, the first-order constraints learned with our
framework helped the search for satisfiable and, especially, unsatisfiable
instances. Similar results have also been observed for the pigeon-hole
problems analysed. The repository containing the implementation and complete
experiments can be found at the following link:
https://github.com/prosysscience/Symmetry_Breaking_with_ILP/tree/extended

file=HouseConfiguration.csv, head to column names, before reading=,
tabular=lrrrr, table head= ABK BASE SBASS $\mathbf{CLASP^{\pi}}$
, command= , table foot=

Table 1: Runtime in seconds for house-configuration problem.

We addressed the extension mentioned in RG 3 in a paper presented at ICLP 2022
[27]. In this paper, we revised several parts of our framework in order to
target PUP instances supplied by [2], studying the double, doublev, and triple
instance collections. Instances of the same type represent buildings of
similar topology with scaling parameters that follow a common distribution.
Although the benchmark instances are synthetic, they represent a relevant
configuration problem concerning safety and security issues in public
buildings, like administration offices or museums. In addition, the scalable
synthetic benchmarks are easy to generate and analyze.

Table 3.2 contains the solving time for the PUP instances in double, and the
table follows the same structure as the previous, but with a timeout of 600
seconds. Moreover, it also considers the computational time obtained by
running clingo on the advanced encoding symm444The encoding used for symm is
taken from the paper [11], where it is called ENC2. From the same paper, we
also take the basic encoding ENC1 and use it as base. which incorporates hand-
crafted static symmetry breaking as well as an ordered representation [6] of
assigned units. From the table, we can observe that symm leads to more robust
clingo performance than the simpler base encoding, and the ground SBCs
computed from sbass (obtained by summing the time in sbass with claspπ).
Moreover, when comparing symm to abk, we observe further significant
performance improvements thanks to our approach, particularly on the
unsatisfiable instances. That is, the learned $\mathit{ABK}$ enables clingo to
solve the considered PUP instances and efficiently prunes the search space,
which must be fully explored in case of unsatisfiability. Similar results have
been observed also for the other two type of instances, doublev and triple.
The repository containing the implementation and complete experiments can be
found at the following link:
https://github.com/prosysscience/Symmetry_Breaking_with_ILP/tree/pup

file= PUPdouble.csv, head to column names, before reading=, tabular=lrrrrr,
table head= ABK SYMM BASE SBASS $\mathbf{CLASP^{\pi}}$
, command= , table foot=

Table 2: Runtimes for PUP double

###  3.3 Open Issues and Expected Achievements

The research goals that we still need to tackle are RG 4 and RG 5. For the
former, we would like to help the user on deciding the elements in $S$ and
$Gen$, and automatically identify a set of constraints which performs
relatively fast, while preserving the satisfiability of the target instances.
A more ambitious target that can be developed for this research goal is the
identification of predicates to use in the language bias to learn the
constraints. Moreover, from the experiments with the PUP instances, we
observed that the labelling instance impacted the symmetries identified by
sbass. Thus, we hope to introduce automatic (re-)labeling schemes for
constants appearing in instances to exploit common problem structure in a less
input-specific way. For RG 5 we aim to extend the applicability of our
framework to programs containing weak constraints. Targeting optimization
problems can lead to relevant results as optimization involves solving
unsatisfiable subproblem(s) on attempting (and failing) to improve an optimal
answer set, where symmetry breaking is particularly crucial for the
performance.

## References

  * [1]
  * [2] M. Aschinger, C. Drescher, G. Friedrich, G. Gottlob, P. Jeavons, A. Ryabokon & E. Thorstensen (2011): _Optimization Methods for the Partner Units Problem_.  In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science 6697, Springer, pp. 4–19, 10.1007/978-3-642-21311-34.
  * [3] G. Brewka, T. Eiter & M. Truszczyński (2011): _Answer Set Programming at a Glance_.  Communications of the ACM 54(12), pp. 92–103, 10.1145/2043174.2043195.
  * [4] P. Codenotti, H. Katebi, K. Sakallah & I. Markov (2013): _Conflict Analysis and Branching Heuristics in the Search for Graph Automorphisms_.  In: IEEE 25th International Conference on Tools with Artificial Intelligence, IEEE Computer Society, pp. 907–914, 10.1109/ICTAI.2013.139.
  * [5] D. Cohen, P. Jeavons, C. Jefferson, K. Petrie & B. Smith (2006): _Symmetry Definitions for Constraint Satisfaction Problems_.  Constraints 11(2-3), pp. 115–137, 10.1007/s10601-006-8059-8.
  * [6] J. Crawford & A. Baker (1994): _Experimental Results on the Application of Satisfiability Algorithms to Scheduling Problems_.  In: Proceedings of the twelfth national conference on Artificial Intelligence, pp. 1092–1097.
  * [7] A. Cropper, S. Dumančić & S. Muggleton (2020): _Turning 30: New Ideas in Inductive Logic Programming_.  In C. Bessiere, editor: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI’20), ijcai.org, pp. 4833–4839, 10.24963/ijcai.2020/673.
  * [8] A. Cropper & S. Dumančić (2020): _Inductive Logic Programming at 30: A New Introduction_.  https://arxiv.org/abs/2008.07912.  arXiv:https://arxiv.org/abs/2008.07912.
  * [9] P. Darga, H. Katebi, M. Liffiton, I. Markov & K. Sakallah (2004): _Saucy_.  http://vlsicad.eecs.umich.edu/BK/SAUCY/.
  * [10] J. Devriendt, B. Bogaerts, M. Bruynooghe & M. Denecker (2016): _On Local Domain Symmetry for Model Expansion_.  Theory and Practice of Logic Programming 16(5-6), pp. 636–652, 10.1017/S1471068416000508.
  * [11] C. Dodaro, P. Gasteiger, N. Leone, B. Musitsch, F. Ricca & K. Schekotihin (2016): _Combining Answer Set Programming and Domain Heuristics for Solving Hard Industrial Problems_.  Theory and Practice of Logic Programming 16(5-6), pp. 653–669, 10.1017/S1471068416000284.
  * [12] C. Drescher, O. Tifrea & T. Walsh (2011): _Symmetry-breaking Answer Set Solving_.  AI Communications 24(2), pp. 177–194, 10.3233/AIC-2011-0495.
  * [13] E. Erdem, M. Gelfond & N. Leone (2016): _Applications of ASP_.  AI Magazine 37(3), pp. 53–68, 10.1609/aimag.v37i3.2678.
  * [14] G. Friedrich, A. Ryabokon, A. Falkner, A. Haselböck, G. Schenner & H. Schreiner (2011): _(Re)configuration using Answer Set Programming_.  In: IJCAI 2011 Workshop on Configuration, CEUR-WS.org, pp. 17–24.
  * [15] M. Gebser, R. Kaminski, B. Kaufmann & T. Schaub (2012): _Answer Set Solving in Practice_.  Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan and Claypool Publishers, 10.2200/S00457ED1V01Y201211AIM019.
  * [16] M. Gelfond & V. Lifschitz (1988): _The Stable Model Semantics for Logic Programming_.  In R. Kowalski & K. Bowen, editors: Proceedings of the Fifth International Conference and Symposium of Logic Programming (ICLP’88), MIT Press, pp. 1070–1080.
  * [17] M. Gelfond & V. Lifschitz (1991): _Classical Negation in Logic Programs and Disjunctive Databases_.  New Generation Computing 9, pp. 365–385, 10.1007/BF03037169.
  * [18] M. Law (2022): _Conflict-driven Inductive Logic Programming_.  Theory and Practice of Logic Programming, pp. 1–28, 10.1017/S1471068422000011.
  * [19] M. Law, A. Russo & K. Broda (2014): _Inductive Learning of Answer Set Programs_.  In E. Fermé & J. Leite, editors: Proceedings of the Fourteenth European Conference on Logics in Artificial Intelligence (JELIA’14), Lecture Notes in Artificial Intelligence 8761, Springer-Verlag, pp. 311–325, 10.1007/978-3-319-11558-022.
  * [20] M. Law, A. Russo & K. Broda (2018): _Inductive Learning of Answer Set Programs from Noisy Examples_.  Advances in Cognitive Systems 7, pp. 57–76.
  * [21] M. Law, A. Russo & K. Broda (2020): _The ILASP System for Inductive Learning of Answer Set Programs_.  The Association for Logic Programming Newsletter.  Available at https://www.cs.nmsu.edu/ALP/2020/04/the-ilasp-system-for-inductive-learning-of-answer-set-programs/.
  * [22] M. Law, A. Russo & K. Broda (2021): _ILASP_.  www.ilasp.com.
  * [23] C. Mears, M. García de la Banda, M. Wallace & B. Demoen (2008): _A Novel Approach for Detecting Symmetries in CSP Models_.  In L. Perron & M. Trick, editors: Proceedings of the Fifth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR’08), Lecture Notes in Computer Science 5015, Springer-Verlag, pp. 158–172, 10.1007/978-3-540-68155-714.
  * [24] J. Puget (2005): _Automatic Detection of Variable and Value Symmetries_.  In P. van Beek, editor: Proceedings of the Eleventh International Conference on Principles and Practice of Constraint Programming (CP’05), Lecture Notes in Computer Science 3709, Springer-Verlag, pp. 475–489, 10.1007/1156475136.
  * [25] K. Sakallah (2009): _Symmetry and Satisfiability_.  In A. Biere, M. Heule, H. van Maaren & T. Walsh, editors: Handbook of Satisfiability, chapter 10, Frontiers in Artificial Intelligence and Applications 185, IOS Press, pp. 289–338, 10.3233/978-1-58603-929-5-289.
  * [26] T. Syrjänen (2001): _Lparse 1.0 User’s Manual_.  Available at http://www.tcs.hut.fi/Software/smodels/lparse.ps.gz.
  * [27] A. Tarzariol, M. Gebser, M. Law & K. Schekotihin (2022): _Efficient lifting of symmetry breaking constraints for complex combinatorial problems_ , 10.48550/ARXIV.2205.07129.  Available at https://arxiv.org/abs/2205.07129.
  * [28] A. Tarzariol, M. Gebser & K. Schekotihin (2021): _Lifting Symmetry Breaking Constraints with Inductive Logic Programming_.  In Z. Zhi-Hua, editor: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI’21), ijcai.org, pp. 2062–2068, 10.24963/ijcai.2021/284.
  * [29] A. Tarzariol, M. Gebser & K. Schekotihin (2022): _Lifting Symmetry Breaking Constraints with Inductive Logic Programming_.  Machine Learning 111(4), pp. 1303 – 1326, 10.1007/s10994-022-06146-3.
  * [30] Erich Christian Teppan, Gerhard Friedrich & Georg Gottlob (2016): _Tractability frontiers of the partner units configuration problem_.  J. Comput. Syst. Sci. 82(5), pp. 739–755, 10.1016/j.jcss.2015.12.004.
  * [31] T. Walsh (2012): _Symmetry Breaking Constraints: Recent Results_.  In J. Hoffmann & B. Selman, editors: Proceedings of the Twenty-Sixth National Conference on Artificial Intelligence (AAAI’12), AAAI Press, pp. 2192–2198.

##  Appendix A Inductive Learning from Symmetries - Example

Here we will illustrate an example of our ILP framework; for more details, see
[29]. Let us consider the pigeon-hole problem, which is about checking whether
$p$ pigeons can be placed into $h$ holes such that each hole contains at most
one pigeon. An encoding in ASP of this problem is:

pigeon(X-1) :- pigeon(X), X > 1. hole(X-1) :- hole(X), X > 1. {p2h(P,H) :
hole(H)} = 1 :- pigeon(P). :- p2h(P1,H), p2h(P2,H), P1 != P2.It takes as input
the ground facts pigeon($p$). and hole($h$). For example, solving the instance
with $p=3$ and $h=3$ leads to six answer sets:

⬇

$\mathit{AS}_{1}$ = {p2h(1,1), p2h(2,2), p2h(3,3)} = 100010001

$\mathit{AS}_{2}$ = {p2h(1,1), p2h(2,3), p2h(3,2)} = 010100001

$\mathit{AS}_{3}$ = {p2h(1,2), p2h(2,1), p2h(3,3)} = 100001010

$\mathit{AS}_{4}$ = {p2h(1,2), p2h(2,3), p2h(3,1)} = 001100010

$\mathit{AS}_{5}$ = {p2h(1,3), p2h(2,1), p2h(3,2)} = 010001100

$\mathit{AS}_{6}$ = {p2h(1,3), p2h(2,2), p2h(3,1)} = 001010100

where the binary integer given on the right corresponds to the value that will
be considered for the lexicographic order. Using sbass with this instance
produces the following set of generators:

⬇

$\pi_{1}\;=\;\big{(}\,$p2h(3,2) p2h(3,3)$\,\big{)}$ $\big{(}\,$p2h(2,2)
p2h(2,3)$\,\big{)}$ $\big{(}\,$p2h(1,2) p2h(1,3)$\,\big{)}$

$\pi_{2}\;=\;\big{(}\,$p2h(3,1) p2h(3,3)$\,\big{)}$ $\big{(}\,$p2h(2,1)
p2h(2,3)$\,\big{)}$ $\big{(}\,$p2h(1,1) p2h(1,3)$\,\big{)}$

$\pi_{3}\;=\;\big{(}\,$p2h(2,3) p2h(3,3)$\,\big{)}$ $\big{(}\,$p2h(2,2)
p2h(3,2)$\,\big{)}$ $\big{(}\,$p2h(2,1) p2h(3,1)$\,\big{)}$

$\pi_{4}\;=\;\big{(}\,$p2h(1,1) p2h(3,3)$\,\big{)}$ $\big{(}\,$p2h(2,1)
p2h(2,3)$\,\big{)}$ $\big{(}\,$p2h(1,3) p2h(3,1)$\,\big{)}$

$\quad\big{(}\,$p2h(1,2) p2h(3,2)$\,\big{)}$

Applying a generator to an answer set returns a symmetric solution. For
example, $\pi_{\\_}1(\mathit{AS}_{\\_}6)=\mathit{AS}_{\\_}4$. For each answer
set $AS_{\\_}i$, we apply all the generators to it and check whether there is
a generator $\pi_{\\_}j$ such that
$AS_{\\_}i\geq\pi_{\\_}j(\mathit{AS}_{\\_}i)$. If there exists such
$\pi_{\\_}j$, then $AS_{\\_}i$ will define a negative example, otherwise a
positive one.

As a result, we create one positive example with $\mathit{AS}_{\\_}6$ (since
it is the only answer set that is not mapped into a smaller interpretation)
and five negative examples with the other answer sets. The resulting ILP task
is as follows:

%% Input encoding pigeon(X-1) :- pigeon(X), X > 1. hole(X-1) :- hole(X), X >
1. {p2h(P,H) : hole(H)} = 1 :- pigeon(P). :- p2h(P1,H), p2h(P2,H), P1 != P2.
%% Active Background Knowledge lessThan(X,Y) :- pigeon(X), pigeon(Y), X < Y.
lessThan(X,Y) :- hole(X), hole(Y), X < Y. maxpigeon(X) :- pigeon(X), not
pigeon(X+1). maxhole(X) :- hole(X), not hole(X+1). %% Negative examples
#neg(id1@100, {p2h(2,3), p2h(1,2), p2h(3,1)}, {p2h(2,1), p2h(1,1), p2h(3,3),
p2h(1,3), p2h(3,2), p2h(2,2)}, {pigeon(3). hole(3).}). #neg(id3@100,
{p2h(2,1), p2h(3,2), p2h(1,3)}, {p2h(1,1), p2h(3,3), p2h(3,1), p2h(2,2),
p2h(2,3), p2h(1,2)}, {pigeon(3). hole(3).}). #neg(id4@100, {p2h(2,3),
p2h(1,1), p2h(3,2)}, {p2h(2,1), p2h(3,3), p2h(3,1), p2h(1,3), p2h(2,2),
p2h(1,2)}, {pigeon(3). hole(3).}). #neg(id5@100, {p2h(2,1), p2h(3,3),
p2h(1,2)}, {p2h(1,1), p2h(3,1), p2h(1,3), p2h(3,2), p2h(2,3), p2h(2,2)},
{pigeon(3). hole(3).}). #neg(id6@100, {p2h(1,1), p2h(3,3), p2h(2,2)},
{p2h(2,1), p2h(3,1), p2h(1,3), p2h(3,2), p2h(2,3), p2h(1,2)}, {pigeon(3).
hole(3).}). %% Positive example #pos(id2, {p2h(3,1), p2h(2,2), p2h(1,3)}, {},
{pigeon(3). hole(3).}). %% Language bias #modeb(2,p2h(var(pigeon),var(hole))).
#modeb(2,pigeon(var(pigeon))). #modeb(2,hole(var(hole))).
#modeb(1,maxhole(var(hole))). #modeb(1,maxpigeon(var(pigeon))).
#modeb(2,lessThan(var(hole),var(hole)),(anti_reflexive)).
#modeb(2,lessThan(var(pigeon),var(pigeon)),(anti_reflexive)).
#modeb(2,lessThan(var(hole),var(pigeon))).
#modeb(2,lessThan(var(pigeon),var(hole))).

After running ilasp, the learned first-order constraints are:

:- p2h(X,Y), lessThan(Z,Y), maxpigeon(X). % do not assign the pigeon with the
max label to a hole % other than the first one :- p2h(X,Y), lessThan(X,Y),
lessThan(Y,Z). % for all but the last hole, do not assign a pigeon with % a
smaller label to the hole