By Alice Tarzariol
Alpen Adria Universitat Klagenfurt (Austria)
April 2023
Abstract
Answer Set Programming (ASP) is a declarative programming paradigm based on non-monotonic reasoning and stable model semantics. Its versatile language can be used to encode many combinatorial search and optimization problems as compact and elegant logic programs, which answer sets correspond to problem solutions. Powerful algorithms of modern ASP solvers ensure efficient computation of answer sets even for large instances of practical problems.Nevertheless, the applicability of ASP is subordinated to the quality of the problem encoding, which often requires a programmer to have a clear understanding of the considered problem in combination with vast experience in using the ASP modeling language.In this regard, the computation of symmetric answer sets, i.e., syntactically different candidates that entail the same characteristics, is a factor that can significantly affect the performance of a solver. Finding symmetric answer sets does not bring any additional value and, therefore, programmers use constraints in their encoding to prune them from the search space. However, the identification of symmetries and the definition of constraints can be tedious and time-consuming. In the literature, we can find various tools that aim to avoid the computation of symmetric answer sets. A popular approach consists of automatically detecting and introducing a set of Symmetry Breaking Constraints (SBCs) for each given problem instance using properties of permutation groups. The system sbass 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. Moreover, 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. In contrast, model-oriented approaches aim to find general SBCs that depend less on a particular instance. This thesis presents a novel model-oriented approach that lifts ground symmetries identified by instance-specific approaches by applying Inductive Logic Programming—a symbolic machine-learning technique.The results show how the devised learning framework manages to find constraints that generalize for a given distribution of instances and overcome the limitations of the online application of instance-specific approaches like sbass. Its applicability is first studied on a limited set of simple combinatorial decision problems and then extended to industrial problems such as the Partner Units Problem. Experiments demonstrate that the efficiency of the learned constraints not only overcomes the propositional SBCs introduced by sbass but also outperforms advanced encodings written by ASP experts, thanks to the exploitation of the characteristics of the instances under consideration. Finally, we further generalize the application domain to combinatorial optimization problems, obtaining similar improvements in solver performance.