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. - 59:1(2013), pp. 142-156. [10.1287/mnsc.1120.1571]
GUB Covers and Power-Indexed Formulations for Wireless Network Design
D'ANDREAGIOVANNI, FABIO;
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.File | Dimensione | Formato | |
---|---|---|---|
VE_2013_11573-466570.pdf
Accesso riservato
Tipologia:
Versione pubblicata dall'editore
Dimensione
298.21 kB
Formato
Adobe PDF
|
298.21 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
1704.06674.pdf
Open access
Tipologia:
Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione
357.48 kB
Formato
Adobe PDF
|
357.48 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris