Chance‐constrained multi‐terminal network design problems |
| |
| Authors: | Yongjia Song Minjiao Zhang |
| |
| Affiliation: | 1. Department of Statistical Sciences and Operations Research, Virginia Commonwealth University, Richmond, Virginia;2. Department of Information Systems, Statistics, and Management Science, The University of Alabama, Tuscaloosa, Alabama |
| |
| Abstract: | We consider a reliable network design problem under uncertain edge failures. Our goal is to select a minimum‐cost subset of edges in the network to connect multiple terminals together with high probability. This problem can be seen as a stochastic variant of the Steiner tree problem. We propose two scenario‐based Steiner cut formulations, study the strength of the proposed valid inequalities, and develop a branch‐and‐cut solution method. We also propose an LP‐based separation for the scenario‐based directed Steiner cut inequalities using Benders feasibility cuts, leveraging the success of the directed Steiner cuts for the deterministic Steiner tree problem. In our computational study, we test our branch‐and‐cut method on instances adapted from graphs in SteinLib Testdata Library with up to 100 nodes, 200 edges, and 17 terminals. The performance of our branch‐and‐cut method demonstrates the strength of the scenario‐based formulations and the benefit from adding the additional valid inequalities that we propose. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 321–334, 2015 |
| |
| Keywords: | stochastic network design Steiner tree chance constraint Benders decomposition |
|
|
