Two-layer Network Design by Branch-and-Cut featuring MIP-based Heuristics
Please always quote using this URN:urn:nbn:de:0296-matheon-3654
- This paper deals with MIP-based primal heuristics to be used within a branch-and-cut approach for solving multi-layer telecommunication network design problems. Based on a mixed-integer programming formulation for two network layers, we present three heuristics for solving important subproblems, two of which solve a sub-MIP. On multi-layer planning instances with many parallel logical links, we show the effectiveness of our heuristics in finding good solutions early in the branch-and-cut search tree.
Author: | Sebastian Orlowski, Arie M. C. A. Koster, Christian Raack, Roland Wessäly |
---|---|
URN: | urn:nbn:de:0296-matheon-3654 |
Referee: | Volker Kaibel |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2006/11/22 |
Release Date: | 2006/11/20 |
Tag: | |
Institute: | Zuse Institute Berlin (ZIB) |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B18 Communication networks [See also 68M10, 94A05] |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C59 Approximation methods and heuristics | |
Preprint Number: | 359 |