Stochastic Programming

Chance-Constrained Optimization under Limited Distributional Information: A Review of Reformulations Based on Sampling and Distributional Robustness

  • Simge Küçükyavuz
  • Ruiwei Jiang
    • Categories Stochastic Programming Tags , , ,

    Chance-constrained programming (CCP) is one of the most difficult classes of optimization problems that has attracted the attention of researchers since the 1950s. In this survey, we focus on cases when only a limited information on the distribution is available, such as a sample from the distribution, or the moments of the distribution. We first … Read more

    Stochastic dual dynamic programming and its variants – a review

  • Christian Füllner
  • Steffen Rebennack
    • Categories Stochastic Programming Tags , , , , , , ,

    We provide a tutorial-type review on stochastic dual dynamic programming (SDDP), as one of the state-of-the-art solution methods for large-scale multistage stochastic programs. Since introduced about 30 years ago for solving large-scale multistage stochastic linear programming problems in energy planning, SDDP has been applied to practical problems from several fields and is enriched by various … Read more

    Heteroscedasticity-aware residuals-based contextual stochastic optimization

  • Rohit Kannan
  • Güzin Bayraksan
  • James R. Luedtke
    • Categories Robust Optimization, Stochastic Programming Tags , , , , , ,

    We explore generalizations of some integrated learning and optimization frameworks for data-driven contextual stochastic optimization that can adapt to heteroscedasticity. We identify conditions on the stochastic program, data generation process, and the prediction setup under which these generalizations possess asymptotic and finite sample guarantees for a class of stochastic programs, including two-stage stochastic mixed-integer programs … Read more

    Constrained and Composite Optimization via Adaptive Sampling Methods

  • Raghu Bollapragada
  • Richard H. Byrd
  • Jorge Nocedal
  • Yuchen Xie
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Stochastic Programming

    The motivation for this paper stems from the desire to develop an adaptive sampling method for solving constrained optimization problems in which the objective function is stochastic and the constraints are deterministic. The method proposed in this paper is a proximal gradient method that can also be applied to the composite optimization problem min f(x) … Read more

    A converging Benders’ decomposition algorithm for two-stage mixed-integer recourse models

  • Ward Romeijnders
  • Niels van der Laan
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

    We propose a new solution method for two-stage mixed-integer recourse models. In contrast to existing approaches, we can handle general mixed-integer variables in both stages, and thus, e.g., do not require that the first-stage variables are binary. Our solution method is a Benders’ decomposition, in which we iteratively construct tighter approximations of the expected second-stage … Read more

    Stochastic RWA and Lightpath Rerouting in WDM Networks

  • Maryam Daryalal
  • Merve Bodur
    • Categories Stochastic Programming, Telecommunications Tags , , ,

    In a telecommunication network, Routing and Wavelength Assignment (RWA) is the problem of finding lightpaths for incoming connection requests. When facing a dynamic traffic, greedy assignment of lightpaths to incoming requests based on predefined deterministic policies leads to a fragmented network that cannot make use of its full capacity due to stranded bandwidth. At this … Read more

    Kernel Distributionally Robust Optimization

  • Moritz Diehl
  • Wittawat Jitkrittum
  • Bernhard Schölkopf
  • Jia-Jie Zhu
    • Categories Robust Optimization, Statistics, Stochastic Programming Tags , , ,

    We propose kernel distributionally robust optimization (Kernel DRO) using insights from the robust optimization theory and functional analysis. Our method uses reproducing kernel Hilbert spaces (RKHS) to construct a wide range of convex ambiguity sets, including sets based on integral probability metrics and finite-order moment bounds. This perspective unifies multiple existing robust and stochastic optimization … Read more

    Moreau envelope of supremum functions with applications to infinite and stochastic programming

  • Pedro Pérez-Aros
  • Emilio Vilches
    • Categories Convex Optimization, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    In this paper, we investigate the Moreau envelope of the supremum of a family of convex, proper, and lower semicontinuous functions. Under mild assumptions, we prove that the Moreau envelope of a supremum is the supremum of Moreau envelopes, which allows us to approximate possibly nonsmooth supremum functions by smooth functions that are also the … Read more

    ALSO-X and ALSO-X+: Better Convex Approximations for Chance Constrained Programs

  • Nan Jiang
  • Weijun Xie
    • Categories Stochastic Programming

    In a chance constrained program (CCP), the decision-makers aim to seek the best decision whose probability of violating the uncertainty constraints is within the prespecified risk level. As a CCP is often nonconvex and is difficult to solve to optimality, much effort has been devoted to developing convex inner approximations for a CCP, among which … Read more

    Residuals-based distributionally robust optimization with covariate information

  • Rohit Kannan
  • Güzin Bayraksan
  • James R. Luedtke
    • Categories Robust Optimization, Stochastic Programming Tags , , , , , , ,

    We consider data-driven approaches that integrate a machine learning prediction model within distributionally robust optimization (DRO) given limited joint observations of uncertain parameters and covariates. Our framework is flexible in the sense that it can accommodate a variety of regression setups and DRO ambiguity sets. We investigate asymptotic and finite sample properties of solutions obtained … Read more