Enhancing a Branch-and-Bound Algorithm for Two-Stage Stochastic Integer Network Design-Based Models
针对两阶段随机整数网络设计模型，提出分支定界策略，包括有效不等式、多根分支定界树、最优性割的选择性使用以及基于次梯度的分支技术，并通过固定费用网络设计问题验证效果。
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.