Chance-Constrained Programming Models and Approximations for General Stochastic Bottleneck Spanning Tree Problems
Siqian Shen, Murat Kurt, Jue Wang
INFORMS Journal on Computing · 2015 · Volume 27 · Issue 2
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.
Keywords
stochastic bottleneck spanning tree, chance-constrained programming, special ordered sets, bisection algorithm, NP-complete
Enable JavaScript for citation tools and additional paper interactions.