BROWSE
Detail
Journal Article
Benders Decomposition Approach for the Robust Network Design Problem with Flow Bifurcations
Cited 30 time in 
Share 
Share
- Authors
- Chungmok Lee, Kyungsik Lee, Sungsoo Park
- Issue Date
- 2013-08
- Citation
- Networks : An International Journal, v.62, no.1, pp.1-16
- ISSN
- 0028-3045
- Publisher
- John Wiley & Sons
- Language
- English
- Type
- Journal Article
- Abstract
- We consider a network design problem in which flow bifurcations are allowed. The demand data are assumed to be uncertain, and the uncertainties of demands are expressed by an uncertainty set. The goal is to install facilities on the edges at minimum cost. The solution should be able to deliver any of the demand requirements defined in the uncertainty set. We propose an exact solution algorithm based on a decomposition approach in which the problem is decomposed into two distinct problems: (1) designing edge capacities; and (2) checking the feasibility of the designed edge capacities with respect to the uncertain demand requirements. The algorithm is a special case of the Benders decomposition method. We show that the robust version of the Benders subproblem can be formulated as a linear program whose size is polynomially bounded. We also propose a simultaneous cut generation scheme to accelerate convergence of the Benders decomposition algorithm. Computational results on real-life telecommunication problems are reported, and these demonstrate that robust solutions with very small penalties in the objective values can be obtained. © 2012 Wiley Periodicals, Inc. Networks, 2013. Copyright © 2012 Wiley Periodicals, Inc.
- KSP Keywords
- Benders decomposition method, Cut generation, Decomposition algorithm, Decomposition approach, Linear program, Minimum cost, Network Design Problem, Robust network design, Robust solution, Solution algorithm, computational results