Automatic Generation of Polynomial Symmetry Breaking Constraints

• URL: http://arxiv.org/abs/2602.08297v1
• Date: Mon, 09 Feb 2026 06:05:10 GMT
• Title: Automatic Generation of Polynomial Symmetry Breaking Constraints
• Authors: Madalina Erascu, Johannes Middeke,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Symmetry in integer programming causes redundant search and is often handled with symmetry breaking constraints that remove as many equivalent solutions as possible. We propose an algebraic method which allows to generate a random family of polynomial inequalities which can be used as symmetry breakers. The method requires as input an arbitrary base polynomial and a group of permutations which is specific to the integer program. The computations can be easily carried out in any major symbolic computation software. In order to test our approach, we describe a case study on near half-capacity 0-1 bin packing instances which exhibit substantial symmetries. We statically generate random quadratic breakers and add them to a baseline integer programming problem which we then solve with Gurobi. It turns out that simple symmetry breakers, especially combining few variables and permutations, most consistently reduce work time.

Related papers

• 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)
• 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)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Deep Learning Symmetries and Their Lie Groups, Algebras, and Subalgebras from First Principles [55.41644538483948]
  We design a deep-learning algorithm for the discovery and identification of the continuous group of symmetries present in a labeled dataset. We use fully connected neural networks to model the transformations symmetry and the corresponding generators. Our study also opens the door for using a machine learning approach in the mathematical study of Lie groups and their properties.
  arXiv  Detail & Related papers  (2023-01-13T16:25:25Z)
• 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)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• Linear programming with unitary-equivariant constraints [2.0305676256390934]
  Unitary equivariance is a natural symmetry that occurs in many contexts in physics and mathematics. We show that under additional symmetry assumptions, this problem reduces to a linear program that can be solved in time that does not scale in $d$. We also outline a possible route for extending our method to general unitary-equivariant semidefinite programs.
  arXiv  Detail & Related papers  (2022-07-12T17:37:04Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Penalty Weights in QUBO Formulations: Permutation Problems [0.0]
  optimisation algorithms designed to work on quantum computers have been of research interest in recent years. Many of these solver can only optimise problems that are in binary and quadratic form. There are many optimisation problems that are naturally represented as permutations. We propose new static methods of calculating penalty weights which lead to more promising results.
  arXiv  Detail & Related papers  (2022-06-20T22:00:38Z)
• 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)
• Computing the quantum guesswork: a quadratic assignment problem [6.445605125467573]
  Previous approaches to the computation of the guesswork were based on standard semi-definite programming techniques. We show that computing the quantum guesswork of qubit ensembles with uniform probability distribution leads to a more-than-quadratic speedup. As examples, we compute the guesswork of regular and quasi-regular sets of qubit states.
  arXiv  Detail & Related papers  (2021-12-03T01:24:57Z)

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.