Universität zu Köln

Baumann, Frank and Buchheim, Christoph ORCID: 0000-0001-9974-404X (2009). Compact and Extended Formulations for Range Assignment Problems. Working Paper.

Preview

PDF zaik2009-582.pdf Download (147kB) | Preview

Abstract

We devise two new integer programming models for range assignment problems arising in wireless network design. Building on an arbitrary set of feasible network topologies, e.g., all spanning trees, we explicitly model the power consumption at a given node as a weighted maximum over edge variables. We show that the standard ILP model is an extended formulation of the new models. For all models, we derive complete polyhedral descriptions in the unconstrained case where all topologies are allowed. These results give rise to tight relaxations even in the constrained case. We can show experimentally that the compact formulations compare favorably to the standard approach.

Item Type:	Preprints, Working Papers or Reports (Working Paper)
Creators:	Creators Email ORCID ORCID Put Code Baumann, Frank UNSPECIFIED UNSPECIFIED UNSPECIFIED Buchheim, Christoph UNSPECIFIED orcid.org/0000-0001-9974-404X UNSPECIFIED
URN:	urn:nbn:de:hbz:38-549822
Date:	2009
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54982