Stochastic Programming

Epi-convergence of Sample Averages of a Random Lower Semi-continuous Functional Generated by a Markov Chain and Application to Stochastic Optimization

  • John Birge
  • Arnab Sur
    • Categories Stochastic Programming Tags , , , , , ,

    The purpose of this article is to establish epigraphical convergence of the sample averages of a random lower semi-continuous functional associated with a Harris recurrent Markov chain with stationary distribution $\pi$. Sample averages associated with an ergodic Markov chain with stationary probability distribution will epigraphically converge from $\pi$-almost all starting points. The property of Harris … Read more

    A Unified Framework for Multistage and Multilevel Mixed Integer Linear Optimization

  • Suresh Bolusani
  • Stefano Coniglio
  • Ted K. Ralphs
  • Sahar Tahernejad
    • Categories (Mixed) Integer Linear Programming, Game Theory, Stochastic Programming Tags , , , , ,

    We introduce a unified framework for the study of multilevel mixed integer linear optimization problems and multistage stochastic mixed integer linear optimization problems with recourse. The framework highlights the common mathematical structure of the two problems and allows for the development of a common algorithmic framework. Focusing on the two-stage case, we investigate, in particular, … Read more

    A Framework for Generalized Benders’ Decomposition and Its Application to Multilevel Optimization

  • Suresh Bolusani
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Game Theory, Stochastic Programming Tags , , ,

    We describe an algorithmic framework generalizing the well-known framework originally introduced by Benders. We apply this framework to several classes of optimization problems that fall under the broad umbrella of multilevel/multistage mixed integer linear optimization problems. The development of the abstract framework and its application to this broad class of problems provides new insights and … Read more

    On Linear Optimization over Wasserstein Balls

  • Daniel Kuhn
  • Wolfram Wiesemann
  • Man-Chung Yue
    • Categories Robust Optimization, Stochastic Programming Tags , , , ,

    Wasserstein balls, which contain all probability measures within a pre-specified Wasserstein distance to a reference measure, have recently enjoyed wide popularity in the distributionally robust optimization and machine learning communities to formulate and solve data-driven optimization problems with rigorous statistical guarantees. In this technical note we prove that the Wasserstein ball is weakly compact under … Read more

    A Framework for Adaptive Open-pit Mining Planning under Geological Uncertainty

  • Margaret Armstrong
  • Tito Homem-de-Mello
  • Guido Lagos
  • Tomas Lagos
  • Denis Saure
    • Categories Dynamic Programming, Scheduling, Stochastic Programming Tags , , , ,

    Mine planning optimization aims at maximizing the profit obtained from extracting valuable ore. Beyond its theoretical complexity (the open-pit mining problem with capacity constraints reduces to a knapsack problem with precedence constraints, which is NP-hard), practical instances of the problem usually involve a large to very large number of decision variables, typically of the order … Read more

    A new interior-point approach for large two-stage stochastic problems

  • Jordi Castro
  • Paula de la Lama
    • Categories Linear, Cone and Semidefinite Programming, Optimization Software Benchmark, Stochastic Programming

    Two-stage stochastic models give rise to very large optimization problems. Several approaches have been devised for efficiently solving them, including interior-point methods (IPMs). However, using IPMs, the linking columns associated to first-stage decisions cause excessive fill-in for the solution of the normal equations. This downside is usually alleviated if variable splitting is applied to first-stage … Read more

    Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization

  • Lin Xiao
  • Junyu Zhang
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , ,

    We consider minimization of composite functions of the form $f(g(x))+h(x)$, where $f$ and $h$ are convex functions (which can be nonsmooth) and $g$ is a smooth vector mapping. In addition, we assume that $g$ is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose … Read more

    Inexact cuts in SDDP applied to multistage stochastic nondifferentiable problems

  • Vincent Guigues
  • Renato D.C. Monteiro
  • Benar Fux Svaiter
    • Categories Stochastic Programming

    In [13], an Inexact variant of Stochastic Dual Dynamic Programming (SDDP) called ISDDP was introduced which uses approximate (instead of exact with SDDP) primal dual solutions of the problems solved in the forward and backward passes of the method. That variant of SDDP was studied in [13] for linear and for differentiable nonlinear Multistage Stochastic … Read more

    Dual Decomposition of Two-Stage Distributionally Robust Mixed-Integer Programming under the Wasserstein Ambiguity Set

  • Kibaek Kim
    • Categories (Mixed) Integer Linear Programming, Robust Optimization, Stochastic Programming Tags , ,

    We develop a dual decomposition of two-stage distributionally robust mixed-integer programming (DRMIP) under the Wasserstein ambiguity set. The dual decomposition is based on the Lagrangian dual of DRMIP, which results from the Lagrangian relaxation of the nonanticipativity constraints and min-max inequality. We present two Lagrangian dual problem formulations, each of which is based on different principle. We show … Read more

    A Model of Supply-Chain Decisions for Resource Sharing with an Application to Ventilator Allocation to Combat COVID-19

  • Sanjay Mehrotra
  • Hamed Rahimian
  • Masoud Barah
  • Fengqiao Luo
  • Karolina Schantz
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Stochastic Programming Tags , , , , ,

    We present a stochastic optimization model for allocating and sharing a critical resource in the case of a pandemic. The demand for different entities peaks at different times, and an initial inventory for a central agency is to be allocated. The entities (states) may share the critical resource with a different state under a risk-averse … Read more