Premium
Benders decomposition approach for the robust network design problem with flow bifurcations
Author(s) -
Lee Chungmok,
Lee Kyungsik,
Park Sungsoo
Publication year - 2013
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21486
Subject(s) - benders' decomposition , mathematical optimization , convergence (economics) , decomposition , set (abstract data type) , flow network , computer science , network planning and design , scheme (mathematics) , enhanced data rates for gsm evolution , decomposition method (queueing theory) , flow (mathematics) , robust optimization , mathematics , ecology , computer network , mathematical analysis , telecommunications , geometry , discrete mathematics , economics , biology , programming language , economic growth
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.