Decomposition methods for the two-stage stochastic Steiner tree problem.

A new algorithmic approach for solving the stochastic Steiner tree problem based on three procedures for computing lower bounds (dual ascent, Lagrangian relaxation, Benders decomposition) is introduced. Our method is derived from a new integer linear programming formulation, which is shown to be strongest among all known formulations. The resulting method, which relies on an interplay of the dual information retrieved from the respective dual procedures, computes upper and lower bounds and combines them with several rules for fixing variables in order to decrease the size of problem instances.

Integer programming models and branch-and-cut approaches to generalized {0,1,2}-survivable network design problems.

In this article, we introduce the Generalized [Formula: see text]-Survivable Network Design Problem ([Formula: see text]-GSNDP) which has applications in the design of backbone networks. Different mixed integer linear programming formulations are derived by combining previous results obtained for the related [Formula: see text]-GSNDP and Generalized Network Design Problems. An extensive computational study comparing the correspondingly developed branch-and-cut approaches shows clear advantages for two particular variants.