Discrete Optimization Talks (DOTs)

TBA

TBA

TBA

TBA

Abstract: A famous conjecture of Goemans on single-source unsplittable flows states that one can turn any fractional flow into an unsplittable one of no higher cost, while increasing the load on any arc by at most the maximum demand. Despite extensive work on the topic, only limited progress has been made. Recently, Morell and Skutella suggested an alternative conjecture, stating that one can turn any fractional flow into an unsplittable one without changing the load on any arc by more than the maximum demand.

We show that their conjecture implies Goemans' conjecture (with a violation of twice the maximum demand). To this end, we generalize a technique of Linhares and Swamy, used to obtain a low-cost chain-constrained spanning tree from an algorithm without cost guarantees. Whereas Linhares and Swamy's proof relies on Langrangian duality, we provide a very simple elementary proof of a generalized version, which we hope to be of independent interest.

This is joint work with Chaitanya Swamy, Vera Traub, Laura Vargas Koch, Rico Zenklusen.

Bio: Vera Traub is an Associate Professor at ETH Zurich. Her main areas are Combinatorial Optimization and Approximation Algorithms.

Prior to joining ETHZ, she has been a Professor at the University of Bonn and a Postdoc at ETH Zurich. She obtained her PhD in 2020 from the University of Bonn. For her research she has received several awards, including an EATCS Distinguished Dissertation Award, a Maryam Mirzakhani New Frontiers Prize, and a Heinz Maier-Leibnitz Prize.

Abstract: Humanitarian organizations must plan and operate two distinct aid delivery services on a shared network for responding to both ongoing (OG) demand in a reliable and cost-efficient way and sudden-onset (SO) emergencies rapidly. This paper studies the joint planning problem and presents scenario-informed, data-driven delivery service recommendations that preserve managerial interpretability. We develop an integrated two-stage model to jointly plan OG and SO services over a shared network under common operational constraints. In the first stage, the model optimizes over which warehouses to open and SO-dedicated safety stock levels; in the second stage, operations over the network are decided for serving the known OG demand and the SO requests revealed over time. To support planning under limited historical data, a deep-learning pipeline labels historical demand as OG or SO and generates realistic, diverse demand scenarios that preserve temporal and spatial structure while introducing controlled variation. Rather than solving a single large stochastic program, we solve the model per scenario to build a reusable decision library and reveal how first-stage designs vary with scenario conditions. From this library, we derive (i) a baseline recommendation using only historical scenarios and (ii) a pattern-based recommendation based on the frequency of first-stage decision patterns over all scenarios generated. Using a pre-specified demand-feature set, we train a feature-to-decision recommender that maps scenario features to representative first-stage designs, enabling fast, interpretable, scenario-specific guidance without re-solving the optimization model. Computational experiments show that, relative to the historical baseline, pattern-based recommendation improves per unit cost efficiency and increases early fulfillment and service coverage. Feature importance analysis from feature-to-decision recommender indicates that total sudden-onset demand and the budget constraints are the primary decision drivers, with commodity compositions, seasonality, and geography refining the recommended design.

Bio: Dr. Özlem Ergun is a College of Engineering Distinguished Professor in Mechanical and Industrial Engineering at Northeastern University. Dr. Ergun’s research focuses on design and management of large-scale and decentralized networks. She has applied her work on network design, management, and resilience to problems arising in many critical systems including transportation, pharmaceuticals, and healthcare.  She has worked with organizations that respond to emergencies and humanitarian crises around the world, including USAID, UN WFP, UNHCR, IFRC, OXFAM America, CARE USA, FEMA, USACE, CDC, AFCEMA, and MedShare International.  Recently, Dr. Ergun partnered with the Massachusetts’ Executive Office of Elder Affairs (EOEA) to help match qualified medical professionals to Long Term Care facilities with open positions around the state as part of the state’s response efforts to COVID19. Dr. Ergun also served as a member of the National Academies Committee on Building Adaptable and Resilient Supply Chains after Hurricanes Harvey, Irma, and Maria and the National Academies Committee on Security of America’s Medical Supply Chain. She was the President of INFORMS Section on Public Programs, Service and Needs in 2013 and is an INFORMS fellow. She served as the Area Editor at the Operations Research journal for Policy Modeling Public Sector Area and currently serves as the Department co-Editor at MSOM journal for Environment, Health and Society Department. 

Prior to joining Northeastern Dr. Ergun was the Coca-Cola Associate Professor in the School of Industrial and Systems Engineering at Georgia Institute of Technology, where she also co-founded and co-directed the Health and Humanitarian Systems Research Center at the Supply Chain and Logistics Institute.  She received a B.S. in Operations Research and Industrial Engineering from Cornell University in 1996 and a Ph.D. in Operations Research from the Massachusetts Institute of Technology in 2001.

Abstract:
Network interdiction involved expending a limited budget destroying infrastructure in a network to maximally reduce some functionality of the network. Typically, the network is owned by an adversary, and we are trying to interdict their use of the network. We introduce a novel variant of the maximum flow interdiction problem in which the adversary is using a network we own. We wish to reclaim our network and still have it as functional as possible for our goals. To model this situation we assume we have a set of  "bad pairs,’" which are pairs of nodes the adversary has taken over. The adversary needs flows above a minimum threshold between bad pairs to achieve its goal. We are also given a set of "good pairs,'' which represent the functionality of our own network we wish to preserve after the interdiction. We are required to maintain flow above a minimum threshold between good pairs. Our objective it so maximize the number of bad pairs whose residual flow capacity drops below their functional threshold. We formulate this problem as a mixed-integer linear program (MILP) and also introduce a fast and effective MILP-based primal heuristic motivated by a previous pseudo-approximation for classic max-flow interdiction. We show the accuracy and computational benefits of the heuristic relative to the MILP formulation on a computational study on graph instances from the SNAP and DIMACS repositories.

Bio:
Emma Johnson is a Senior Member of Technical Staff in the Operations Research and Computational Analysis department at Sandia National Laboratories. She has a Ph.D. in Operations Research from Georgia Institute of Technology (2021) and expertise in discrete optimization, particularly mixed-integer linear programming, disjunctive programming, and multilevel optimization. Her research focuses mainly on developing solution methods for large-scale discrete optimization problems in scheduling, logistics, and system design. In addition, she is a developer of Pyomo, an open-source Python package for math programming, and lead developer of its subpackage supporting Generalized Disjunctive Programming.

Abstract:
In this talk, we investigate a robust bilevel network interdiction problem motivated by applications in human trafficking disruption. In this problem, the follower, who we assume to be rational, will solve a minimum cost network flow problem on a network whose arcs may be interdicted/removed by the leader. The leader, who interdicts the network, optimizes their own objective computed using the optimal flow obtained in the follower’s problem. We consider the case where the leader does not know the follower’s cost vector, but only that it belongs to a given uncertainty set, while the follower has complete knowledge about their own parameters. We present a column-and-constraint generation (C&CG) method to solve the optimistic version of this problem. We discuss the difficulties in solving the standard subproblem from the C&CG method and propose a method to solve the subproblem by exploiting the structure of the uncertainty set. We demonstrate the effectiveness of the proposed approach through computational experiments with synthetic human trafficking networks.

Bio:
Dr. Yongjia Song is currently an associate professor in the Department of Industrial Engineering at Clemson University. Dr. Song received his Ph.D. degree in industrial and systems engineering from University of Wisconsin-Madison in 2013. Dr. Song’s research interests include optimization under uncertainty, integer programming, and applications of optimization in transportation and logistics, networks, and energy systems. Dr. Song is a recipient of the National Science Foundation CAREER award in 2021, and his research has been supported by several federal funding agencies, including the National Science Foundation (NSF), Department of Energy (DOE), Office of Naval Research (ONR), among others. 

Abstract:

In this talk, we study cut-generating functions in the setting of the Gomory--Johnson group relaxations for integer programming. We address an open question: whether every facet (extreme function) for a finite cyclic group relaxation injects into the space of extreme functions for the infinite group problem.

We give a variant of the Basu--Hildebrand--Molinaro approximation theorem [IPCO 2016] for continuous minimal functions of the infinite group problem. Specifically, we show that any piecewise linear minimal function with rational breakpoints in 1/qZ and rational values at these breakpoints can be approximated by piecewise linear two-slope extreme functions while preserving all function values on 1/qZ: a feature not guaranteed by the earlier construction. As a corollary, every extreme function for the finite group problem on 1/qZ is the restriction of a continuous piecewise linear two-slope extreme function for the infinite group problem, with breakpoints on a refinement 1/(Mq)Z. Combined with Gomory’s master theorem, this establishes that the infinite group problem indeed serves as the correct master problem for facets of one-row group relaxations.

This is a joint work with Matthias Koeppe.

Bio:

Yuan Zhou is an Associate Professor in the Department of Mathematics at the University of Kentucky. She earned her Diplôme d’Ingénieur from École Centrale Paris and a master’s degree in Applied Mathematics (Actuariat) from Université Paris-Dauphine in 2012. She received her Ph.D. in Applied Mathematics from the University of California, Davis in 2017, under the supervision of Matthias Köppe. Her research focuses on polyhedral geometry and cutting planes, particularly cut-generating functions for integer programming.

Abstract:
Let $A ∈ \mathbb{Z}^{m \times n}$ be an integer matrix with components bounded by $\Delta$ in absolute value. Cook et al. (1986) have shown that there exists a universal matrix $B ∈ \mathbb{Z}^{m' ×n}$ with the following property:  For each  $b ∈ \mathbb{Z}^m$, there exists $t \in \mathbb{Z}^{m'}$ such that the integer hull of the polyhedron $P = \{ x ∈ \mathbb{R}^n ： Ax \leq b\}$ is described by $P_I = \{ x \in \mathbb{R}^n ： Bx \leq t\}$. Our main result is that $t$ is an affine function of $b$ as long as $b$ is from a fixed equivalence class of the lattice $D \cdot \mathbb{Z}^m$. Here $D \in \setN$ is a number that depends on $n$ and $\Delta$ only. Furthermore, $D$ as well as the matrix $B$ can be computed in time depending on $\Delta$ and $n$ only. An application of this result is the solution of an open problem posed by Cslovjecsek et al.~(SODA 2024) concerning the complexity of 2-stage-stochastic integer programming problems.  The main tool of our proof is  the  classical theory of Chv\'atal-Gomory cutting planes and the elementary closure of rational polyhedra.
This is joint work with Friedrich Eisenbrand.

Bio:
Thomas Rothvoss is Professor in the Paul G. Allen School of Computer Science & Engineering and the Department of Mathematics
at the University of Washington. His research interests are approximation algorithms, theoretical integer programming and convex geometry. He received the 2018 Delbert Ray Fulkerson Prize and the 2023 Goedel Prize. His research is supported by an Alfred P. Sloan Research Fellowship (2015), a David & Lucile Packard Foundation Fellowship (2016)  as well as an NSF CAREER Award (2016).

Abstract:
We study a class of decision-making problems under uncertainty, where the planner hedges against the worst-case realization in an integer uncertainty set that has a functional dependence on the decisions of the planner. We propose three methods to reformulate and solve these problems: the first is based on a single-level semi-infinite reformulation, where the dependence of the uncertainty on the decisions is modeled with auxiliary binary variables; the second is based on a single-follower bilevel reformulation; and the third one is a multiple-follower bilevel reformulation where each robust constraint is associated with a follower. We provide additional enhancements to strengthen the linear programming relaxation of the single-level formulation and propose a column and constraint generation algorithm to solve it. The multiple-follower bilevel formulation is further transformed into a multicommodity flow single-level mixed-integer problem by exploiting recent advancements in decision diagrams. We perform numerical experiments that show the column and constraint generation algorithm can solve small- and medium- scale instances within a few minutes. This method is outperformed by the multicommodity flow formulation when dealing with problems with a single robust constraint. We complement our experiments by using the column and constraint generation algorithm to solve a constrained shortest path problem with maintenance decisions and uncertain arc failures. The proposed method can solve instances of this problem with hundreds of nodes and thousands of arcs in a few minutes.

Bio:
Leonardo Lozano is an associate professor in the Operations, Business Analytics & Information Systems Department at the University of Cincinnati. He received his B.Sc. degree from Universidad de los Andes, his M.Sc. degree from University of Florida, and his Ph.D. degree from Clemson University. His research focuses on exact algorithms for discrete optimization and has been published in Operations Research, Mathematical Programming, Transportation Science, Networks (Glover-Klingman 2020 best paper award), and INFORMS Journal on Computing, among others. His research has been funded by the Office of Naval Research, the Air Force Office of Scientific Research, and Google.