Discrete Optimization Talks (DOTs)

DOTs are virtual discrete optimization talks, organized by Aleksandr M. Kazachkov and Elias B. Khalil. To receive updates (and the Zoom link) for upcoming DOTs, please join our mailing list. If you would like to give a DOT, please fill out this form or email us.

Topics of interest include theoretical, computational, and applied aspects of integer and combinatorial optimization.

The format is two 30-minute talks each session. From January to April 2022, the seminars are scheduled for the last Friday of every month at 1:00 p.m. ET.

A special feature of DOTs is a social component. After a usual talk, you might grab a tea/coffee and chat with other attendees. Why not here too? Join us for some informal discussion after each DOT, as well as throughout the week on our Discord channel.

Videos of past DOTs are posted under Past Talks and can also be found on our YouTube Channel.

Join the mailing list to receive information about our upcoming seminars and how to virtually participate. Joining this list is necessary to receive the password for each DOT (usually sent on the Monday of the week in which there are DOTs). You may also wish to subscribe to our Google calendar (also available in ics format).

Upcoming Talks

Marc Pfetsch
Technische Universität Darmstadt

Presolving for Mixed-Integer Semidefinite Optimization

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.

Victor Zavala
University of Wisconsin-Madison

Solution of Large-Scale Supply Chain Models using Graph Sampling & Coarsening

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.

Danial Davarnia
Iowa State University

TBD


Michael Poss
Le Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier

TBD


Jorge Sefair
Arizona State University

TBD


Alexandra Newman
Colorado School of Mines

TBD


Swati Gupta
Georgia Tech

Learning Projections over Submodular Polytopes


Emma Frejinger
Université de Montréal

TBD