Lifting Symmetry Breaking Constraints with Inductive Logic Programming
- URL: http://arxiv.org/abs/2112.11806v2
- Date: Thu, 23 Dec 2021 12:41:28 GMT
- Title: Lifting Symmetry Breaking Constraints with Inductive Logic Programming
- Authors: Alice Tarzariol, Martin Gebser, Konstantin Schekotihin
- Abstract summary: We introduce a new model-oriented approach for Answer Set Programming that lifts the Symmetry Breaking Constraints into a set of interpretable first-order constraints.
Experiments demonstrate the ability of our framework to learn general constraints from instance-specific SBCs.
- Score: 2.036811219647753
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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.
Related papers
- Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods.
Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem.
As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
arXiv Detail & Related papers (2023-10-08T23:39:38Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
Constrained optimization problems abound in industry, from portfolio optimization to logistics.
One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space.
In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
arXiv Detail & Related papers (2022-11-16T18:59:54Z) - A Model-Oriented Approach for Lifting Symmetries in Answer Set
Programming [0.0]
We introduce a new model-oriented Answer Set Programming that lifts the SBCs of small problem instances into a set of interpretable first-order constraints.
After targeting simple problems, we aim to extend our method to be applied also for advanced decision problems.
arXiv Detail & Related papers (2022-08-05T10:50:03Z) - Efficient Knowledge Compilation Beyond Weighted Model Counting [7.828647825246474]
We introduce Second Level Algebraic Model Counting (2AMC) as a generic framework for these kinds of problems.
First level techniques based on Knowledge Compilation (KC) have been adapted for specific 2AMC instances by imposing variable order constraints.
We show that we can exploit the logical structure of a 2AMC problem to omit parts of these constraints, thus limiting the negative effect.
arXiv Detail & Related papers (2022-05-16T08:10:40Z) - Efficient lifting of symmetry breaking constraints for complex
combinatorial problems [9.156939957189502]
This work extends the learning framework and implementation of a model-based approach for Answer Set Programming.
In particular, we incorporate a new conflict analysis algorithm in the Inductive Logic Programming system ILASP.
arXiv Detail & Related papers (2022-05-14T20:42:13Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space.
We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states.
Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
arXiv Detail & Related papers (2022-03-11T17:19:26Z) - QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver
Surrogates [14.905085636501438]
We build surrogate models of QUBO solvers via learning from solver data on a collection of instances of a problem.
In this way, we are able capture the common structure of the instances and their interactions with the solver, and produce good choices of penalty parameters.
QROSS is shown to generalise well to out-of-distribution datasets and different types of QUBO solvers.
arXiv Detail & Related papers (2021-03-19T09:06:12Z) - An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
We introduce a divide-and-conquer based diagnosis algorithm (FastDiag) which identifies minimal sets of faulty constraints in an over-constrained problem.
We compare FastDiag with the conflict-directed calculation of hitting sets and present an in-depth performance analysis.
arXiv Detail & Related papers (2021-02-17T19:55:42Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
We propose two novel conditional gradient-based methods for solving structured convex optimization problems.
The most important feature of our framework is that only a subset of the constraints is processed at each iteration.
Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
arXiv Detail & Related papers (2020-07-07T21:26:35Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
We present a general framework for mining constraints from data.
In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem.
We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
arXiv Detail & Related papers (2020-06-18T20:09:53Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.