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.
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 |