Refine
Document Type
- In Proceedings (15)
- ZIB-Report (15)
- Article (8)
- Book (1)
- Book chapter (1)
- Poster (1)
Language
- English (41)
Is part of the Bibliography
- no (41)
Keywords
- 0-1 Program (1)
- Ant Colony Optimization (1)
- Base Station Cooperation (1)
- Capacitated Network Design (1)
- Combinatorial Optimization, Robust Optimization, Multiband Robustness, Network Design (1)
- Data Uncertainty (1)
- Exact Large Neighborhood Search (1)
- Harvest Scheduling (1)
- Heterogeneous Wireless Networks, Biobjective Optimization, Mixed Integer Linear Programming, Simulation (1)
- Metaheuristic (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 provide an overview of our main results about studying Linear Programming Problems whose coefficient matrix is subject to uncertainty and the uncertainty is modeled through a multi-band set. Such an uncertainty set generalizes the classical one proposed by Bertsimas and Sim and is particularly suitable in the common case of arbitrary non-symmetric distributions of the parameters. Our investigations were inspired by practical needs of our industrial partner in ongoing projects with focus on the design of robust telecommunications networks.
The rapid technological evolution of telecommunication networks demands service providers to regularly update their technology, with the aim of remaining competitive in the marketplace. However, upgrading the technology in a network is not a trivial task. New hardware components need to be installed in the network and during the installation network connectivity may be temporarily compromised. The Wavelength Division Multiplexing (WDM) technology, whose upgrade is considered in here, shares fiber links among several optical connections and tearing down a single link may disrupt several optical connections at once. When the upgrades involve large parts of a network, typically not all links can be upgraded in parallel, which may lead to an unavoidable longer disruption of some connections. A bad scheduling of the overall endeavor, however, can dramatically increase the disconnection time of parts of the networks, causing extended service disruption. In this contribution, we study the problem of finding a schedule of the fiber link upgrades that minimizes the total service disruption time. To the best of our knowledge, this problem has not yet been formalized and investigated. The aim of our work is to close this gap by presenting a mathematical optimization model for the problem and an innovative solution algorithm that tackles the intrinsic difficulties of the problem. Computational experience on realistic instances completes our study. Our original investigations have been driven by real needs of DFN, operator of the German National Research and Education Network and our partner in the BMBF research project ROBUKOM (http://www.robukom.de/).
We propose a novel optimization model for resource assignment in heterogeneous wireless network. The model adopts two objective functions maximizing the number of served users and the minimum granted utility at once. A distinctive feature of our new model is to consider two consecutive time slots, in order to include handover as an additional decision dimension.
Furthermore, the solution algorithm that we propose refines a heuristic solution approach recently proposed in literature, by considering a real joint optimization of the considered resources. The simulation study shows that the new model leads to a significant reduction in handover frequency, when compared to a traditional scheme based on maximum SNR.
A central assumption in classical optimization is that all the input data of a
problem are exact. However, in many real-world problems, the input data are subject
to uncertainty. In such situations, neglecting uncertainty may lead to nominally optimal
solutions that are actually suboptimal or even infeasible. Robust optimization
offers a remedy for optimization under uncertainty by considering only the subset of
solutions protected against the data deviations. In this paper, we provide an overview
of the main theoretical results of multiband robustness, a new robust optimization
model that extends and refines the classical theory introduced by Bertsimas and Sim.
After introducing some new results for the special case of pure binary programs, we
focus on the harvest scheduling problem and show how multiband robustness can
be adopted to tackle the uncertainty affecting the volume of produced timber and
grant a reduction in the price of robustness.
Revisiting the use of Robust Optimization for optimal energy offering under price uncertainty
(2015)
We propose a new Robust Optimization method for the energy offering problem of a price-taker generating company that wants to build offering curves for its generation units, in order to maximize its profit while taking into account the uncertainty of market price. Our investigations have been motivated by a critique to another Robust Optimization method, which entails the solution of a sequence of robust optimization problems imposing full protection and defined over a sequence of nested subintervals of market prices: this method presents a number of issues that may severely limit its application and computational efficiency in practice and that may expose a company to the risk of presenting offering curves resulting into suboptimal or even infeasible accepted offers. To tackle all such issues, our method provides for solving one single robust counterpart, considering an intermediate level of protection between null and full protection, and to make energy offers at zero price, practically eliminating the risk of non-acceptance. Computational results on instances provided by our industrial partners show that our new method is able to grant a great improvement in profit.
We investigate the 3-architecture Connected Facility Location Problem arising in the design of urban telecommunication access networks integrating wired and wireless technologies. We propose an original optimization model for the problem that includes additional variables and constraints to take into account wireless signal coverage represented through signal-to-interference ratios. Since the problem can prove very challenging even for modern state-of-the art optimization solvers, we propose to solve it by an original primal heuristic that combines a probabilistic fixing procedure, guided by peculiar Linear Programming relaxations, with an exact MIP heuristic, based on a very large neighborhood search. Computational experiments on a set of realistic instances show that our heuristic can find solutions associated with much lower optimality gaps than a state-of-the-art solver.
Revisiting wireless network jamming by SIR-based considerations and Multiband Robust Optimization
(2016)
We revisit the mathematical models for wireless network jamming introduced by Commander et al. (2007,2008): we first point out the strong connections with classical wireless network design and then we propose a new model
based on the explicit use of signal-to-interference quantities. Moreover, to ad-
dress the uncertain nature of the jamming problem and tackle the peculiar right-hand-side (RHS) uncertainty of the corresponding model, we propose an original robust cutting-plane algorithm drawing inspiration from Multiband Robust Optimization. Finally, we assess the performance of the proposed cutting plane algorithm by experiments on realistic network instances.
The planning of a communication network is inevitably depending on the quality of both the planning tool and the demand forecast used. In this article, we show exemplarily how the emerging area of Robust Optimization can advance the network planning by a more accurate mathematical description of the demand uncertainty. After a general introduction of the concept and its application to a basic network design problem, we present two applications: multi-layer and mixed-line-rate network design. We conclude with a discussion of extensions of the robustness concept to increase the accuracy of handling uncertainties.