Polyhedral Results for the Edge Capacity Polytope
Please always quote using this URN: urn:nbn:de:0297-zib-5907
- Network loading problems occur in the design of telecommunication networks, in many different settings. The polyhedral structure of this problem is important in developing solution methods for the problem. In this paper we investigate the polytope of the problem restricted to one edge of the network (the edge capacity problem). We describe classes of strong valid inequalities for the edge capacity polytope, and we derive conditions under which these constraints define facets. As the edge capacity problem is a relaxation of the network loading problem, their polytopes are intimately related. We, therefore, also give conditions under which the inequalities of the edge capacity polytope define facets of the network loading polytope. Furthermore, some structural properties are derived, such as the relation of the edge capacity polytope to the knapsack polytope. We conclude the theoretical part of this paper with some lifting theorems, where we show that this problem is polynomially solvable for most of our classes of valid inequalities. In a computational study the quality of the constraints is investigated. Here, we show that the valid inequalities of the edge capacity polytope are not only important for solving the edge capacity problem, but also for the network loading problem, showing that the edge capacity problem is an important subproblem.
Author: | Stan P.M. van Hoesel, Arie M.C.A. Koster, Robert L.M.J. van de Leensel, Martin W.P. Savelsbergh |
---|---|
Document Type: | ZIB-Report |
Tag: | cutting planes; knapsack with integer capacity; mixed integer programming; network design |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization | |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C90 Applications of mathematical programming | |
Date of first Publication: | 2000/06/26 |
Series (Serial Number): | ZIB-Report (00-22) |
ZIB-Reportnumber: | 00-22 |
Published in: | Appeared in: Mathematical Programming, series A, vol. 92 (2002) pp. 335-358 |