Session: Special Session in Honor of Suvrajeet Sen: Stochastic Mixed-Integer Programming
Chair: Lewis Ntaimo
Cluster: Optimization Under Uncertainty and Data-driven Optimization
Talk 1: On Disjunctive Decomposition for Stochastic Mixed-Integer Programming: A Reflection on Algorithm Development and Applications
Speaker: Lewis Ntaimo
Abstract: Two-stage stochastic mixed-integer programming (SMIP) involves making discrete decisions in the face of future uncertainty and has many applications in science and engineering. However, solving SMIP is very challenging mainly due to its nonconvexity and large-scale nature. In this talk, we reflect on the development of disjunctive decomposition for SMIP initiated by Suvrajeet Sen. Disjuctive decomposition relies on generating disjunctive cutting planes that are shared among scenarios to sequentially convexify the nonconvex expected recourse function. We review the basic theory and derivation of a class of disjunctive decomposition algorithms, and illustrate the algorithms using simple numerical examples. Finally, we discuss computer implementation and application of the algorithms towards solving standard SMIP problems.
Talk 2: Integer L-Shaped and Lagrangian Cuts Revisited: A Unified Perspective
Speaker: Simge Kucukyavuz
Abstract: We study cut generation methods for solving stochastic mixed-integer programs, focusing on Lagrangian cuts obtained by relaxing non-anticipativity constraints in the Lagrangian dual. The Lagrangian dual admits multiple optimal solutions, and not all solutions lead to cuts with strong approximations. Surprisingly, we establish that integer L-shaped cuts, which are easy to obtain but often weak, belong to the class of Lagrangian cuts—typically considered stronger, though computationally harder to derive. Second, we study alternative duals that address convergence issues of the classical dual by reformulating the non-anticipativity constraints. While these variants can achieve convergence with mixed-integer state variables, they may also suffer from multiple optimal solutions that may produce weak cuts. To address this, we propose a normalization of the dual formulations to identify solutions that lead to strong cuts. We conclude with a summary of our computational experiments that compare the proposed methods.
Talk 3: A Stochastic Diversion Path Problem
Speaker: Cole Smith
Abstract: We examine a stochastic network optimization problem in which the goal is to modify arc lengths so that a specified path (the “diversion path”) will be optimal with sufficiently high probability. Given modification costs for each arc in the network, the objective in a deterministic form of the problem would be to minimize the sum of modification costs needed to guarantee that the diversion path is optimal. In the stochastic version, each arc length is an independent, uniformly-distributed random variable. (The lower bound on the arc lengths is nonnegative.) Given a parameter 0 < tau
