Discrete Optimization Talks (DOTs)

Abstract: The Continuous Quadrant Penalty (CQP) approach provides a framework for addressing structured nonlinear optimization problems involving disjunctions. It relies on the introduction of a smooth, piecewise-quadratic penalty function, resulting in a continuous nonconvex optimization problem that provides a continuous-optimization alternative to classical mixed-integer formulations.
In this work, we address the sparse approximation problem. We propose an original CQP-based formulation and investigate its potential within a global optimization framework. Numerical experiments demonstrate the effectiveness of the proposed approach and highlight the potential of CQP formulations for solving sparse approximation problems.
Joint work with Marcel Mongeau

Bio: Sonia Cafieri is Professor at Ecole Nationale de l'Aviation Civile, University of Toulouse, France, where she heads the research group "Mathematical Optimization and Operations Research". She held positions at Ecole Polytechnique in Paris (collaborating with GERAD in Montréal), and at University of Naples (Italy). She received her PhD in Mathematics from University of Naples, and her Habilitation from University of Toulouse.  She has seated on the Managing Board of EUROPT group on continuous optimization (2014-2026), and co-leads the French nonlinear mathematical optimization group.  She serves on the editorial boards of ITOR, OR Forum, and EAAI. Her research interests include nonlinear continuous and mixed-integer optimization, with applications in engineering and air transportation.

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.