Sampling Scenario Set Partition Dual Bounds for Multistage Stochastic Programs

Ilke Bakir*, Natashia Boland, Brian Dandurand, Alan Erera

*Corresponding author voor dit werk

Onderzoeksoutput: ArticleAcademicpeer review

7 Citaten (Scopus)
298 Downloads (Pure)

Samenvatting

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. Â

Originele taal-2English
Pagina's (van-tot)145-163
Aantal pagina's19
TijdschriftINFORMS Journal on Computing
Volume32
Nummer van het tijdschrift1
DOI's
StatusPublished - 2020

Vingerafdruk

Duik in de onderzoeksthema's van 'Sampling Scenario Set Partition Dual Bounds for Multistage Stochastic Programs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit