Marc E. Pfetsch

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 … Read more

    Dual Conflict Analysis for Mixed-Integer Semidefinite Programs

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

    Conflict analysis originally tried to exploit the knowledge that certain nodes in a relaxation-based branch-and-bound are infeasible. It has been extended to derive valid constraints also from feasible nodes. This paper adapts this approach to mixed-integer semidefinite programs. Using dual solutions, the primal constraints are aggregated and the resulting inequalities can be used at different … Read more

    Sub-Exponential Lower Bounds for Branch-and-Bound with General Disjunctions via Interpolation

  • Max Gläser
  • Marc E. Pfetsch
    • Categories Integer Programming

    \(\) This paper investigates linear programming based branch-and-bound using general disjunctions, also known as stabbing planes, for solving integer programs. We derive the first sub-exponential lower bound (in the encoding length \(L\) of the integer program) for the size of a general branch-and-bound tree for a particular class of (compact) integer programs, namely \(2^{\Omega(L^{1/12 -\epsilon})}\) … 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

    On the Complexity of Finding Shortest Variable Disjunction Branch-and-Bound Proofs

  • Max Gläser
  • Marc E. Pfetsch
    • Categories Branch and Cut Algorithms Tags , ,

    We investigate the complexity of finding small branch-and-bound trees using variable disjunctions. We first show that it is not possible to approximate the size of a smallest branch-and-bound tree within a factor of 2^(1/5) in time 2^(\delta n) with \delta < 1/5, unless the strong exponential time hypothesis fails. Similarly, for any \varepsilon > 0, … Read more

    The SCIP Optimization Suite 8.0

  • Ksenia Bestuzheva
  • Mathieu Besançon
  • Wei-Kun Chen
  • Antonia Chmiela
  • Tim Donkiewicz
  • Jasper van Doornmalen
  • Leon Eifler
  • Oliver Gaul
  • Gerald Gamrath
  • Ambros Gleixner
  • Leona Gottwald
  • Christoph Graczyk
  • Katrin Halbig
  • Alexander Hoen
  • Christopher Hojny
  • Rolf van der Hulst
  • Thorsten Koch
  • Marco E. Lübbecke
  • Stephen J. Maher
  • Frederic Matter
  • Erik Mühmer
  • Benjamin Müller
  • Marc E. Pfetsch
  • Daniel Rehfeldt
  • Steffan Schlein
  • Franziska Schlösser
  • Felipe Serrano
  • Yuji Shinano
  • Boro Sofranac
  • Mark Turner
  • Stefan Vigerske
  • Fabian Wegscheider
  • Philipp Wellner
  • Dieter Weninger
  • Jakob Witzig
    • Categories Branch and Cut Algorithms, Integer Programming, Optimization Software and Modeling Systems Tags , , , , , , , , ,

    The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 8.0 of the SCIP Optimization Suite. Major updates in SCIP include improvements in symmetry handling and decomposition algorithms, new cutting planes, a new plugin type … 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

    Presolving for Mixed-Integer Semidefinite Optimization

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

    This paper provides a discussion and evaluation of presolving methods for mixed-integer semidefinite programs. We generalize methods from the mixed-integer linear case and introduce new methods that depend on the semidefinite condition. The considered methods include adding linear constraints, bounds relying on 2 × 2 minors of the semidefinite constraints, bound tightening based on solving … Read more

    A Generic Optimization Framework for Resilient Systems

  • Marc E. Pfetsch
  • Andreas Schmitt
    • Categories (Mixed) Integer Nonlinear Programming, Robust Optimization Tags , , , ,

    This paper addresses the optimal design of resilient systems, in which components can fail. The system can react to failures and its behavior is described by general mixed integer nonlinear programs, which allows for applications to many (technical) systems. This then leads to a three-level optimization problem. The upper level designs the system minimizing a … Read more

    Combinatorial Acyclicity Models for Potential-based Flows

  • Oliver Habeck
  • Marc E. Pfetsch
    • Categories (Mixed) Integer Nonlinear Programming, Network Optimization Tags , , ,

    Potential-based flows constitute a basic model to represent physical behavior in networks. Under natural assumptions, the flow in such networks must be acyclic. The goal of this paper is to exploit this property for the solution of corresponding optimization problems. To this end, we introduce several combinatorial models for acyclic flows, based on binary variables … Read more