ETRI-Knowledge Sharing Plaform

ENGLISH

성과물

논문 검색
구분 SCI
연도 ~ 키워드

상세정보

학술지 Benders Decomposition Approach for the Robust Network Design Problem with Flow Bifurcations
Cited 27 time in scopus Download 2 time Share share facebook twitter linkedin kakaostory
저자
이충목, 이경식, 박성수
발행일
201308
출처
Networks : An International Journal, v.62 no.1, pp.1-16
ISSN
0028-3045
출판사
John Wiley & Sons
DOI
https://dx.doi.org/10.1002/net.21486
협약과제
12MC1100, SMART Post 구축 기술 개발, 정훈
초록
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.
키워드
Benders decomposition, integer programming, network design, robust optimization
KSP 제안 키워드
Benders decomposition method, Cut generation, Decomposition algorithm, Decomposition approach, Exact solution, Integer Programming, Linear program, Minimum cost, Network Design Problem, Robust network design, Robust optimization