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

• 成果类型: Article
• 署名作者: Lee, Chungmok; Lee, Kyungsik; Park, Kyungchul; Park, Sungsoo
• 署名单位: Electronics & Telecommunications Research Institute - Korea (ETRI); Korea Advanced Institute of Science & Technology (KAIST); Hankuk University Foreign Studies; Myongji University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1120.1049
• 发表日期: 2012
• 页码: 604-610
• 关键词: demand uncertainty; optimization

摘要

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.