Discrete Optimization Talks (DOTs)

Abstract: TBA

Bio: TBA

Abstract: We present an output sensitive polynomial time algorithm for enumerating every facet of the disjunctive hull for a simple disjunction. The algorithm is an augmented version of network simplex over the reverse polar set which visits every neighboring vertex, and which can avoid degeneracy. Additionally, the algorithm produces the facet defining inequalities in order of depth as measured by a min-max optimization problem.

Bio: Connor Johnston is a 4th year PhD student at the University of Florida advised by Aleksandr Kazachkov.

Abstract: In convex geometry, the Shapley–Folkman Lemma asserts that the nonconvexity of a Minkowski sum of $n$-dimensional nonconvex sets does not accumulate once the number of summands exceeds the dimension $n$, and thus the sum becomes approximately convex. Originally published by Starr in the context of quasi-equilibrium in nonconvex market models in economics, the lemma has since found widespread use in optimization, particularly for estimating the duality gap of the Lagrangian dual of separable nonconvex problems.

Given its foundational nature, we pose the following geometric question: \emph{Is it possible for the nonconvexity of the Minkowski sum of $n$-dimensional nonconvex sets to vanish as the number of summands increases, under some general conditions?} We answer this affirmatively. First, we provide a new and elementary geometric proof of the Shapley–Folkman Lemma based on the facial structure of the convex hull of each set. This leads to an unconditional improvement over the classical error bound derived from the lemma.

Building on this new geometric perspective, we further show that when most of the sets satisfy a certain ``local smoothness'' condition, their Minkowski sum converges directly to a convex set, with a vanishing nonconvexity measure. In optimization, this implies that the Lagrangian dual of block-structured smooth nonconvex problems—with potentially additional sparsity constraints—is asymptotically tight under mild assumptions, which contracts non-vanishing duality gap obtained via classical Shapley-Folkman Lemma.

Bio: Jingye Xu is a fifth Ph.D. candidate in Algorithms, Combinatorics, and Optimization at Georgia Tech, advised by Santanu Dey and Diego Cifuentes. His research focuses on optimization, with particular interests in nonconvex duality and probabilistic techniques for optimization.

Abstract: We study the Rectified Linear Unit (ReLU) dual, an existing dual formulation for stochastic programs that reformulates non-anticipativity constraints using ReLU functions to generate tight, non-convex, and mixed-integer representable cuts. While this dual reformulation guarantees convergence with mixed-integer state variables, it admits multiple optimal solutions that can yield weak cuts. To address this issue, we propose normalizing the dual in the extended space to identify solutions that yield stronger cuts. We prove that the resulting normalized cuts are tight and Pareto-optimal in the original state space. We further compare normalization with existing regularization-based approaches for handling dual degeneracy and explain why normalization offers key advantages. In particular, we show that normalization can recover any cut obtained via regularization, whereas the converse does not hold. Computational experiments demonstrate that the proposed approach outperforms existing methods by consistently yielding stronger cuts and reducing solution times on harder instances.

Bio: Akul Bansal recently completed his Ph.D. in Industrial Engineering and Management Sciences at Northwestern University, where he was advised by Prof. Simge Küçükyavuz. His research focuses on mixed-integer, large-scale, and stochastic optimization. Prior to joining Northwestern, he earned a Master’s degree in Operations Research from IIT Bombay, India, and a Bachelor’s degree in Mathematics from the University of Delhi.

Abstract: This presentation addresses linear Chance-Constrained Stochastic Problems (CCSPs) with f inite support. CCSPs are first presented in an intuitive manner. Subsequently, we discuss the computational challenges inherent to these problems, specifically the nonconvex structure of the feasible region and the limitations of the standard big-M reformulation. These challenges motivate the use of branch-and-cut approaches.
To this end, we provide a short review on existing families of valid inequalities, such as quantile inequalities (W. Xie and S. Ahmed, 2018) and mixing inequalities (J. Luedtke, S. Ahmed, and G. L. Nemhauser, 2010). This background sets the stage for the primary contribution of this work: a new class of valid inequalities termed multi-disjunctive inequalities. We construct these inequalities by exploiting a previously unknown disjunctive property inherent to the mathematical formulation of CCSPs. Theoretical analysis reveals that there exists small size instances for which the closure of these multi-disjunctive inequalities constitutes a proper subset of the closure generated by previously proposed families.
We perform numerical experiments within a pure cutting-plane framework to compare the closures obtained by enumerating all violated valid inequalities. The results demonstrate that multi-disjunctive inequalities significantly strengthen the continuous relaxation of the considered CCSPs compared to existing quantile and mixing-set inequalities. Furthermore, we evaluate the performance of these inequalities embedded within a branch-and-cut framework. Our resultsindicate that the proposed approach significantly outperforms existing methods on both standard literature instances and newly generated instances designed to be computationally challenging. 

Bio: Marius Roland is a Permanent Research Associate (Chargé de Recherche) in the INOCS Team at the Inria Lille, a position he has held since January 2025. Previously, he served as a Postdoctoral Researcher at Polytechnique Montreal from June 2022 to November 2024, working within the SCALE AI Chair in Data-Driven Supply Chains under the advisement of Prof. Thibaut Vidal. He earned his Ph.D. in Mathematics from Universität Trier in Germany under supervision of Prof. Martin Schmidt. Currently his research interests are: optimization under uncertainty, mixed-integer programming, combinatorial optimization, and machine learning.

Abstract: We study the convex hull of a set of simple disjunctions (defined by a single linear inequality) over the nonnegative orthant. This setting lies between special closed-form cuts such as Gomory fractional cuts, and the general-purpose cut‑generating linear program (CGLP) of Balas. Building on earlier work of Sen and Sherali and of Kim, Richard, and Tawarmalani, we introduce a geometric perspective on generating facet‑defining inequalities for the aforementioned convex hull. We present both theoretical and algorithmic results regarding generating facets of the convex hull. Joint work with Connor Johnston, Aleksandr Kazachkov, and Diego Moran Ramirez.

Bio: Chen is an associate professor in the Integrated Systems Engineering department at the Ohio State University and core faculty member of the Sustainability Institute. His research involves computational optimization, especially MIP/MIP-inspired approaches. Applications include power systems, machine learning, logistics, and manufacturing.

Abstract: In this talk, we focus on mixed integer nonlinear problems with univariate piecewise convex inequalities. We generalize the classic formulation for piecewise linear functions to the case of piecewise convex ones and strengthen them through perspective reformulation. Moreover, we compare the different formulations and we show theoretically that they are not equivalent, contrarily to what has been shown in the literature for the piecewise linear formulations. Computational results on two classes of problems are presented, confirming the theoretical findings. 

Bio: Claudia D'Ambrosio is a senior researcher at CNRS and a professor at École Polytechnique, where she is based at the Computer Science Laboratory (LIX). Her research focuses on the theoretical and computational aspects of mixed integer nonlinear programming, with applications spanning water network design, hydro scheduling, aircraft deconfliction, and urban mobility.

Claudia received her PhD in Automatic Control and Operations Research from the University of Bologna in 2009, under the supervision of Andrea Lodi, and received her habilitation in France in 2018. Her PhD was recognized with the EURO Doctoral Dissertation Award in 2010. She also received the 2nd Robert Faure ROADEF prize in 2015 and was nominated to the CNRS bronze medal in 2018. Her research has been funded by various sources; recently she held the "Integrated Urban Mobility"chair sponsored by Uber from 2019 to 2023.

Abstract: Dantzig-Wolfe (DW) decomposition is a well-known technique in mixed-integer programming (MIP) for decomposing and convexifying constraints to obtain potentially strong dual bounds. We investigate cutting planes that can be derived using the DW decomposition algorithm and show that these cuts can provide the same dual bounds as DW decomposition. More precisely, we generate one cut for each DW block, and when combined with the constraints in the original formulation, these cuts imply the objective function cut one can simply write using the DW bound. This approach typically leads to a formulation with lower dual degeneracy that consequently has a better computational performance when solved by standard MIP solvers in the original space. We also discuss how to strengthen these cuts to improve the computational performance further. 

Joint work with Rui Chen, and Andrea Lodi

Bio: Oktay Günlük is a Gary C. Butler Family Professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Tech. Prior to joining Georgia Tech he was a professor of practice in the School of Operations Research and Information Engineering at Cornell University and the manager of the Mathematical Optimization and Algorithms group at IBM Research. He has also spent three years as a researcher in the Operations Research group in AT&T Labs. At both of these industrial labs, in addition to basic research in mathematical optimization, he has worked on various large-scale applied optimization projects for internal and external customers. He holds B.S. and M.S. degrees from Boğaziçi University in Turkey and a Ph.D. degree from Columbia University. 

Oktay Günlük's main research interests are related to theoretical and computational aspects of discrete optimization problems, mainly in the area of integer programming. In particular, his main body of work is in the area of cutting planes for mixed-integer sets. In addition, some of his current research work includes (1) developing integer programming-based approaches to classification and clustering problems in machine learning, and (2) qubit assignment and routing for quantum computers.

He currently serves as the Editor-in-Chief of Informs Journal on Optimization.