Compact and Extended Formulations for Range Assignment Problems

Baumann, Frank and Buchheim, Christoph (2009) Compact and Extended Formulations for Range Assignment Problems.
Technical Report , 14 p.


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.

Download: [img] PDF
Download (147kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2009-582
Depositing User: Christoph Buchheim
Date Deposited: 13 Mar 2009 00:00
Last Modified: 19 Dec 2011 09:44