TY - GEN A1 - Hoesel, Stan P.M. van A1 - Koster, Arie M.C.A. A1 - Leensel, Robert L.M.J. van de A1 - Savelsbergh, Martin W.P. T1 - Polyhedral Results for the Edge Capacity Polytope N2 - 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. T3 - ZIB-Report - 00-22 KW - network design KW - mixed integer programming KW - cutting planes KW - knapsack with integer capacity Y1 - 2000 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/590 UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-5907 ER -