The Wireless Network Design Problem (WND) consists in choosing values of radio-electrical parameters of transmitters of a wireless network, to maximize network coverage. We present a pure 0-1 Linear Programming formulation for the WND that may contain an exponential number of constraints. Violated inequalities of this formulation are hard to separate both theoretically and in practice. However, a relevant subset of such inequalities can be separated more efficiently in practice and can be used to strengthen classical MILP formulations for the WND. Preliminary computational experience confirms the effectiveness of our new technique both in terms of quality of solutions found and provided bounds. © 2011 Springer-Verlag.

Negative cycle separation in wireless network design / D'Andreagiovanni, Fabio; Mannino, Carlo; Sassano, Antonio. - 6701 LNCS:(2011), pp. 51-56. (Intervento presentato al convegno 5th International Conference on Network Optimization, INOC 2011 tenutosi a Hamburg nel 13 June 2011 through 16 June 2011) [10.1007/978-3-642-21527-8_7].

Negative cycle separation in wireless network design

D'ANDREAGIOVANNI, FABIO;
2011

Abstract

The Wireless Network Design Problem (WND) consists in choosing values of radio-electrical parameters of transmitters of a wireless network, to maximize network coverage. We present a pure 0-1 Linear Programming formulation for the WND that may contain an exponential number of constraints. Violated inequalities of this formulation are hard to separate both theoretically and in practice. However, a relevant subset of such inequalities can be separated more efficiently in practice and can be used to strengthen classical MILP formulations for the WND. Preliminary computational experience confirms the effectiveness of our new technique both in terms of quality of solutions found and provided bounds. © 2011 Springer-Verlag.
2011
5th International Conference on Network Optimization, INOC 2011
Hamburg
13 June 2011 through 16 June 2011
6701 LNCS
51
56
D'Andreagiovanni, Fabio; Mannino, Carlo; Sassano, Antonio
Negative cycle separation in wireless network design / D'Andreagiovanni, Fabio; Mannino, Carlo; Sassano, Antonio. - 6701 LNCS:(2011), pp. 51-56. (Intervento presentato al convegno 5th International Conference on Network Optimization, INOC 2011 tenutosi a Hamburg nel 13 June 2011 through 16 June 2011) [10.1007/978-3-642-21527-8_7].
File in questo prodotto:
File Dimensione Formato  
VE_2011_11573-499537.pdf

Accesso riservato

Dimensione 254.7 kB
Formato Adobe PDF
254.7 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
WND-negative-cycles_LNCS2.pdf

Accesso riservato

Dimensione 112.78 kB
Formato Adobe PDF
112.78 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1331554
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 14
social impact