  


ChanceConstrained Programming Models and Approximation Algorithms for the BalanceConstrained Stochastic Bottleneck Spanning Tree Problem
Jue Wang(juewangumich.edu) Abstract: This paper considers a balanceconstrained stochastic bottleneck spanning tree problem in which edge weights are independently distributed random variables. The problem seeks a minimum value and a spanning tree, whose maximum edge weight is bounded by the value with certain probability, and meanwhile, the minimum edge weight is bounded by a given lower bound in another chance constraint. The problem is transformed into a mixedinteger nonlinear program, for which we formulate two approximations using a special ordered set of type one (SOS1) and a special ordered set of type two (SOS2) variables. Moreover, we consider an integer programming transformation that uses sample average approximation (SAA) technique and develop a Bendersdecompositionbased approach to solve the transformation. The paper also uses a greedy algorithm to derive an upper bound objective value for any given spanning tree solution. We run computations of the SOS1 and SOS2based approximation algorithms and the SAAbased approach by testing them on a variety of graphs for different assumptions of edge weight distributions. Keywords: Stochastic bottleneck spanning tree; chanceconstrained programming; mixedinteger programming; special ordered set; sample average approximation. Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Category 2: Stochastic Programming Category 3: Network Optimization Citation: Download: [PDF] Entry Submitted: 07/26/2012 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  