1,721,033 research outputs found
Upper and lower bounds for the fixed spectrum frequency assignment problem
No full textA survey of the results described in the author's PhD thesis (Montemanni 2001) is presented. The thesis, which was supervised by Prof. Derek H. Smith and Dr. Stuart M. Allen, has been defended in January 2002 at the University of Glamorgan (U.K.). The thesis proposes new heuristic algorithms, based on well-known meta-heuristic paradigms, and new lower bounding techniques, based on linear programming, for the fixed spectrum frequency assignment problem. © 2003 Springer-Verlag Berlin/Heidelberg
Scheduling problems with precedence constraints: Models and algorithms
No full textThe sequential ordering problem is a basic scheduling problem with precedence constraints. It can be used to model many real world applications arising in different fields in terms of combinatorial optimization. In this paper we review two approaches to the problem recently appeared in the literature. Both the methods are based on a mixed integer linear programming, which is in turn introduced and discussed. Experimental results are presented to analyze the performance of the algorithms. © 2012 EUROSIS-ETI
Radio Frequency Assignment: Optimization Techniques
No full textThe frequency assignment problem involves the assignment of discrete channels (or frequencies) to the transmitters of a radio network, such as a mobile telephone network. Frequency separation is necessary to avoid interference by other transmitters to the signal received from the wanted transmitter at the reception points. Unnecessary separation causes an excess requirement for spectrum. Good assignments minimise interference and the spectrum required.
Some different variations of the problem are presented in this report to- gether with the results obtained so far for them. In this work we will study mainly the so-called “Fixed Spectrum Problem”, where there is a fixed avail- able spectrum of frequencies and the aim is to minimise interference.
There are two main approaches to model the frequency assignment prob- lem: the so-called “Binary Constraints Model”, historically the most studied in the literature, where only interference from a single transmitter at a time is considered, and the more realistic “Multiple Interference Model”, where interferences from more than one transmitter are considered at the same mo- ment. For this last model a deeply theoretical study does not yet exist in the literature.
The fixed spectrum problem, represented by the binary constraints model has been heavily studied in the last few years, but no general-purpose lower bound has been presented yet. We analyse some Integer Programming for- mulation to understand whether they can be suitable for developing lower bounds.
The multiple interference model is studied and some new algorithms, both heuristic and exact, are presented for it, together with the relevant computational results. Our aim is to understand the potential of this model.
The report concludes by outlining some proposals for future work
A Benders decomposition approach for the robust shortest path problem with interval data
No full textMany real problems can be modelled as robust shortest path problems on digraphs with interval costs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible conflguration of the arc costs. A Benders decomposition approach for this problem is presented
A three-stage robust approach for minimum power multicasting in wireless sensor networks
No full textIn this paper we study the minimum power multicasting problem in wireless sensor networks, where the transmission power required for one network terminal to transmit to another is subject to uncertainty.
We propose a three-stage approach based on linear programming.
Our novel approach adds two polynomial time stages to a first stage corresponding to a classical approach well known in the literature and based on a mathematical programming formulation. Stages two and three are introduced to adjust the transmission power of nodes in such a way to achieve a better protection against uncertainty, without increasing the total power consumption.
Experimental results show that our three-stage approach increases the robustness of the solutions obtained using the classical approach
Minimum power multicasting on wireless networks: a shared incumbent environment approach
No full textShared incumbent environment is a new approachwhere a mixed integer linear programming solverand a meta-heuristic search algorithm work in paralleland inform each other when they improve the best knownsolution. In this study, we implement a shared incumbentenvironment by combining simulated annealing with amathematical programming formulation for solving theminimum power multicasting problem, where the goal isto find a topology for the wireless network terminals suchthat the source terminal will be able send data to alldestination terminals with minimized total transmissionpower. We present our results and analyze the success ofshared incumbent environment approach on instances ofdifferent sizes.
Keywords: minimum power multicasting problem; wir
A note on the article “A robust branch-and-cut approach for the minimum-energy symmetric network connectivity problem”
No full textIn the paper Li et al. [A robust branch-and-cut approach for the minimum-energy symmetric network connectivity problem. Omega 2012;40:210–7] it is claimed that a theoretical result appeared in Montemanni and Gambardella [Exact algorithms for the minimum power symmetric connectivity problem in wireless networks. Computers and Operations Research 2005;32:2891–904] is wrong. In this note we show that the original result is correct, and that the counter-example used to prove the wrongness of the original result is incorrect
- …
