Summary

Integral polyhedra are one of the central objects of integer programming, as they allow to solve combinatorial optimization problems by means of linear programming. Finding outer descriptions of integral polyhedra associated with discrete problems, however, is a challenging task and in many cases such descriptions are not known or exponentially large. To circumvent these problems, a lot of effort has been spent to find descriptions in alternative spaces, leading to groundbreaking insights on practically relevant combinatorial optimization problems. Moreover, if no small formulation of such polyhedra exists, alternative lines of research have studied the existence of small formulations by allowing to use positive semidefinite or integrality constraints.

The aim of this workshop is to bring together researchers from different mathematical disciplines with expertise in aspects of integral polyhedra. Besides presentations about recent achievements, the workshop also features open problem sessions to identify future research directions on the topic, and to stimulate cross-disciplinary collaboration.

Organizers

Participants
(confirmed)

Programme

The programme can be found through THIS LINK

Abstracts

Manuel Aprile
Binary extended formulations and sequential convexification
A binarization of a variable x is a linear formulation through additional binary variables, whose integrality implies the integrality of x. A binary extended formulation of a polyhedron P is obtained by adding to the original description of P binarizations of some of its variables. In the context of mixed-integer programming, imposing integrality on 0/1 variables rather than on general integer variables has interesting convergence properties and has been studied both from the theoretical and from the practical point of view. We propose a notion of natural binarizations and binary extended formulations, encompassing all the ones studied in the literature. We give a simple characterization of the vertices of such formulations, which allows us to study their behavior with respect to sequential convexification. In particular, given a binary extended formulation and one of its variables x, we study a parameter that measures the progress made towards ensuring the integrality of x via application of sequential convexification. We formulate this parameter, which we call rank, as the solution of a set covering problem and express it exactly for the classical binarizations from the literature.
This is joint work with Michele Conforti and Marco Di Summa.

Christopher Hojny
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 employ efficient mixed-integer programming techniques to compute a robust and numerically more practical variant of the relaxation complexity. Our proposed models require row or column generation techniques and can be enhanced by symmetry handling and suitable propagation algorithms. Theoretically, we compare the quality of our models in terms of their LP relaxation values. The performance of those models is investigated on a broad test set and is underlined by their ability to solve challenging instances. Our code is publicly available and we conclude this presentation with a short software demonstration.
This is joint work with Gennadiy Averkov and Matthias Schymura

Aida Khajavirad
Rank-one Boolean tensor factorization and the multilinear polytope
We consider the NP-hard problem of approximating a tensor with binary entries by a rank-one tensor, referred to as rank-one Boolean tensor factorization problem. We formulate this problem, in an extended space of variables, as the problem of minimizing a linear function over a highly structured multilinear set. Leveraging on our prior results regarding the facial structure of multilinear polytopes, we propose novel linear programming relaxations for rank-one Boolean tensor factorization. To analyze the performance of the proposed linear programs, we consider a random corruption model for the input tensor. We first consider the original NP-hard problem and establish information theoretic limits under the random model. Next, we obtain sufficient conditions under which the proposed linear programming relaxations recover the ground truth with high probability. Our theoretical results as well as numerical simulations indicate that certain facets of the multilinear polytope significantly improve the recovery properties of linear programming relaxations for rank-one Boolean tensor factorization.
Joint work with Alberto Del Pia.

Stefan Kober
Improved lower bound on the dimension of the EU council’s voting rules
Kurz and Napel (Optim Lett 10(6):1245–1256, 2015, https://doi.org/10.1007/s11590-015-0917-0) proved that the voting system of the EU council (based on the 2014 population data) cannot be represented as the intersection of six weighted games, i.e., its dimension is at least 7. This set a new record for real-world voting rules and the authors posed the exact determination as a challenge. Recently, Chen et al. (An upper bound on the dimension of the voting system of the European Union Council under the Lisbon rules, 2019, arXiv:1907.09711) showed that the dimension is at most 24. We provide the first improved lower bound and show that the dimension is at least 8.
This is joint work with Stefan Weltge.

Thomas Rothvoss
Discrepancy Theory: Algorithms and Applications
An exciting line of work, starting with Bansal’s seminal paper provides algorithms to find partial colorings in polytopes and more generally in large enough convex sets. The original motivation comes from discrepancy theory where the goal is to bi-color a given set of sets as evenly as possible. For example, this enables a constructive solution to Spencer’s “6-standard deviations suffice” Theorem. We show a surprising simple deterministic algorithm to find partial colorings in a polytope. Moreover we show how discrepancy theory can be used to obtain linear size spectral spartifiers in a graph, matching the result of Batson, Spielman and Srivastava. In particular such sparsifiers imply that in any undirected graph one can select a linear size set of edges with weights so that every cut is preserved up to a 1+epsilon factor.
This is joint work with Avi Levy, Harish Ramadas, and Victor Reis.

Ina Seidel
Lifts for Voronoi cells of lattices
Many polytopes arising in polyhedral combinatorics are linear projections of higher-dimensional polytopes with significantly fewer facets. Such lifts may yield compressed representations of polytopes, which are typically used to construct small-size linear programs. Motivated by algorithmic implications for the closest vector problem, we study lifts of Voronoi cells of lattices. We construct an explicit $d$-dimensional lattice such that every lift of the respective Voronoi cell has $2^{\Omega(d/\log d)} facets. On the positive side, we show that Voronoi cells of $d$-dimensional root lattices and their dual lattices have lifts with $\mathcal{O}(d)$ and $\mathcal{O}(d\log d)$ facets, respectively. We obtain similar results for spectrahedral lifts.
This is joint work with Matthias Schymura and Stefan Weltge.

Hans Raj Tiwary
Permuting some coordinates of a Polytope: Extension Complexity
Let P be a polytope with coordinates labeled x_1,…,x_d. Define $\mathrm{perm}_I(P)$ to be the polytope obtained by taking every permutation $\sigma$ whose set of fixed-points is $[d]\setminus I$, permuting the coordinates of every point in $P$ according to $\sigma$ and taking the convex hull of all such points. Also, define $\mathrm{sort}(P)$ to be the polytope obtained by taking each vertex of $P$ in “sorted order”.

We study the extension complexity of $\mathrm{perm}_I(P)$ and $\mathrm{sort}(P)$ in terms of the extension complexity of $P$. A result by Kaibel and Pashkovich states that if $\mathrm{sort}(P)\subseteq P$ and $I=[d]$ then the extension complexity of $\mathrm{perm}_I(P)$ is bounded above by a polynomial of the extension complexity of $P$. We show that the extension complexity of $\mathrm{perm}_I(P)$ can increase exponentially if $I\neq [d]$ even if the vertices of $P$ contain only three values, say $0,1,$ or $2$ at each of the coordinates $x_i$ for $i\in I$. Furthermore, the extension complexity of $\mathrm{sort}(P)$ can be exponentially larger than that of $P$. We also discuss the implications for the $0/1$ case.

Aleksei Udovenko
Applications of Integer Programming in Symmetric-key Cryptography
In the recent decade, security analysis of symmetric-key ciphers shifted towards automation. The search of attacks is now most often aided by generic solvers for languages such as SAT (Satisfiability), SMT (Satisfiability Modulo Theories), CP (Constraint Programming), MILP (Mixed-Integer Linear Programming). This approach already covers many attack classes such as linear/differential cryptanalysis, division property, meet-in-the-middle attacks, etc., and much effort is done today towards modeling other attacks. MILP is used more often since it naturally allows to express the optimization aspect and the integer / floating point arithmetic. These often occur in cryptanalytic attacks. For example, in differential/linear cryptanalysis, the goal is to find a valid pattern of differences/linear masks throughout the analyzed cipher such that the associated cost – probability or correlation – is maximal. This talk will introduce the basics of main symmetric cryptanalysis methods, overview the history of using MILP for finding attacks (or proving resistance to), and describe the state-of-the-art techniques. The talk will be concluded by stating open problems in the field.

Matthias Walter
Using Oracles to Analyze Polyhedra in Practice
The well-known equivalence of optimization and separation implies that one can use an optimization oracle for an integer program to derive a separation oracle for the corresponding integer hull. I will introduce the C++ library IPO in which such oracles as well as practical variants of relevant algorithms are implemented. Among them are algorithms for computing the affine hull and the dimension, for testing adjacency and for separating a point via a facet-defining inequality. I will provide example applications and discuss difficulties that one encounters.

Further information will follow soon.