IDEAS home Printed from
   My bibliography  Save this article

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


  • Kathryn M. Schumacher
  • Richard Li‐Yang Chen
  • Amy E.M. Cohn
  • Jeremy Castaing


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

Suggested Citation

  • Kathryn M. Schumacher & Richard Li‐Yang Chen & Amy E.M. Cohn & Jeremy Castaing, 2016. "Algorithm to solve a chance‐constrained network capacity design problem with stochastic demands and finite support," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(3), pages 236-246, April.
  • Handle: RePEc:wly:navres:v:63:y:2016:i:3:p:236-246
    DOI: 10.1002/nav.21685

    Download full text from publisher

    File URL:
    Download Restriction: no

    References listed on IDEAS

    1. Hua Sun & Ziyou Gao & W. Szeto & Jiancheng Long & Fangxia Zhao, 2014. "A Distributionally Robust Joint Chance Constrained Optimization Model for the Dynamic Network Design Problem under Demand Uncertainty," Networks and Spatial Economics, Springer, vol. 14(3), pages 409-433, December.
    2. Geir Dahl & Mechthild Stoer, 1998. "A Cutting Plane Algorithm for Multicommodity Survivable Network Design Problems," INFORMS Journal on Computing, INFORMS, vol. 10(1), pages 1-11, February.
    3. S Mudchanatongsuk & F Ordóñez & J Liu, 2008. "Robust solutions for network design under transportation cost and demand uncertainty," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(5), pages 652-662, May.
    4. S. Sridhar & R. Chandrasekaran, 1992. "Integer Solution to Synthesis of Communication Networks," Mathematics of Operations Research, INFORMS, vol. 17(3), pages 581-585, August.
    5. Xing Hong & Miguel A. Lejeune & Nilay Noyan, 2015. "Stochastic network design for disaster preparedness," IISE Transactions, Taylor & Francis Journals, vol. 47(4), pages 329-357, April.
    6. Yongjia Song & James R. Luedtke & Simge Küçükyavuz, 2014. "Chance-Constrained Binary Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 735-747, November.
    7. Jean-Paul Watson & Roger J-B Wets & David L. Woodruff, 2010. "Scalable Heuristics for a Class of Chance-Constrained Stochastic Programs," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 543-554, November.
    8. Bai, Ruibin & Wallace, Stein W. & Li, Jingpeng & Chong, Alain Yee-Loong, 2014. "Stochastic service network design with rerouting," Transportation Research Part B: Methodological, Elsevier, vol. 60(C), pages 50-65.
    9. Adam Ouorou, 2006. "Robust Capacity Assignment in Telecommunications," Computational Management Science, Springer, vol. 3(4), pages 285-305, September.
    10. Thapalia, Biju K. & Crainic, Teodor Gabriel & Kaut, Michal & Wallace, Stein W., 2012. "Single-commodity network design with random edge capacities," European Journal of Operational Research, Elsevier, vol. 220(2), pages 394-403.
    Full references (including those not matched with items on IDEAS)

    More about this item


    Access and download statistics


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:63:y:2016:i:3:p:236-246. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Wiley Content Delivery). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.