TY - JOUR

T1 - Generalized adaptive partition-based method for two-stage stochastic linear programs with fixed recourse

AU - Ramirez-Pico, Cristian

AU - Moreno, Eduardo

N1 - Funding Information:
Supported by ANID/CONICYT-Fondecyt Regular 1161064 and 1200809.
Publisher Copyright:
© 2021, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

PY - 2022/11

Y1 - 2022/11

N2 - We present a method to solve two-stage stochastic linear programming problems with fixed recourse when the uncertainty space can have either discrete or continuous distributions. Given a partition of the uncertainty space, the method is addressed to solve a discrete problem with one scenario for each element of the partition (subregions of the uncertainty space). Fixing first-stage variables, we formulate a second-stage subproblem for each element, and exploiting information from the dual of these problems, we provide conditions that the partition must satisfy to obtain an optimal solution. These conditions provide guidance on how to refine the partition, iteratively approaching an optimal solution. The results from computational experiments show how the method automatically refines the partition of the uncertainty space in the regions of interest for the problem. Our algorithm is a generalization of the adaptive partition-based method presented by Song and Luedtke for discrete distributions, extending its applicability to more general cases.

AB - We present a method to solve two-stage stochastic linear programming problems with fixed recourse when the uncertainty space can have either discrete or continuous distributions. Given a partition of the uncertainty space, the method is addressed to solve a discrete problem with one scenario for each element of the partition (subregions of the uncertainty space). Fixing first-stage variables, we formulate a second-stage subproblem for each element, and exploiting information from the dual of these problems, we provide conditions that the partition must satisfy to obtain an optimal solution. These conditions provide guidance on how to refine the partition, iteratively approaching an optimal solution. The results from computational experiments show how the method automatically refines the partition of the uncertainty space in the regions of interest for the problem. Our algorithm is a generalization of the adaptive partition-based method presented by Song and Luedtke for discrete distributions, extending its applicability to more general cases.

KW - Adaptive partition-based approach

KW - Continuous distribution

KW - Scenario aggregation

KW - Two-stage stochastic programming

UR - http://www.scopus.com/inward/record.url?scp=85101322323&partnerID=8YFLogxK

U2 - 10.1007/s10107-020-01609-8

DO - 10.1007/s10107-020-01609-8

M3 - Article

AN - SCOPUS:85101322323

SN - 0025-5610

VL - 196

SP - 755

EP - 774

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-2

ER -