Relax-and-cut for capacitated network design. (English) Zbl 1162.90576
Brodal, Gerth Stølting (ed.) et al., Algorithms – ESA 2005. 13th annual European symposium, Palma de Mallorca, Spain, October 3–6, 2005. Proceedings. Berlin: Springer (ISBN 3-540-29118-0/pbk). Lecture Notes in Computer Science 3669, 47-58 (2005).
Summary: We present an evaluation of a Lagrangean-based branch-and-bound algorithm with additional valid inequalities for the capacitated network design problem. The focus is on two types of valid inequalities, the cover inequalities and local cuts. We show how these inequalities can be considered in a Lagrangean relaxation without destroying the computationally simple structure of the subproblems. We present an extensive computational study on a large set of benchmark data. The results show that the presented algorithm outperforms many other exact and heuristical solvers in terms of running time and solution quality.
For the entire collection see [Zbl 1086.68003].
For the entire collection see [Zbl 1086.68003].
MSC:
| 90C35 | Programming involving graphs or networks |
| 90B10 | Deterministic network models in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
