TY - GEN A1 - Borndörfer, Ralf A1 - Eisenblätter, Andreas A1 - Grötschel, Martin A1 - Martin, Alexander T1 - The Orientation Model for Frequency Assignment Problems N2 - 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. T3 - ZIB-Report - TR-98-01 KW - Minimum-Cost Flow Problems KW - Cellular Radio Telephone Systems KW - Frequency Assignment Problem KW - Integer Programming Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5627 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Eisenblätter, Andreas A1 - Grötschel, Martin A1 - Martin, Alexander T1 - Frequency Assignment in Cellular Phone Networks N2 - We present a graph-theoretic model for the \emph{frequency assignment problem} in Cellular Phone Networks: Obeying several technical and legal restrictions, frequencies have to be assigned to transceivers so that interference is as small as possible. This optimization problem is NP-hard. Good approximation cannot be guaranteed, unless P = NP. We describe several assignment heuristics. These heuristics are simple and not too hard to implement. We give an assessment of the heuristics' efficiency and practical usefulness. For this purpose, typical instances of frequency assignment problems with up to 4240 transceivers and 75 frequencies of a German cellular phone network operator are used. The results are satisfying from a practitioner's point of view. The best performing heuristics were integrated into a network planning system used in practice. T3 - ZIB-Report - SC-97-35 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3044 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Eisenblätter, Andreas A1 - Grötschel, Martin A1 - Martin, Alexander T1 - Frequency assignment in cellular phone networks JF - Annals of Operations Research Y1 - 1998 U6 - https://doi.org/10.1023/A:1018908907763 VL - 76 SP - 73 EP - 93 PB - J. C. Baltzer AG, Science Publishers ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Eisenblätter, Andreas A1 - Grötschel, Martin A1 - Martin, Alexander T1 - Stable-Set and Other Techniques for Frequency Assignment Problems T2 - Anais da I Oficina Nacional em Problemas de Corte & Empacotamento Y1 - 1996 SP - 17 EP - 21 PB - Universidade de São Paulo, Instituto de Matemática e Estatística ER - TY - GEN A1 - Eisenblätter, Andreas A1 - Fügenschuh, Armin A1 - Koch, Thorsten A1 - Koster, Arie M.C.A. A1 - Martin, Alexander A1 - Pfender, Tobias A1 - Wegel, Oliver A1 - Wessäly, Roland T1 - Modelling Feasible Network Configurations for UMTS N2 - A model for the optimisation of the location and configuration of base stations in a UMTS network is described. The focus is primarily on modelling the configuration problem sufficiently accurate using mixed-integer variables and (essentially) linear constraints. These constraints reflect the limited downlink code capacity in each cell, the interference limitations for successful up- and downlink transmissions, the need for sufficiently strong (cell) pilot signals, and the potential gain for mobiles from being in soft(er) hand-over. It is also explained how to use the model as a basis for rating network configurations. T3 - ZIB-Report - 02-16 KW - UMTS KW - radio interface KW - network planning KW - configuration KW - perfect power control KW - mathematical model KW - mixed integer programming KW - MOMENTUM KW - IST-20 Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6837 ER - TY - GEN A1 - Eisenblätter, Andreas A1 - Geerdes, Hans-Florian A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Wessäly, Roland T1 - UMTS Radio Network Evaluation and Optimization beyond Snapshots N2 - This paper is concerned with UMTS radio network design. Our task is to reconfigure antennas and the related cells as to improve network quality. In contrast to second generation GSM networks, \emph{interference} plays a paramount role when designing third generation radio networks. A known compact formulation for assessing the interference characteristics of a radio network as coupling relations between cells based on user snapshots is generalized to statistical average load. This enables us to overcome the notorious difficulties of snapshot-based network optimization approaches. We recall a mixed-integer programming model for the network design problem that is based on user snapshots and contrast it with a new network design model based on the average coupling formulation. Exemplarily focusing on the important problem of optimizing antenna tilts, we give computational results for a fast local search algorithm and the application of a MIP solver to both models. These results demonstrate that our new average-based approaches outperform state-of-the-art snapshot models for UMTS radio network optimization. T3 - ZIB-Report - 04-15 KW - UMTS KW - Network planning KW - Network design KW - Optimization Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7903 ER - TY - GEN A1 - Eisenblätter, Andreas A1 - Fügenschuh, Armin A1 - Geerdes, Hans-Florian A1 - Junglas, Daniel A1 - Koch, Thorsten A1 - Martin, Alexander T1 - Optimization Methods for UMTS Radio Network Planning N2 - The UMTS radio network planning problem poses the challenge of designing a cost-effective network that provides users with sufficient coverage and capacity. We describe an optimization model for this problem that is based on comprehensive planning data of the EU project MOMENTUM. We present heuristic mathematical methods for this realistic model, including computational results. T3 - ZIB-Report - 03-41 Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7637 ER - TY - CHAP A1 - Eisenblätter, Andreas A1 - Fügenschuh, Armin A1 - Geerdes, Hans-Florian A1 - Junglas, Daniel A1 - Koch, Thorsten A1 - Martin, Alexander T1 - Integer Programming Methods for UMTS Radio Network Planning T2 - Proceedings of the WiOpt’04, Cambridge, UK Y1 - 2004 ER - TY - CHAP A1 - Eisenblätter, Andreas A1 - Fügenschuh, Armin A1 - Koch, Thorsten A1 - Koster, Arie M.C.A. A1 - Martin, Alexander A1 - Pfender, Tobias A1 - Wegel, Oliver A1 - Wessäly, Roland ED - G. Anandalingam, S. T1 - Mathematical Model of Feasible Network Configurations for UMTS T2 - Telecommunications network design and management Y1 - 2002 SP - 1 EP - 24 PB - Kluwer ER - TY - CHAP A1 - Eisenblätter, Andreas A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Achterberg, Tobias A1 - Fügenschuh, Armin A1 - Koster, Arie M.C.A. A1 - Wegel, Oliver A1 - Wessäly, Roland ED - Anandalingam, G. ED - Raghavan, S. T1 - Modelling Feasible Network Configurations for UMTS T2 - Telecommunications Network Design and Management Y1 - 2003 UR - http://opus.kobv.de/zib/volltexte/2002/684/ PB - Kluver ER -