  


Scenario Set Partition Dual Bounds for Multistage Stochastic Programming: A Hierarchy of Bounds and a Partition Sampling Approach
Ilke Bakir (ilkebakirgatech.edu) Abstract: We consider multistage stochastic programming problems in which the random parameters have finite support, leading to optimization over a finite scenario set. We propose a hierarchy of bounds based on partitions of the scenario set into subsets of (nearly) equal cardinality. These expected partition (EP) bounds coincide with EGSO bounds provided by Sandikci et al. (2013) in the case that the subset cardinality divides evenly into the cardinality of the scenario set, and otherwise interpolate between the bounds for two consecutive cardinalities. Partition bounds have a substantial advantage for practical computation: solution of the group subproblem for all subsets in a single partition yields a dual bound. Furthermore, the best of even a very small number of such single partition bounds is very likely, in practice, to be better than the corresponding EP bound. By sampling partitions of the scenario set, we obtain an algorithm that provides exact dual bounds for the stochastic program. The practical value of these ideas is illustrated on benchmark problems, and the approach compared to Sample Average Approximation. Finally, we present three methods for improving the dual bounds obtained by the partition sampling algorithm: (i) Partition sampling using the scenario tree structure in multistage instances, (ii) generating optimally recombined partitions using the samples that were previously sampled in the algorithm, and (iii) truncating the partition bound calculations by ceasing computation of partitions that appear to be unpromising in terms of finding a good partition bound. Keywords: Stochastic programming Category 1: Stochastic Programming Citation:: Download: [PDF] Entry Submitted: 01/28/2016 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  