"Compact and Extended Formulations for Range Assignment Problems"
Technical report by Frank Baumann, Christoph Buchheim, available as BibTeX Source and in portable document format.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2009-582
Keywords:	range assignment, submodular functions, wireless networks
MSC codes:	68M10, 90C27, 90C57
This technical report has 14 pages, was written in March 2009, it has not been published.
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.