Discrete Optimization Talks (DOTs)

Abstract: The goal of this talk is to provide a discussion and evaluation of presolving methods for mixed-integer semidefinite programs. We generalize methods from the mixed-integer linear case and introduce new methods that depend on the semidefinite condition. The considered methods include adding linear constraints, bounds relying on 2 by 2 minors of the semidefinite constraints, bound tightening based on solving a semidefinite program with one variable, and scaling of the matrices in the semidefinite constraints. Tightening variable bounds can also be used in a node presolving step. Along the way, we briefly discuss the solution of semidefinite programs with one variable using a semismooth Newton method and the convergence of iteratively applying bound tightening. We then provide a computational comparison of the different presolving methods, demonstrating their effectiveness with an improvement in running time of about 22 % on average. The impact depends on the instance type and varies across the methods.

Joint work with Frederic Matter (TU Darmstadt)

Short bio: Marc Pfetsch has been a full professor at TU Darmstadt, Germany, since 2012. Beforehand, he was professor at TU Braunschweig, Germany, from 2008 to 2012. He passed the habilitation at TU Berlin (2008), Germany, holds a Ph. D. also from TU Berlin (2002), and a Diploma in mathematics from the University of Heidelberg, Germany. He is an area editor of Operations Research Letters and on the editorial board of INFORMS Journal on Computing as well as Mathematical Programming Computation. He contributed to the project on evaluating gas network capacities, which won the EURO Excellence in Practice Award for 2016. He is one of the developers of the frameworks SCIP (www.scipopt.org) and SCIP-SDP (http://www.opt.tu-darmstadt.de/scipsdp/). His research interests include mixed-integer nonlinear programming (mixed-integer semidefinite programming, in particular), symmetries in integer programming and compressed sensing.

Abstract: We present a graph sampling and coarsening scheme (gSC) for computing lower and upper bounds for large-scale supply chain models. An edge sampling scheme is used to build a low-complexity problem that is used to finding an approximate (but feasible) solution for the original model and to compute a lower bound (for a maximization problem). This scheme is similar in spirit to the so-called sample average approximation scheme, which is widely used for the solution of stochastic programs. A graph coarsening (aggregation) scheme is used to compute an upper bound and to estimate the optimality gap of the approximate solution. The coarsening scheme uses node sampling to select a small set of support nodes that are used to guide node/edge aggregation and we show that the coarsened model provides a relaxation of the original model and a valid upper bound. We provide numerical evidence that gSC can yield significant improvements in solution time and memory usage over state-of-the-art solvers. Specifically, we study a supply chain design model (a mixed-integer linear program) that contains over 38 million variables and show that gSC finds a solution with an optimality gap of <0.5% in less than 22 minutes.

Biosketch: Victor M. Zavala is the Baldovin-DaPra Professor in the Department of Chemical and Biological Engineering at the University of Wisconsin-Madison and a computational mathematician in the Mathematics and Computer Science Division at Argonne National Laboratory. He holds a B.Sc. degree from Universidad Iberoamericana and a Ph.D. degree from Carnegie Mellon University, both in chemical engineering. He is on the editorial board of the Journal of Process Control, Mathematical Programming Computation, and Computers & Chemical Engineering. He is a recipient of NSF and DOE Early Career awards and of the Presidential Early Career Award for Scientists and Engineers. His research interests include computational modeling, statistics, control, and optimization.