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

\(\) 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

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

\(\) 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

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

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

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

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

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

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

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