TY - JOUR
T1 - Sampling Scenario Set Partition Dual Bounds for Multistage Stochastic Programs
AU - Bakir, Ilke
AU - Boland, Natashia
AU - Dandurand, Brian
AU - Erera, Alan
PY - 2020
Y1 - 2020
N2 - We consider multistage stochastic programming problems in which the random parameters have finite support, leading to optimization over a finite scenario set. There has been recent interest in dual bounds for such problems, of two types. One, known as expected group subproblem objective (EGSO) bounds, require solution of a group subproblem, which optimizes over a subset of the scenarios, for all subsets of the scenario set that have a given cardinality. Increasing the subset cardinality in the group subproblem improves bound quality, (EGSO bounds form a hierarchy), but the number of group subproblems required to compute the bound increases very rapidly. Another is based on partitions of the scenario set into subsets. Combining the values of the group subproblems for all subsets in a partition yields a partition bound. In this paper, we consider partitions into subsets of (nearly) equal cardinality. We show that the expected value of the partition bound over all such partitions also forms a hierarchy. To make use of these bounds in practice, we propose random sampling of partitions and suggest two enhancements to the approach: Sampling partitions that align with the multistage scenario tree structure and use of an auxiliary optimization problem to discover new best bounds based on the values of group subproblems already computed. We establish the effectiveness of these ideas with computational experiments on benchmark problems. Finally, we give a heuristic to save computational effort by ceasing computation of a partition partway through if it appears unpromising. Â
AB - We consider multistage stochastic programming problems in which the random parameters have finite support, leading to optimization over a finite scenario set. There has been recent interest in dual bounds for such problems, of two types. One, known as expected group subproblem objective (EGSO) bounds, require solution of a group subproblem, which optimizes over a subset of the scenarios, for all subsets of the scenario set that have a given cardinality. Increasing the subset cardinality in the group subproblem improves bound quality, (EGSO bounds form a hierarchy), but the number of group subproblems required to compute the bound increases very rapidly. Another is based on partitions of the scenario set into subsets. Combining the values of the group subproblems for all subsets in a partition yields a partition bound. In this paper, we consider partitions into subsets of (nearly) equal cardinality. We show that the expected value of the partition bound over all such partitions also forms a hierarchy. To make use of these bounds in practice, we propose random sampling of partitions and suggest two enhancements to the approach: Sampling partitions that align with the multistage scenario tree structure and use of an auxiliary optimization problem to discover new best bounds based on the values of group subproblems already computed. We establish the effectiveness of these ideas with computational experiments on benchmark problems. Finally, we give a heuristic to save computational effort by ceasing computation of a partition partway through if it appears unpromising. Â
KW - stochastic programming
KW - multistage stochastic programming
KW - bounds
KW - dual decomposition
KW - MIXED 0-1 PROBLEMS
KW - ALGORITHMIC FRAMEWORK
KW - DECOMPOSITION
KW - AGGREGATION
KW - MODELS
KW - APPROXIMATIONS
KW - OPTIMIZATION
U2 - 10.1287/ijoc.2018.0885
DO - 10.1287/ijoc.2018.0885
M3 - Article
SN - 1091-9856
VL - 32
SP - 145
EP - 163
JO - INFORMS Journal on Computing
JF - INFORMS Journal on Computing
IS - 1
ER -