Optimization Online


Chance-Constrained Programming Models and Approximation Algorithms for the Balance-Constrained Stochastic Bottleneck Spanning Tree Problem

Jue Wang(juewang***at***umich.edu)
Siqian Shen(siqian***at***umich.edu)
Murat Kurt(muratkur***at***buffalo.edu)

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


Download: [PDF]

Entry Submitted: 07/26/2012
Entry Accepted: 07/27/2012
Entry Last Modified: 07/26/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society