Paper Info
Title
Chance-Constrained Programming Models and Approximations for General Stochastic Bottleneck Spanning Tree Problems
Abstract
We consider a balance-constrained stochastic bottleneck spanning tree problem BCSBSTP where edge weights are independently distributed but may follow arbitrary continuous distributions. The goal is to minimize a threshold variable that may be exceeded by the maximum edge weight at certain risk, subject to the minimum edge weight being no less than a fixed threshold with a probability guarantee. We characterize these two requirements as chance constraints, which are typically used for bounding the risk of undesirable random outcomes. Given independently distributed edge weights, we reformulate BCSBSTP as a mixed-integer nonlinear program, approximated by two mixed-integer linear programs based on special ordered set of type one SOS1 and special ordered set of type two SOS2 variables. By relaxing the probabilistic guarantee on the minimum edge weight in BCSBSTP, we also consider a stochastic bottleneck spanning tree problem SBSTP, of which optimal tree solutions are approximated via a bisection algorithm in pseudopolynomial time. We demonstrate computational results of our models and algorithms by testing randomly generated instances with edge weights following a diverse set of independent distributions.
Year
DOI
Venue
2015
10.1287/ijoc.2014.0627
INFORMS Journal on Computing
Keywords
DocType
Volume
bisection algorithm,np complete
Journal
27
Issue
ISSN
Citations 
2
1091-9856
0
PageRank 
References 
Authors
0.34
14
3
Name
Order
Citations
PageRank
Siqian Shen112312.61
murat kurt200.34
Jue Wang32871155.89