Algorithm to solve a chance-constrained network capacity design problem with stochastic demands and finite support

• Published in: Naval research logistics 2016-04, Vol.63 (3), p.236-246
• Main Authors: Schumacher, Kathryn M., Li-Yang Chen, Richard, Cohn, Amy E.M., Castaing, Jeremy
• Format: Article
• Language: English
• Subjects: Algorithms; chance constraints; Computation; Demand; greedy algorithm; Logistics; MATHEMATICS AND COMPUTING; Navy; network design; Networks; Run time (computers); Separation
• ISSN: 0894-069X; 1520-6750
• DOI: 10.1002/nav.21685

We consider the problem of determining the capacity to assign to each arc in a given network, subject to uncertainty in the supply and/or demand of each node. This design problem underlies many real‐world applications, such as the design of power transmission and telecommunications networks. We first consider the case where a set of supply/demand scenarios are provided, and we must determine the minimum‐cost set of arc capacities such that a feasible flow exists for each scenario. We briefly review existing theoretical approaches to solving this problem and explore implementation strategies to reduce run times. With this as a foundation, our primary focus is on a chance‐constrained version of the problem in which α% of the scenarios must be feasible under the chosen capacity, where α is a user‐defined parameter and the specific scenarios to be satisfied are not predetermined. We describe an algorithm which utilizes a separation routine for identifying violated cut‐sets which can solve the problem to optimality, and we present computational results. We also present a novel greedy algorithm, our primary contribution, which can be used to solve for a high quality heuristic solution. We present computational analysis to evaluate the performance of our proposed approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 236–246, 2016