Présidents de session
Stochastic integer programming: Large-Scale and HPC-Based Computation
- Jean-Paul Watson (Lawrence Livermore National Laboratory)
Stochastic integer programming: Contributed talks
- Jeff Linderoth (University of Wisconsin-Madison)
Stochastic integer programming: Advancement in Stochastic Discrete Optimization
- Haoxiang Yang
Stochastic integer programming: Contributed talks
- Ricardo Fukasawa (University of Waterloo)
MIP-SPPY is software for stochastic programming that can run on a laptop, but uses MPI (message passing interface) to perform well on distributed memory computers. In this talk I will talk about high level changes to the user interface and low level changes to the way we manage interaction between algorithms running asynchronously in parallel.
Parallel implementations of scenario-based decomposition strategies are now scalable to thousands and millions of scenarios, thanks to advances in modeling systems (e.g.., Pyomo) and supporting meta-solvers (e.g., mpi-sppy). We describe challenges and their solution considering a large-scale power grid capacity expansion model, where scenarios represent individual days of weather. We discuss...
The Influence Maximization Problem (IMP), which seeks to identify influential nodes in a network to maximize expected information spread, is inherently stochastic and NP-hard—making it a natural candidate for quantum optimization methods. Classical approaches typically formulate IMP as a deterministic optimization problem (e.g., via sample average approximation), then encode it as a Quadratic...
We consider a two-stage stochastic decision problem where the decision-maker has the opportunity to obtain information about the distribution of the random variables X through a set of discrete actions that we refer to as probing. Specifically, probing allows the decision-maker to observe components of a random vector Y that is jointly-distributed with X. We propose a three-stage optimization...
The distributionally robust optimization (DRO) framework has emerged as a powerful approach for dealing with uncertainty. In the context of unit commitment, where demand uncertainty affects the right-hand side of constraints, we investigate a DRO approach based on the Wasserstein distance with the $L^2 $-norm. This approach can be addressed using Benders' decomposition as in the risk-neutral...
We address the Multi-Item Capacitated Lot-Sizing Problem (MCLSP) under decision-dependent uncertainty through a new probing-enhanced stochastic programming framework. In this setting, the demand is strongly correlated with another random vector and the decision-maker can strategically acquire partial information about uncertain demand by selecting component of the correlated random vector to...
In many real-life situations, such as medical product launches, energy investments, or the rollout of new policies, decision-makers must act before knowing exactly when critical information will become available. We develop new mathematical models that incorporate uncertainty about what will happen and when that uncertainty will resolve. Traditional decision-making tools assume fixed timelines...
Multistage stochastic mixed-integer programming (MS-MIP) is a powerful framework for sequential decision-making under uncertainty, yet its computational complexity poses significant challenges. This paper presents a convergent cutting-plane algorithm for solving MS-MIP with binary state variables. Our method exploits a geometric interpretation of the convex envelope of value functions and the...
Large-scale mixed-integer programs (MIPs) pose significant computational challenges due to their complexity, nonconvexity, and nonsmooth dual functions. Traditional decomposition methods often suffer from slow convergence, sensitivity to parameters, and instability. We propose Bundle-ADMM, a novel method combining the Alternating Direction Method of Multipliers (ADMM) and bundle techniques to...
Staged alert systems have been successfully implemented to minimize socioeconomic losses while avoiding overwhelming healthcare systems. Optimizing such systems can be formulated as a challenging two-stage stochastic mixed-integer programming problem with a discontinuous recourse function, where decision variables reside in a discrete space. Traditional simulation-based optimization techniques...
Solving large-scale stochastic optimization problems is challenging, especially when uncertainties are represented by a large number of scenarios. To tackle this, we introduce TULIP ("Two-step warm start method Used for solving Large-scale stochastic mixed-Integer Problems"), an efficient approach for solving two-stage stochastic (mixed) integer programs with an exponential number of...
We introduce a novel technique that generates Benders cuts from a corner relaxation of the target higher-dimensional polyhedron. Moreover, we develop a computationally efficient method to separate facet-defining inequalities for the epigraph
associated with this corner relaxation. By leveraging a known connection between arc-flow and path-flow formulations, we show that our method can recover...
We present a general price-and-cut procedure for two-stage stochastic integer programs with complete recourse, and first-stage binary variables. We propose a novel set of cutting planes that can close the optimality gap when added to the Dantzig-Wolfe decomposition master problem. It is shown to provide a finite exact algorithm for a number of stochastic integer programs, even in the
presence...
Optimization under uncertainty often relies on sampling the uncertainty to evaluate some expectations or to work with probability constraints. As the dimension of the random variable grows, the applicability of this approach diminishes, as achieving non-trivial precision through sampling may require too many samples to be practical.
We propose an alternative approach, where the probability...
