An improved benders decomposition applied to a multi-layer network design problem

Bernard Fortz (1) , Michael Poss (2)

1 GOM - Graphes et Optimisation Mathématique [Bruxelles]
2 Heudiasyc - Heuristique et Diagnostic des Systèmes Complexes [Compiègne]

Benders decomposition has been widely used for solving network design problems. In this paper, we use a branch-and-cut algorithm to improve the separation procedure of Gabrel et al. and Knippel et al. for capacitated network design. We detail experiments on bi-layer networks, comparing with Knippel’s previous results.

Mots clés: multi-layer network design; metric inequalities; branch-and-cut Boulevard du Triomphe CP 210 / 01; B-1050 Brussels; Belgium

Domaines: Recherche opérationnelle [math.OC]

Bernard Fortz, Michael Poss. An improved benders decomposition applied to a multi-layer network design problem. Operations Research Letters, 2009, 37 (5), pp.359-364. ⟨10.1016/j.orl.2009.05.007⟩. ⟨hal-01255545⟩