Technical Note---Branch-and-Price-and-Cut Approach to the Robust Network Design Problem Without Flow Bifurcations

Chungmok Lee (), Kyungsik Lee (), Kyungchul Park () and Sungsoo Park ()
Additional contact information
Chungmok Lee: IT Convergence Technology Research Laboratory, Electronics and Telecommunications Research Institute, Yuseong-gu, Daejeon 305-700, Republic of Korea, Department of Industrial and Systems Engineering, KAIST, Guseong-dong, Yuseong-gu, Daejeon 305-701, Republic of Korea
Kyungsik Lee: Department of Industrial and Management Engineering, Hankuk University of Foreign Studies, Mohyeon-myon, Yongin-si, Gyeonggi-do 449-791, Republic of Korea
Kyungchul Park: College of Business Administration, Myongji University, Namgaja-dong, Seodaemun-gu, Seoul 120-728, Republic of Korea
Sungsoo Park: Department of Industrial and Systems Engineering, KAIST, Guseong-dong, Yuseong-gu, Daejeon 305-701, Republic of Korea

Operations Research, 2012, vol. 60, issue 3, 604-610

Abstract: This paper presents a robust optimization approach to the network design problem under traffic demand uncertainty. We consider the specific case of the network design problem in which there are several alternatives in edge capacity installations and the traffic cannot be split over several paths. A new decomposition approach is proposed that yields a strong LP relaxation and enables traffic demand uncertainty to be addressed efficiently through localization of the uncertainty to each edge of the underlying network. A branch-and-price-and-cut algorithm is subsequently developed and tested on a set of benchmark instances.

Keywords: network design problem; robust optimization; integer programming; branch-and-price-and-cut; robust knapsack problem (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1049 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:3:p:604-610

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().