Sampling Scenario Set Partition Dual Bounds for Multistage Stochastic Programs

Ilke Bakir (), Natashia Boland (), Brian Dandurand () and Alan Erera ()
Additional contact information
Ilke Bakir: Department of Operations, University of Groningen, 9712 CP Groningen, Netherlands
Natashia Boland: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Brian Dandurand: Department of Mathematical Sciences, Royal Melbourne Institute of Technology, Melbourne, Victoria 3000, Australia
Alan Erera: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

INFORMS Journal on Computing, 2020, vol. 32, issue 1, 145-163

Abstract: 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.

Keywords: stochastic programming; multistage stochastic programming; bounds; dual decomposition (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0885 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:2020:i:1:p:145-163

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().