Discrete Optimization Day Schedule
10:15 – 10:30. Kickoff coffee and welcome
10:30 – 11:05. Gonzalo Muñoz: “Treewidth and Extension Complexity”
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”
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”
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”
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”
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 Marcos Goycoolea: “Large-scale Open Pit Mine Production-Scheduling”
The central concern of strategic mine planning is the construction of a tentative production schedule. This is a life-of-mine plan (20-50 years) specifying which part of a mineral deposit should be extracted, when it should be extracted, and how it should be extracted so as to maximize the net present value of the mining project (easily in the hundreds of millions of dollars).
Strategic mine planning is a complex optimization problem made daunting both by the great number of activities that must be scheduled in time and the great uncertainty concerning key economic, geological and operational parameters. Despite being a fairly standard problem regularly faced by mining projects throughout the world, it has received very little attention from the operations research community.
In this talk we describe our efforts modeling this problem as an RCPSP (Resource-Constrained Project Scheduling Problem), the integer-programming techniques we have been using to tackle them, and our experience working with Newmont and Barrick Gold, the world’s biggest gold producers.