symmetry handling

The Impact of Symmetry Handling for the Stable Set Problem via Schreier-Sims Cuts

  • Christopher Hojny
  • Marc E. Pfetsch
  • José Verschae
    • Categories Integer Programming Tags , , ,

    Symmetry handling inequalities (SHIs) are an appealing and popular tool for handling symmetries in integer programming. Despite their practical application, little is known about their interaction with optimization problems. This article focuses on Schreier-Sims (SST) cuts, a recently introduced family of SHIs, and investigate their impact on the computational and polyhedral complexity of optimization problems. … Read more

    A proof system for certifying symmetry and optimality reasoning in integer programming

  • Jasper van Doornmalen
  • Leon Eifler
  • Ambros Gleixner
  • Christopher Hojny
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    We present a proof system for establishing the correctness of results produced by optimization algorithms, with a focus on mixed-integer programming (MIP). Our system generalizes the seminal work of Bogaerts, Gocht, McCreesh, and Nordström (2022) for binary programs to handle any additional difficulties arising from unbounded and continuous variables, and covers a broad range of … Read more

    Handling Symmetries in Mixed-Integer Semidefinite Programs

  • Christopher Hojny
  • Marc E. Pfetsch
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , ,

    Symmetry handling is a key technique for reducing the running time of branch-and-bound methods for solving mixed-integer linear programs. In this paper, we generalize the notion of (permutation) symmetries to mixed-integer semidefinite programs (MISDPs). We first discuss how symmetries of MISDPs can be automatically detected by finding automorphisms of a suitably colored auxiliary graph. Then … Read more

    Handling Sub-symmetry in Integer Programming using Activation Handlers

  • Christopher Hojny
  • Tom Verhoeff
  • Sten Wessel
    • Categories Integer Programming Tags , ,

    Symmetry in integer programs (IPs) can be exploited in order to reduce solving times. Usually only symmetries of the original IP are handled, but new symmetries may arise at some nodes of the branch-and-bound tree. While symmetry-handling inequalities (SHIs) can easily be used to handle original symmetries, handling sub-symmetries arising later on is more intricate. … Read more

    A Unified Framework for Symmetry Handling

  • Jasper van Doornmalen
  • Christopher Hojny
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Integer Programming Tags , , , , ,

    Handling symmetries in optimization problems is essential for devising efficient solution methods. In this article, we present a general framework that captures many of the already existing symmetry handling methods. While these methods are mostly discussed independently from each other, our framework allows to apply different methods simultaneously and thus outperforming their individual effect. Moreover, … Read more

    Efficient Propagation Techniques for Handling Cyclic Symmetries in Binary Programs

  • Jasper van Doornmalen
  • Christopher Hojny
    • Categories 0-1 Programming Tags , , ,

    The presence of symmetries of binary programs typically degrade the performance of branch-and-bound solvers. In this article, we derive efficient variable fixing algorithms to discard symmetric solutions from the search space based on propagation techniques for cyclic groups. Our algorithms come with the guarantee to find all possible variable fixings that can be derived from … Read more

    Schreier-Sims Cuts meet Stable Set: Preserving Problem Structure when Handling Symmetries

  • Christopher Hojny
  • Marc E. Pfetsch
  • José Verschae
    • Categories 0-1 Programming Tags , ,

    Symmetry handling inequalities (SHIs) are a popular tool to handle symmetries in integer programming. Despite their successful application in practice, only little is known about the interaction of SHIs with optimization problems. In this article, we focus on SST cuts, an attractive class of SHIs, and investigate their computational and polyhedral consequences for optimization problems. … Read more