@misc{BorndoerferEisenblaetterGroetscheletal.1998, author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {The Orientation Model for Frequency Assignment Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5627}, number = {TR-98-01}, year = {1998}, abstract = {Mobile telecommunication systems establish a large number of communication links with a limited number of available frequencies; reuse of the same or adjacent frequencies on neighboring links causes interference. The task to find an assignment of frequencies to channels with minimal interference is the frequency assignment problem. The frequency assignment problem is usually treated as a graph coloring problem where the number of colors is minimized, but this approach does not model interference minimization correctly. We give in this paper a new integer programming formulation of the frequency assignment problem, the orientation model, and develop a heuristic two-stage method to solve it. The algorithm iteratively solves an outer and an inner optimization problem. The outer problem decides for each pair of communication links which link gets the higher frequency and leads to an acyclic subdigraph problem with additional longest path restrictions. The inner problem to find an optimal assignment respecting an orientation leads to a min-cost flow problem.}, language = {en} } @misc{EisenblaetterGroetschelKoster2000, author = {Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Koster, Arie M.C.A.}, title = {Frequency Planning and Ramifications of Coloring}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6152}, number = {00-47}, year = {2000}, abstract = {This paper surveys frequency assignment problems coming up in planning wireless communication services. It particularly focuses on cellular mobile phone systems such as GSM, a technology that revolutionizes communication. Traditional vertex coloring provides a conceptual framework for the mathematical modeling of many frequency planning problems. This basic form, however, needs various extensions to cover technical and organizational side constraints. Among these ramifications are \$T\$-coloring and list coloring. To model all the subtleties, the techniques of integer programming have proven to be very useful. The ability to produce good frequency plans in practice is essential for the quality of mobile phone networks. The present algorithmic solution methods employ variants of some of the traditional coloring heuristics as well as more sophisticated machinery from mathematical programming. This paper will also address this issue. Finally, this paper discusses several practical frequency assignment problems in detail, states the associated mathematical models, and also points to public electronic libraries of frequency assignment problems from practice. The associated graphs have up to several thousand nodes and range from rather sparse to almost complete.}, language = {en} } @misc{AardalHoeselKosteretal.2001, author = {Aardal, Karen I. and Hoesel, Stan P.M. van and Koster, Arie M.C.A. and Mannino, Carlo and Sassano, Antonio}, title = {Models and Solution Techniques for Frequency Assignment Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6667}, number = {01-40}, year = {2001}, abstract = {{\begin{rawhtml} Revised Version unter http://dx.doi.org/10.1007/s10479-007-0178-0 \end{rawhtml}} Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modelling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.}, language = {en} } @article{BorndoerferEisenblaetterGroetscheletal.1998, author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {Frequency assignment in cellular phone networks}, volume = {76}, journal = {Annals of Operations Research}, publisher = {J. C. Baltzer AG, Science Publishers}, doi = {10.1023/A:1018908907763}, pages = {73 -- 93}, year = {1998}, language = {en} } @inproceedings{BorndoerferEisenblaetterGroetscheletal.1996, author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {Stable-Set and Other Techniques for Frequency Assignment Problems}, booktitle = {Anais da I Oficina Nacional em Problemas de Corte \& Empacotamento}, publisher = {Universidade de S{\~a}o Paulo, Instituto de Matem{\´a}tica e Estat{\´i}stica}, pages = {17 -- 21}, year = {1996}, language = {en} } @phdthesis{Eisenblaetter2001, author = {Eisenbl{\"a}tter, Andreas}, title = {Frequency Assignment in GSM Networks: Models, Heuristics, and Lower Bounds}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10132}, year = {2001}, abstract = {Mobile cellular communcication is a key technology in today's information age. Despite the continuing improvements in equipment design, interference is and will remain a limiting factor for the use of radio communication. This Ph. D. thesis investigates how to prevent interference to the largest possible extent when assigning the available frequencies to the base stations of a GSM cellular network. The topic is addressed from two directions: first, new algorithms are presented to compute "good" frequency assignments fast; second, a novel approach, based on semidef inite programming, is employed to provide lower bounds for the amount of unavoidable interference. The new methods proposed for automatic frequency planning are compared in terms of running times and effectiveness in computational experiments, where the planning instances are taken from practice. For most of the heuristics the running time behavior is adequate for inter active planning; at the same time, they provide reasonable assignments from a practical point of view (compared to the currently best known, but substantially slower planning methods). In fact, several of these methods are successfully applied by the German GSM network operator E-Plus. The currently best lower bounds on the amount of unavoidable (co-channel) interference are obtained from solving semidefinite programs These programs arise as nonpolyhedral relaxation of a minimum /c-parti tion problem on complete graphs. The success of this approach is made plausible by revealing structural relations between the feasible set of the semidefinite program and a polytope associated with an integer linear programming formulation of the minimum ^-partition problem. Comparable relations are not known to hold for any polynomial time solvable polyhedral relaxation of the minimum ^-partition problem. The appli cation described is one of the first of semidefinite programming for large industrial problems in combinatorial optimization.}, language = {en} }