Discrete Optimization Day Schedule
10:15 – 10:30. Kickoff coffee and welcome
10:30 – 11:05. Gonzalo Muñoz: “Treewidth and Extension Complexity” (Slides)
In this talk, we discuss linear programming (LP) formulations of 0-1 sets parametrized by treewidth: a graph-theoretical parameter that measures structured sparsity. We begin by discussing results that show that if a 0-1 set can be formulated as the set of binary vectors that satisfy certain constraints, and those constraints present a sparsity pattern whose treewidth is k, then the convex hull of the set can be formulated as a polytope of size O(n2^k). Additionally, we show that this bound is tight by proving the existence of 0-1 sets where a smaller formulation cannot exist, for any arbitrary treewidth level k. These results show a strong relationship between LP formulations of binary sets and the sparsity of their base description.
11:05 – 11:40. Eduardo Moreno: “Adaptive Partition Decomposition algorithm for Stochastic Problems” (Slides)
A classic approach to solving two-stage stochastic problems is to approximate the probability distribution by a sample of scenarios, which allows to solve a deterministic problem. However, in many cases a large number of scenarios are required to correctly represent the distribution, for example, in risk aversion optimization problems. Due to this, many scenario aggregation algorithms have emerged to address this problem, most of them to obtain an approximated solution. In this talk we present the Adaptive Partition Decomposition algorithm, for the automatic aggregation and disaggregation of scenarios on stochastic problems. This algorithm is an exact method based on the Bienstock-Zuckerberg decomposition approach, which uses the dual variables for disaggregating scenarios. We show the impact of this method on problems of risk aversion and problems of stochastic network design, as well as their differences and similarities with other classical methods, such as the Benders decomposition.
11:40 – 11:55. Coffee break
11:55 – 12:30. Aleksandr Kazachkov: “Sparse Cutting Planes For Quadratically-Constrained Quadratic Programs” (Slides)
Quadratically-constrained quadratic programs (QCQPs) are an active and challenging research topic in optimization. Their remarkable expressiveness has made these problems a cornerstone in the development of theoretical and practical improvements in non-convex optimization. While modern computational methods, especially those associated to semidefinite programming (SDP), are able to provide strong bounds, they typically rely on computationally-expensive computations hindering their applicability in medium-to-large-scale problems. In this work, we develop a computationally-efficient method that emulates the SDP-based approximations of nonconvex QCQPs via a cutting plane algorithm. These cuts are required to be sparse, in order to ensure attractive numerical properties, and efficiently computable. We present a novel connection between such sparse cut generation and the sparse principal component analysis (PCA) problem in statistics, which allows us to achieve these two goals. We show extensive computational results advocating for the use of our approach.
12:30 – 14:00. Lunch (on your own)
14:00 – 15:00. Daniel Espinoza: “Mixed Integer Programming: The State of the Art, … and why you should care” (Slides)
In this talk, we start with a crash introduction to mixed-integer optimization, its history, uses, and scope. We show that NP-completeness is not the (algorithmic) end for a problem… Rather a starting point. And that if we are willing to sacrifice a small degree of optimality, and we know good polyhedral descriptions for a problem, we can actually solve them, even for seemingly impossible sizes, in surprisingly small running times. We then move into explaining the main aspects of the technology behind modern solvers. Gloss over the most common technique to deal with really huge models, and finally, we conclude with an overview of two areas where deep advances have been made both in the theoretical and also in the computational side, namely: Stochastic Optimization and Risk.
15:00 – 15:15. Coffee break
15:15 – 15:50 Gustavo Angulo: “Matrices with Lexicographically-ordered Rows” (Slides)
The lexicographic order can be used to force a collection of decision vectors to be all different, i.e., to take on different values in some coordinates. We consider the set of fixed-size matrices with bounded integer entries and rows in lexicographic order. We present a dynamic program to optimize a linear function over this set, from which we obtain a compact extended formulation for its convex hull.
15:50 – 16:30 José Verschae: “Breaking Symmetries to rescue Sum of Squares: The case of makespan scheduling” (Slides)
The Sum of Squares (SOS) hierarchy gives an automatized technique to create a family of increasingly tighter convex relaxations for binary programs. There are several problems for which a constant number of rounds give integrality gaps matching the best-known approximation algorithm. In many other, however, ad-hoc techniques give significantly better approximation factors. The lower bounds instances, in many cases, are invariant under the action of a large permutation group. In this talk, I will present how the presence of symmetries on a formulation degrades the performance of the relaxation obtained by the SOS hierarchy. We do so for the special case of the minimum makespan problem on identical machines. Our first result is to show that a linear number of rounds of SOS applied over the configuration linear program yields an integrality gap of at least 1.0009. Then, we consider the weaker assignment linear program and add a well-chosen set of symmetry breaking inequalities that removes a subset of the machine permutation symmetries. We show that applying the SOS hierarchy for $O_\varepsilon(1)$ rounds to this linear program reduces the integrality gap to $(1+\varepsilon)$. Our results suggest that the presence of symmetries were the main barrier preventing the SOS hierarchy to give tight relaxations.