Faster Symmetry Breaking Constraints for Abstract Structures

• URL: http://arxiv.org/abs/2511.11029v1
• Date: Fri, 14 Nov 2025 07:34:23 GMT
• Title: Faster Symmetry Breaking Constraints for Abstract Structures
• Authors: Özgür Akgün, Mun See Chang, Ian P. Gent, Christopher Jefferson,
• Abstract summary: 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.
• Score: 1.784933900656067
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In constraint programming and related paradigms, a modeller specifies their problem in a modelling language for a solver to search and return its solution(s). Using high-level modelling languages such as Essence, a modeller may express their problems in terms of abstract structures. These are structures not natively supported by the solvers, and so they have to be transformed into or represented as other structures before solving. For example, nested sets are abstract structures, and they can be represented as matrices in constraint solvers. Many problems contain symmetries and one very common and highly successful technique used in constraint programming is to "break" symmetries, to avoid searching for symmetric solutions. This can speed up the solving process by many orders of magnitude. Most of these symmetry-breaking techniques involve placing some kind of ordering for the variables of the problem, and picking a particular member under the symmetries, usually the smallest. Unfortunately, applying this technique to abstract variables produces a very large number of complex constraints that perform poorly in practice. In this paper, we demonstrate a new incomplete method of breaking the symmetries of abstract structures by better exploiting their representations. We apply the method in breaking the symmetries arising from indistinguishable objects, a commonly occurring type of symmetry, and show that our method is faster than the previous methods proposed in (Akgün et al. 2025).

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)
• Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
  Chain-of-Thought (CoT) prompting enhances the reasoning of large language models (LLMs) by decomposing problems into sequential steps.<n>We propose Syzygy of Thoughts (SoT)-a novel framework that extends CoT by introducing auxiliary, interrelated reasoning paths.<n>SoT captures deeper logical dependencies, enabling more robust and structured problem-solving.
  arXiv  Detail & Related papers  (2025-04-13T13:35:41Z)
• Exploiting Symmetries in MUS Computation (Extended version) [11.266189935383476]
  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.
  arXiv  Detail & Related papers  (2024-12-18T08:34:32Z)
• Equivariant Symmetry Breaking Sets [0.6475999521931204]
  Equivariant neural networks (ENNs) have been shown to be extremely effective in applications involving underlying symmetries. We propose a novel symmetry breaking framework that is fully equivariant and is the first which fully addresses spontaneous symmetry breaking.
  arXiv  Detail & Related papers  (2024-02-05T02:35:11Z)
• Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
  We focus on optimisation programming (SP), Optimal Control (SOC) and Decision Processes (MDP) Recent progress in solving convex multistage Markov problems is based on cutting planes approximations of the cost-to-go functions of dynamic programming equations. Cutting plane type methods can handle multistage problems with a large number of stages, but a relatively smaller number of state (decision) variables.
  arXiv  Detail & Related papers  (2023-03-28T01:30:40Z)
• 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)
• Learning to Reason With Relational Abstractions [65.89553417442049]
  We study how to build stronger reasoning capability in language models using the idea of relational abstractions. We find that models that are supplied with such sequences as prompts can solve tasks with a significantly higher accuracy.
  arXiv  Detail & Related papers  (2022-10-06T00:27:50Z)
• Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
  Book presents several efforts to tackle this challenge with important scientific implications. It provides alternative optimization schemes that scale well in terms of computational complexity. We present sparsity-exploiting hierarchies of relaxations, for either unconstrained or constrained problems.
  arXiv  Detail & Related papers  (2022-08-23T18:56:05Z)
• 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)
• Object Representations as Fixed Points: Training Iterative Refinement Algorithms with Implicit Differentiation [88.14365009076907]
  Iterative refinement is a useful paradigm for representation learning. We develop an implicit differentiation approach that improves the stability and tractability of training.
  arXiv  Detail & Related papers  (2022-07-02T10:00:35Z)
• Lifting Symmetry Breaking Constraints with Inductive Logic Programming [2.036811219647753]
  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.
  arXiv  Detail & Related papers  (2021-12-22T11:27:48Z)
• SPANet: Generalized Permutationless Set Assignment for Particle Physics using Symmetry Preserving Attention [62.43586180025247]
  Collisions at the Large Hadron Collider produce variable-size sets of observed particles. Physical symmetries of decay products complicate assignment of observed particles to decay products. We introduce a novel method for constructing symmetry-preserving attention networks.
  arXiv  Detail & Related papers  (2021-06-07T18:18:20Z)

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.