Complete Linear Descriptions for Special Instances of the Single Source Fixed Charge Network Flow Design Problem
Please always quote using this URN: urn:nbn:de:0297-zib-1630
- The multicommodity linear formulation of the Fixed Charge Network Flow Design problem is known to have significantly sharp linear relaxation lower bounds. However the tradeoff is the introduction of a large amount of artificial variables. We exhibit a class of special instances for which the lower bound is tight. Further we completly describe the polyhedron in the space of the natural variables.
Author: | Michel Schaffers |
---|---|
Document Type: | ZIB-Report |
Date of first Publication: | 1994/12/15 |
Series (Serial Number): | ZIB-Report (SC-94-35) |
ZIB-Reportnumber: | SC-94-35 |