Optimization Online


Chance-Constrained Multi-Terminal Network Design Problems

Yongjia Song (ysong3***at***vcu.edu)
Minjiao Zhang (mzhang***at***cba.ua.edu)

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 a scenario-based Steiner cut formulation, and a formulation based on a probabilistic variant of Steiner cuts. We study the strength of the proposed valid inequalities, and develop a branch-and-cut solution method. We also propose an LP-based separation for scenario-based directed Steiner cut inequalities using Benders feasibility cuts, leveraging the success of directed Steiner cuts for the deterministic Steiner tree problem. Mixing inequalities are also applied to further strengthen the formulation. In our computational study, we show the performance of our branch-and-cut method on the test instances to demonstrate the strength of the scenario-based formulations and the benefit from adding the Benders feasibility cuts and mixing inequalities.

Keywords: Stochastic network design, Steiner tree, Chance constraint, Benders decomposition

Category 1: Network Optimization

Category 2: Stochastic Programming

Category 3: Integer Programming

Citation: Accepted in Naval Research Logistics, 2015

Download: [PDF]

Entry Submitted: 05/07/2014
Entry Accepted: 05/08/2014
Entry Last Modified: 04/15/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society