Optimization Online


Towards an accurate solution of wireless network design problems

Fabio D’Andreagiovanni(d.andreagiovanni***at***zib.de)
Ambros M. Gleixner(gleixner***at***zib.de)

Abstract: The optimal design of wireless networks has been widely studied in the literature and many optimization models have been proposed over the years. However, most models directly include the signal-to-interference ratios representing service coverage conditions. This leads to mixed-integer linear programs with constraint matrices containing tiny coefficients that vary widely in their order of magnitude. These formulations are known to be challenging even for state-of-the-art solvers: the standard numerical precision supported by these solvers is usually not sufficient to reliably guarantee feasible solutions. Service coverage errors are thus commonly present. Though these numerical issues are known and become evident even for small-sized instances, just a very limited number of papers has tried to tackle them, by mainly investigating alternative non-compact formulations in which the sources of numerical instabilities are eliminated. In this work, we explore a new approach by investigating how recent advances in exact solution algorithms for linear and mixed-integer programs over the rational numbers can be applied to analyze and tackle the numerical difficulties arising in wireless network design models.

Keywords: network design; exact computation; accurate mixed-integer linear programming; numerics

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: ZIB-Report 16-12, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustraße 7, 14195 Berlin, ISSN 1438-0064, April 2016, accepted for publication in the Proceedings of the 4th International Symposium on Combinatorial Optimization (ISCO)

Download: [PDF]

Entry Submitted: 05/10/2016
Entry Accepted: 05/10/2016
Entry Last Modified: 05/10/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society