Refine
Document Type
- ZIB-Report (3)
- Article (1)
- In Proceedings (1)
Language
- English (5)
Is part of the Bibliography
- no (5)
Keywords
- 0-1 Program (1)
- Ant Colony Optimization (1)
- Base Station Cooperation (1)
- Capacitated Network Design (1)
- Exact Large Neighborhood Search (1)
- Metaheuristic (1)
- Multiband Robust Optimization (1)
- Multiperiod Design (1)
- Multiperiod Network Design, Traffic Uncertainty, Robust Optimization, Multiband Robustness, Hybrid Heuristics (1)
- Traffic Uncertainty (1)
Institute
Base station cooperation in the downlink of cellular systems has been recently suggested as a promising concept towards a
better exploitation of the communication system physical resources. It may offer a high gain in capacity through interference mitigation.
This however,
comes at a cost of high information exchange between cooperating entities and a high computational burden.
Clustering of base stations into subgroups is an alternative to
guarantee such cooperation benefits in a lower scale. The optimal definition of clusters, however, and a systematic way to find a solution to
such problem is not yet available. In this work, we highlight the combinatorial nature of the problem, exploit this to describe the
system of users and base stations as a graph and formulate a pure 0-1 program. Its solution
suggests a cost optimal way to form clusters and assign user subsets to them.
We investigate the Robust Multiperiod Network Design Problem, a generalization of the classical Capacitated Network Design Problem that additionally considers multiple design periods and provides solutions protected against traffic uncertainty.
Given the intrinsic difficulty of the problem, which proves challenging even for state-of-the art commercial solvers, we propose a hybrid primal heuristic based on the combination of ant colony optimization and an exact large neighborhood search. Computational experiments on a set of realistic instances from the SNDlib show that our heuristic can find solutions of extremely good quality with low optimality gap.
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.
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.