Abstract
We propose a pure 0-1 formulation for the wireless network design problem, i.e., the problem of configuring
a set of transmitters to provide service coverage to a set of receivers. In contrast with classical mixedinteger
formulations, where power emissions are represented by continuous variables, we consider only a finite
set of power values. This has two major advantages: it better fits the usual practice and eliminates the sources
of numerical problems that heavily affect continuous models. A crucial ingredient of our approach is an effective
basic formulation for the single knapsack problem representing the coverage condition of a receiver. This
formulation is based on the generalized upper bound (GUB) cover inequalities introduced by Wolsey [Wolsey L
(1990) Valid inequalities for 0-1 knapsacks and mips with generalised upper bound constraints. Discrete Appl.
Math. 29(2–3):251–261]; and its core is an extension of the exact formulation of the GUB knapsack polytope
with two GUB constraints. This special case corresponds to the very common practical situation where only
one major interferer is present. We assess the effectiveness of our formulation by comprehensive computational
results over realistic instances of two typical technologies, namely, WiMAX and DVB-T.
a set of transmitters to provide service coverage to a set of receivers. In contrast with classical mixedinteger
formulations, where power emissions are represented by continuous variables, we consider only a finite
set of power values. This has two major advantages: it better fits the usual practice and eliminates the sources
of numerical problems that heavily affect continuous models. A crucial ingredient of our approach is an effective
basic formulation for the single knapsack problem representing the coverage condition of a receiver. This
formulation is based on the generalized upper bound (GUB) cover inequalities introduced by Wolsey [Wolsey L
(1990) Valid inequalities for 0-1 knapsacks and mips with generalised upper bound constraints. Discrete Appl.
Math. 29(2–3):251–261]; and its core is an extension of the exact formulation of the GUB knapsack polytope
with two GUB constraints. This special case corresponds to the very common practical situation where only
one major interferer is present. We assess the effectiveness of our formulation by comprehensive computational
results over realistic instances of two typical technologies, namely, WiMAX and DVB-T.