One major task in wireless network planning is to assign emission powers and frequencies to transmitters so as to maximize the customers coverage (Power and Frequency Assignment Problem, PFAP). We present an optimization model which can be applied whenever the coverage is evaluated through a ¯nite set of testpoints, and the coverage condition of one testpoint can be cast into a linear function of the wanted and interfering signals. This happens, for instance, in mobile telephony and audio/video broadcasting. Natural compact integer programming formulations for PFAP often show large integrality gap and cannot be used to solve instances of practical interest. We present a non-compact Set Packing formulation for PFAP obtained by applying the Dantzig-Wolfe decomposition to the natural formulation. The pricing problem consists in optimizing the emission powers in a single frequency network, for which effective algorithms are available. Experiments show that the non-compact formulation is very tight and the resulting branch-and-price algorithm solves to optimality practically relevant instances of the Italian broadcasting system.

A tight reformulation of the power-and-frequency assignment problem in wireless networks / Mannino, C.; Marinelli, Fabrizio; Rossi, F.; Smriglio, S.. - STAMPA. - Technical Report TRCS 003/2007, Dipartimento di Informatica, Università degli Studi di L'Aquila:(2007).

A tight reformulation of the power-and-frequency assignment problem in wireless networks

MARINELLI, Fabrizio;
2007-01-01

Abstract

One major task in wireless network planning is to assign emission powers and frequencies to transmitters so as to maximize the customers coverage (Power and Frequency Assignment Problem, PFAP). We present an optimization model which can be applied whenever the coverage is evaluated through a ¯nite set of testpoints, and the coverage condition of one testpoint can be cast into a linear function of the wanted and interfering signals. This happens, for instance, in mobile telephony and audio/video broadcasting. Natural compact integer programming formulations for PFAP often show large integrality gap and cannot be used to solve instances of practical interest. We present a non-compact Set Packing formulation for PFAP obtained by applying the Dantzig-Wolfe decomposition to the natural formulation. The pricing problem consists in optimizing the emission powers in a single frequency network, for which effective algorithms are available. Experiments show that the non-compact formulation is very tight and the resulting branch-and-price algorithm solves to optimality practically relevant instances of the Italian broadcasting system.
2007
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11566/79565
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact