Chance-Constrained Programming Models and Approximation Algorithms for the Balance-Constrained Stochastic Bottleneck Spanning Tree Problem
Abstract: This paper considers a balance-constrained 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 mixed-integer 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 Benders-decomposition-based 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 SOS2-based approximation algorithms and the SAA-based approach by testing them on a variety of graphs for different assumptions of edge weight distributions.
Keywords: Stochastic bottleneck spanning tree; chance-constrained programming; mixed-integer programming; special ordered set; sample average approximation.
Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )
Category 2: Stochastic Programming
Category 3: Network Optimization
Entry Submitted: 07/26/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|