REAL

Complexity of different ILP models of the frequency assignment problem

Mann, Zoltán Ádám and Szajkó, Anikó (2012) Complexity of different ILP models of the frequency assignment problem. In: Linear Programming - New Frontiers in Theory and Applications. Nova Science Publishers, pp. 305-326. ISBN 978-1-61209-579-0

[img]
Preview
Text
Mann_Szajko_Nova_2012.pdf - Accepted Version

Download (305kB) | Preview

Abstract

The frequency assignment problem (FAP) arises in wireless communication networks, such as cellular phone communication systems, television broadcasting, WLANs, and military communication systems. In all these applications, the task is to assign frequencies to a set of transmitters, subject to interference constraints. The exact form of the constraints and the objective function vary according to the specific application. Integer linear programming (ILP) is widely used to solve the different flavors of the FAP. For most FAP versions, there are more than one natural ILP formulations, e.g. using a large number of binary variables or a smaller number of integer variables. A common experience with these solution techniques, as well as with NP-hard optimization problems in general, is a high variance in problem complexity. Some problem instances are tremendously hard to solve optimally. There are also examples of relatively big problem instances that are nevertheless quite easy to solve. In general, it is hard to predict how long it will take to solve a given problem instance. This article presents a systematic study of how the complexity of the FAP depends on different parameters of the ILP model. We examine different types of constraints, different problem sizes and constraint densities, and varying sets of available frequen- cies. We conduct empirical measurements with an ILP solver to assess how problem complexity depends on these factors. Based on the empirical data, it becomes possible to predict how time-consuming the solution of a given problem instance is, depending on the ILP model parameters. The ability to predict complexity is useful in several scenarios. First of all, it allows a sound judgement whether it is feasible to solve a given ILP formulation optimally. Moreover, it also supports sophisticated load-balancing when multiple FAPs are solved on parallel machines. Eventually, a better understanding of the origins of complexity may lead to enhanced optimization techniques.

Item Type: Book Section
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: Dr. Zoltán Ádám Mann
Date Deposited: 22 Sep 2014 20:54
Last Modified: 03 Apr 2023 08:16
URI: http://real.mtak.hu/id/eprint/16013

Actions (login required)

Edit Item Edit Item