A packing integer program arising in two-layer network design
Please always quote using this URN:urn:nbn:de:0296-matheon-6410
- In this paper we study a certain cardinality constrained packing integer program which is motivated by the problem of dimensioning a cut in a two-layer network. We prove NP-hardness and consider the facial structure of the corresponding polytope. We provide a complete description for the smallest nontrivial case and develop two general classes of facet-defining inequalities. This approach extends the notion of the well known cutset inequalities to two network layers.
Download full text files
Additional Services
| Author: | Christian Raack, Arie M. C. A. Koster |
|---|---|
| URN: | urn:nbn:de:0296-matheon-6410 |
| Referee: | Andreas Bley |
| Document Type: | Preprint, Research Center Matheon |
| Language: | English |
| Date of first Publication: | 2009/07/27 |
| Release Date: | 2009/07/26 |
| Tag: | |
| Institute: | Zuse Institute Berlin (ZIB) |
| Preprint Number: | 646 |
