Stochastic Programming

The Surprising Performance of Random Partial Benders Decomposition

  • Jean Pauphilet
  • Yupeng Wu
    • Categories (Mixed) Integer Linear Programming, Integer Programming, Stochastic Programming Tags ,

    Benders decomposition is a technique to solve large-scale mixed-integer optimization problems by decomposing them into a pure-integer master problem and a continuous separation subproblem. To accelerate convergence, we propose Random Partial Benders Decomposition (RPBD), a decomposition method that randomly retains a subset of the continuous variables within the master problem. Unlike existing problem-specific approaches, RPBD … Read more

    Optimal participation of energy communities in electricity markets under uncertainty. A multi-stage stochastic programming approach

  • Albert Solà Vilalta
  • Ignasi Mañé Bosch
  • F.-Javier Heredia
    • Categories Energy, Stochastic Programming Tags , , ,

    We propose a multi-stage stochastic programming model for the optimal participation of energy communities in electricity markets. The multi-stage aspect captures the different times at which variable renewable generation and electricity prices are observed. This results in large-scale optimization problem instances containing large scenario trees with 34 stages, to which scenario reduction techniques are applied. … Read more

    On vehicle routing problems with stochastic demands — Generic disaggregated integer L-shaped formulations

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Branch and Cut Algorithms, Stochastic Programming, Transportation Tags , , ,

    We study the vehicle routing problem with stochastic demands (VRPSD), an important variant of the classical capacitated vehicle routing problem in which customer demands are modeled as random variables. We develop the first algorithm for the VRPSD in the case where the demands are given by an empirical probability distribution of scenarios — a data-driven … Read more

    MDP modeling for multi-stage stochastic programs

  • David P. Morton
  • Oscar Dowson
  • Bernardo K. Pagnoncelli
    • Categories Stochastic Programming Tags , , , ,

    We study a class of multi-stage stochastic programs, which incorporate modeling features from Markov decision processes (MDPs). This class includes structured MDPs with continuous state and action spaces. We extend policy graphs to include decision-dependent uncertainty for one-step transition probabilities as well as a limited form of statistical learning. We focus on the expressiveness of … Read more

    An extension of an interior-point method to include risk aversion in large-scale multistage stochastic optimization

  • Jordi Castro
  • Laureano F. Escudero
  • Juan F. Monge
    • Categories Linear Programming, Stochastic Programming Tags , , , ,

    In the earlier paper “On solving large-scale multistage stochastic optimization problems with a new specialized interior-point approach, European Journal of Operational Research, 310 (2023), 268–285” the authors presented a novel approach based on a specialized interior-point method (IPM) for solving (risk neutral) large-scale multistage stochastic optimization problems. The method computed the Newton direction by combining … Read more

    Approximating value functions via corner Benders’ cuts

  • Matheus Jun Ota
  • Ricardo Fukasawa
  • Aleksandr M. Kazachkov
    • Categories Branch and Cut Algorithms, Integer Programming, Stochastic Programming Tags , , , , ,

    We introduce a novel technique to generate Benders’ cuts from a conic relaxation (“corner”) derived from a basis of a higher-dimensional polyhedron that we aim to outer approximate in a lower-dimensional space. To generate facet-defining inequalities for the epigraph associated to this corner, we develop a computationally-efficient algorithm based on a compact reverse polar formulation … Read more

    Approximating inequality systems within probability functions: studying implications for problems and consistency of first-order information

  • Wim van Ackooij
  • Pedro Pérez-Aros
  • David Villacís
    • Categories Nonsmooth Optimization, Stochastic Programming Tags , , , ,

    In this work, we are concerned with the study of optimization problems featuring so-called probability or chance constraints. Probability constraints measure the level of satisfaction of an underlying random inequality system and ensure that this level is high enough. Such an underlying inequality system could be expressed by an abstractly known or perhaps costly to … Read more

    Solution of Stochastic Facility Location Problems with Combinatorially many Decision-Dependent Distributions

  • Giovanni Pantuso
    • Categories Combinatorial Optimization, Facility Planning and Design, Stochastic Programming

    This article describes a model and an exact solution method for facility location problems with decision-dependent uncertainties. The model allows characterizing the probability distribution of the random elements as a function of the choice of open facilities. This, in turn, generates a combinatorial number of potential distributions of the random elements. Though general in the … Read more

    Measuring the Economic Value of Wind–Solar Complementarity in Europe Using Chance Constraints

  • Montree Jaidee
  • Bismark Singh
    • Categories Energy, Stochastic Programming Tags , , , ,

    The variability of wind and solar photovoltaic (PV) generation poses significant risks for producers in day-ahead electricity markets, where commitments must be made before actual output is realized. A common mitigation strategy is to invest in storage, but an alternative is to exploit the natural complementarity between wind and solar resources. We evaluate this economic … Read more

    Extracting Alternative Solutions from Benders Decomposition

  • Matthew Viens
  • William E. Hart
  • Michael C. Ferris
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Stochastic Programming Tags , , , , ,

    We show how to extract alternative solutions for optimization problems solved by Benders Decom- position. In practice, alternative solutions provide useful insights for complex applications; some solvers do support generation of alternative solutions but none appear to support such generation when using Benders Decomposition. We propose a new post-processing method that extracts multiple optimal and … Read more