------------------------------------------------------------
DOTs: Discrete Optimization Talks
https://talks.discreteopt.com/
A Virtual Seminar Series
By the Mixed Integer Programming Society
------------------------------------------------------------
We hope you join us for the next DOT session this Friday, September 11, 2026 at 12:00 ET (Sign up for zoom links). We will have two half-hour talks (details below) followed by an open, informal discussion.
------------------------------------------------------------
Speaker: Connor Johnston (University of Florida)
Title: The many facets of simple disjunctions
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.
------------------------------------------------------------
Speaker: Jingye Xu (Georgia Tech)
Title: Asymptotically Strong Dual of Smooth Nonconvex Problems: A Smooth Shapley–Folkman Perspective
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.
------------------------------------------------------------
Speaker: Akul Bansal (Northwestern University)
Title: Normalization of ReLU Dual for Cut Generation in Stochastic Mixed-Integer Programs
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.
------------------------------------------------------------
Hope to see you there,
Margarita Castro (Pontificia Universidad Católica de Chile)
Silvia Di Gregorio (Université Sorbonne Paris Nord)
Aleksandr Kazachkov (University of Florida)
------------------------------------------------------------
For more information, including links to past talks, visit our website: https://talks.discreteopt.com. If you have any questions, email us at talks@discreteopt.com.