W e propose a pure 0-1 formulation for the wireless network design problem, i.e., the problem of configuring a set of transmitters to provide service coverage to a set of receivers. In contrast with classical mixed-integer formulations, where power emissions are represented by continuous variables, we consider only a finite set of power values. This has two major advantages: it better fits the usual practice and eliminates the sources of numerical problems that heavily affect continuous models. A crucial ingredient of our approach is an effective basic formulation for the single knapsack problem representing the coverage condition of a receiver. This formulation is based on the generalized upper bound (GUB) cover inequalities introduced by Wolsey [Wolsey L (1990) Valid inequalities for 0-1 knapsacks and mips with generalised upper bound constraints. Discrete Appl. Math. 29(2-3):251-261]; and its core is an extension of the exact formulation of the GUB knapsack polytope with two GUB constraints. This special case corresponds to the very common practical situation where only one major interferer is present. We assess the effectiveness of our formulation by comprehensive computational results over realistic instances of two typical technologies, namely, WiMAX and DVB-T.

GUB Covers and Power-Indexed Formulations for Wireless Network Design / D'Andreagiovanni, Fabio; Mannino, Carlo; Sassano, Antonio. - In: MANAGEMENT SCIENCE. - ISSN 0025-1909. - STAMPA. - 59:1(2013), pp. 142-156. [10.1287/mnsc.1120.1571]

GUB Covers and Power-Indexed Formulations for Wireless Network Design

D'ANDREAGIOVANNI, FABIO;MANNINO, Carlo;SASSANO, Antonio
2013

Abstract

W e propose a pure 0-1 formulation for the wireless network design problem, i.e., the problem of configuring a set of transmitters to provide service coverage to a set of receivers. In contrast with classical mixed-integer formulations, where power emissions are represented by continuous variables, we consider only a finite set of power values. This has two major advantages: it better fits the usual practice and eliminates the sources of numerical problems that heavily affect continuous models. A crucial ingredient of our approach is an effective basic formulation for the single knapsack problem representing the coverage condition of a receiver. This formulation is based on the generalized upper bound (GUB) cover inequalities introduced by Wolsey [Wolsey L (1990) Valid inequalities for 0-1 knapsacks and mips with generalised upper bound constraints. Discrete Appl. Math. 29(2-3):251-261]; and its core is an extension of the exact formulation of the GUB knapsack polytope with two GUB constraints. This special case corresponds to the very common practical situation where only one major interferer is present. We assess the effectiveness of our formulation by comprehensive computational results over realistic instances of two typical technologies, namely, WiMAX and DVB-T.
0-1 linear programming; gub cover inequalities; power discretization; strong formulation; wireless network design
01 Pubblicazione su rivista::01a Articolo in rivista
GUB Covers and Power-Indexed Formulations for Wireless Network Design / D'Andreagiovanni, Fabio; Mannino, Carlo; Sassano, Antonio. - In: MANAGEMENT SCIENCE. - ISSN 0025-1909. - STAMPA. - 59:1(2013), pp. 142-156. [10.1287/mnsc.1120.1571]
File allegati a questo prodotto
File Dimensione Formato  
VE_2013_11573-466570.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 298.21 kB
Formato Adobe PDF
298.21 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11573/466570
 Attenzione

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

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