Marc E. Pfetsch The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming (CIP) framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a … Read more
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
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
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})}\) for … Read more
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
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 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
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
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
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