The role of rationality in integer-programming relaxations

For a finite set $X \subset \Z^d$ that can be represented as $X = Q \cap \Z^d$ for some polyhedron $Q$, we call $Q$ a relaxation of $X$ and define the relaxation complexity $\rc(X)$ of $X$ as the least number of facets among all possible relaxations $Q$ of $X$. The rational relaxation complexity $\rc_\Q(X)$ restricts … Read more

Efficient MIP Techniques for Computing the Relaxation Complexity

The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the minimal number of inequalities needed to formulate a linear optimization problem over X without using auxiliary variables. Besides its relevance in integer programming, this concept has interpretations in aspects of social choice, symmetric cryptanalysis, and machine learning. We … Read more

Mixed-Integer Programming Techniques for the Minimum Sum-of-Squares Clustering Problem

The minimum sum-of-squares clustering problem is a very important problem in data mining and machine learning with very many applications in, e.g., medicine or social sciences. However, it is known to be NP-hard in all relevant cases and to be notoriously hard to be solved to global optimality in practice. In this paper, we develop … Read more

Efficient Propagation Techniques for Handling Cyclic Symmetries in Binary Programs

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

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