Exploiting Symmetries in MUS Computation (Extended version)

• URL: http://arxiv.org/abs/2412.13606v1
• Date: Wed, 18 Dec 2024 08:34:32 GMT
• Title: Exploiting Symmetries in MUS Computation (Extended version)
• Authors: Ignace Bleukx, Hélène Verhaeghe, Bart Bogaerts, Tias Guns,
• Abstract summary: In eXplainable Constraint Solving (XCS), it is common to extract a Minimal Unsatisfiable Subset (MUS) from a set of unsatisfiable constraints.<n>Finding MUSes can be computationally expensive for highly symmetric problems.<n>In this paper, we take inspiration from existing symmetry-handling techniques and adapt well-known MUS-computation methods to exploit symmetries in the specification.
• Score: 11.266189935383476
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In eXplainable Constraint Solving (XCS), it is common to extract a Minimal Unsatisfiable Subset (MUS) from a set of unsatisfiable constraints. This helps explain to a user why a constraint specification does not admit a solution. Finding MUSes can be computationally expensive for highly symmetric problems, as many combinations of constraints need to be considered. In the traditional context of solving satisfaction problems, symmetry has been well studied, and effective ways to detect and exploit symmetries during the search exist. However, in the setting of finding MUSes of unsatisfiable constraint programs, symmetries are understudied. In this paper, we take inspiration from existing symmetry-handling techniques and adapt well-known MUS-computation methods to exploit symmetries in the specification, speeding-up overall computation time. Our results display a significant reduction of runtime for our adapted algorithms compared to the baseline on symmetric problems.

Related papers

• Automatic Generation of Polynomial Symmetry Breaking Constraints [0.0]
  We propose a method to generate a random family of inequalities which can be used as symmetry breakers.<n>The method requires as input an arbitrary base and a group of symbolic permutations which is specific to the integer program.<n>It turns out that simple symmetry breakers, especially combining few variables and permutations, most consistently reduce work time.
  arXiv  Detail & Related papers  (2026-02-09T06:05:10Z)
• Orbitopal Fixing in SAT [0.688204255655161]
  We present a practical static symmetry breaking approach based on orbitopal fixing.<n>Our methods deliver consistent speedups on symmetry-rich benchmarks with negligible regressions elsewhere.
  arXiv  Detail & Related papers  (2026-01-23T16:01:48Z)
• Faster Symmetry Breaking Constraints for Abstract Structures [1.784933900656067]
  We show a new incomplete method of breaking the symmetries of abstract structures by better exploiting their representations.<n>We apply the method in breaking the symmetries arising from indistinguishable objects, a commonly occurring type of symmetry.
  arXiv  Detail & Related papers  (2025-11-14T07:34:23Z)
• Computing Game Symmetries and Equilibria That Respect Them [77.72705755558839]
  We study the computational of identifying and using symmetries in games. We find a strong connection between game symmetries and graph automorphisms. We show that finding a Nash equilibrium that respects a given set of symmetries is exactly as hard as Brouwer fixed point and gradient descent problems.
  arXiv  Detail & Related papers  (2025-01-15T16:15:16Z)
• Metaheuristics for the Template Design Problem: Encoding, Symmetry and Hybridisation [0.0]
  The template design problem (TDP) is a hard problem with a high number of symmetries which makes solving it more complicated. This paper explores and analyses a wide range of metaheuristics to tackle the problem with the aim of assessing their suitability for finding template designs.
  arXiv  Detail & Related papers  (2024-11-05T06:29:12Z)
• Structured Regularization for Constrained Optimization on the SPD Manifold [1.1126342180866644]
  We introduce a class of structured regularizers, based on symmetric gauge functions, which allow for solving constrained optimization on the SPD manifold with faster unconstrained methods. We show that our structured regularizers can be chosen to preserve or induce desirable structure, in particular convexity and "difference of convex" structure.
  arXiv  Detail & Related papers  (2024-10-12T22:11:22Z)
• Symmetry-Informed Governing Equation Discovery [29.16110821783827]
  We propose to leverage symmetry in automated equation discovery to compress the equation search space and improve the accuracy and simplicity of the learned equations. Our approach demonstrates better robustness against noise and recovers governing equations with significantly higher probability than baselines without symmetry.
  arXiv  Detail & Related papers  (2024-05-27T01:58:23Z)
• Learning Layer-wise Equivariances Automatically using Gradients [66.81218780702125]
  Convolutions encode equivariance symmetries into neural networks leading to better generalisation performance. symmetries provide fixed hard constraints on the functions a network can represent, need to be specified in advance, and can not be adapted. Our goal is to allow flexible symmetry constraints that can automatically be learned from data using gradients.
  arXiv  Detail & Related papers  (2023-10-09T20:22:43Z)
• Tapping into Permutation Symmetry for Improved Detection of k-Symmetric Extensions [3.501108734684888]
  In this study, we introduce an approach that adeptly leverages permutation symmetry. By fine-tuning the SDP problem for detecting ( k )-symmetric extensions, our method markedly diminishes the searching space dimensionality. This leads to an algorithmic enhancement, reducing the complexity from ( O(d2k) ) to ( O(kd2) ) in the qudit ( k )-symmetric extension scenario.
  arXiv  Detail & Related papers  (2023-09-08T06:05:56Z)
• 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)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• 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)
• Symmetry Breaking in Symmetric Tensor Decomposition [44.181747424363245]
  We consider the nonsymmetry problem associated with computing the points rank decomposition of symmetric tensors. We show that critical points the loss function is detected by standard methods.
  arXiv  Detail & Related papers  (2021-03-10T18:11:22Z)
• Classical symmetries and QAOA [3.2880869992413246]
  We study the relationship between the Quantum Approximate Optimization Algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symmetry properties of the QAOA dynamics and the group of classical symmetries of the objective function.
  arXiv  Detail & Related papers  (2020-12-08T20:02:09Z)

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.