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

Computational Aspects of Relaxation Complexity: Possibilities and Limitation

The relaxation complexity $\mathrm{rc}(X)$ of the set of integer points $X$ contained in a polyhedron is the smallest number of facets of any polyhedron $P$ such that the integer points in $P$ coincide with $X$. It is a useful tool to investigate the existence of compact linear descriptions of $X$. In this article, we derive … Read more

A Benders-type Approach for Robust Optimization of Kidney Exchanges under Full Recourse

The goal of kidney exchange programs is to match recipients with a willing but incompatible donor with another compatible donor, so as to maximize total (weighted) transplants. There is significant uncertainty in this process, as planned transplants may be cancelled for a variety of reasons. Planning exchanges while considering failures, and options for recourse, is … Read more

Simple Iterative Methods for Linear Optimization over Convex Sets

We give simple iterative methods for computing approximately optimal primal and dual solutions for the problem of maximizing a linear functional over a convex set $K$ given by a separation oracle. In contrast to prior work, our algorithms directly output primal and dual solutions and avoid a common requirement of binary search on the objective … Read more

The SCIP Optimization Suite 7.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 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies … Read more

Integrality of Linearizations of Polynomials over Binary Variables using Additional Monomials

Polynomial optimization problems over binary variables can be expressed as integer programs using a linearization with extra monomials in addition to those arising in the given polynomial. We characterize when such a linearization yields an integral relaxation polytope, generalizing work by Del Pia and Khajavirad (SIAM Journal on Optimization, 2018) and Buchheim, Crama and Rodríguez-Heck … Read more

Polynomial Size IP Formulations of Knapsack May Require Exponentially Large Coefficients

A desirable property of integer formulations is to consist of few inequalities having small coefficients. We show that these targets are conflicting by proving the existence of knapsack sets that need exponentially many inequalities or exponentially large coefficients in any integer formulation. Moreover, we show that there exist undirected graphs such that (in a natural … Read more

Knapsack Polytopes – A Survey

The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy a given single linear inequality with non-negative coefficients. This paper provides a comprehensive overview of knapsack polytopes. We discuss basic polyhedral properties, (lifted) cover and other valid inequalities, cases for which complete linear descriptions are known, geometric properties for small dimensions, … Read more

Strong IP Formulations Need Large Coefficients

The development of practically well-behaving integer programming formulations is an important aspect of solving linear optimization problems over a set $X \subseteq \{0,1\}^n$. In practice, one is often interested in strong integer formulations with additional properties, e.g., bounded coefficients to avoid numerical instabilities. This article presents a lower bound on the size of coefficients in … Read more