Enhancing a branch-and-bound algorithm for two-stage stochastic integer network design-based models

• 成果类型: Article
• 署名作者: Andrade, Rafael; Lisser, Abdel; Maculan, Nelson; Plateau, Gerard
• 署名单位: Universite Paris Saclay; Universidade Federal do Rio de Janeiro; Universite Paris 13
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.1060.0536
• 发表日期: 2006
• 页码: 1450-1455
• 关键词: stochastic integer programming; network design under uncertainty; B&B strategies

摘要

In this paper we present branch-and-bound (B&B) strategies for two-stage stochastic integer network design-based models with integrality constraints in the first-stage variables. These strategies are used within L-shaped decomposition-based B&B framework. We propose a valid inequality in order to improve B&B performance. We use this inequality to implement a multirooted B&B tree. A selective use of optimality cuts is explored in the B&B approach and we also propose a subgradient-based technique for branching on 0-1 feasible solutions. Finally, we present computational results for a fixed-charge network design problem with random demands.