Refine
Document Type
- ZIB-Report (12) (remove)
Language
- English (12)
Has Fulltext
- yes (12)
Is part of the Bibliography
- no (12) (remove)
Keywords
- network design (4)
- energy efficiency (2)
- integer programming (2)
- mixed integer programming (2)
- multi-layer network design (2)
- Circuit Switching (1)
- FTTx, FTTH, FTTB, FTTC, FTTN, telecommunications, access networks, passive optical networks, network design, routing, energy efficiency (1)
- IP-over-WDM (1)
- Opacity (1)
- SNDlib (1)
Institute
This paper deals with directed, bidirected, and undirected capacitated network design problems. Using mixed integer rounding (MIR), we generalize flow-cutset inequalities to these three link types and to an arbitrary modular link capacity structure, and propose a generic separation algorithm. In an extensive computational study on 54 instances from the Survivable Network Design Library (SNDlib), we show that the performance of cplex can significantly be enhanced by this class of cutting planes. The computations reveal the particular importance of the subclass of cutset-inequalities.
Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust
programs with arbitrary recourse. We apply them to robust network design with polyhedral demand
uncertainty, introducing the affine routing principle.
We compare the affine routing to the well-studied static and dynamic routing schemes for robust
network design.
All three schemes are embedded into the general framework of two-stage network design with recourse.
It is shown that affine routing can be seen as a generalization of the widely used static
routing still being tractable and providing cheaper solutions. We investigate properties on the
demand polytope under which affine routings reduce to static routings and also develop conditions on
the uncertainty set leading to dynamic routings being affine. We show however that affine routings
suffer from the drawback that (even totally) dominated demand vectors are not necessarily supported
by affine solutions. Uncertainty sets have to be designed accordingly. Finally, we present
computational results on networks from SNDlib. We conclude that for these instances the
optimal solutions based on affine routings tend to be as cheap as optimal network designs for
dynamic routings. In this respect the affine routing principle can be used to approximate the cost
for two-stage solutions with free recourse which are hard to compute.