Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 3 of 31
Back to Result List

Capacitated Network Design with Multicast Commodities

Please always quote using this URN: urn:nbn:de:0297-zib-5823
  • This paper addresses the problem of designing a minimum cost network whose capacities are sufficiently large to allow a feasible routing of a given set of multicast commodities. A multicast commodity consists of a set of two or mo re terminals that need to be connected by a so called broadcast tree, which consumes on all of its edges a capacity as large as the demand value associated with that commodity. We model the network design problem with multicast commodities as the problem of packing capacitated Steiner trees in a graph. In the first part of the paper we present three mixed-integer programming formulations for this problem. The first natural formulation uses only one integer capacity variable for each edge and and one binary tree variable for each commodity-edge pair. Applying well-known techniques from the Steiner tree problem, we then develop a stronger directed and a multicommodity flow based mixed-integer programming formulation. In the second part of the paper we study the associated polyhedra and derive valid and even facet defining inequalities for the natural formulation. Finally, we describe separation algorithms for these inequalities and present computational results that demonstrate the strength of our extended formulations.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Daniel Bienstock, Andreas Bley
Document Type:ZIB-Report
Tag:Steiner tree packing; multicast 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/05/02
Series (Serial Number):ZIB-Report (00-14)
ZIB-Reportnumber:00-14
Published in:Appeared in: Proceedings in the 8th International Conference on Telecommunication Systems, March 9-12, 2000 Nashville
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.