MATHEON-B3
Refine
Year of publication
Document Type
- ZIB-Report (10)
- In Proceedings (7)
- Article (4)
- Book chapter (1)
- In Collection (1)
- Master's Thesis (1)
Is part of the Bibliography
- no (24)
Keywords
- network design (3)
- mixed integer programming (2)
- multi-layer network design (2)
- Circuit Switching (1)
- IP-over-WDM (1)
- Opacity (1)
- SNDlib (1)
- affine adjustable robust counterparts (1)
- affine routing (1)
- branch-and-cut (1)
Institute
We investigate the Robust Multiperiod Network Design Problem, a generalization
of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical
CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against
traffic volume uncertainty, we propose a Robust Optimization model based
on Multiband Robustness (Büsing and D'Andreagiovanni, 2012), a refinement of classical Gamma-Robustness by Bertsimas and Sim (2004) that uses a system of multiple deviation bands. Since the resulting optimization problem
may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib (2010) show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps.