Negative Cycle Separation in Wireless Network
Design∗

arXiv:1704.04656v1 [math.OC] 15 Apr 2017

Fabio D’Andreagiovanni, Carlo Mannino and Antonio Sassano

Abstract The Wireless Network Design Problem (WND) consists in choosing values of radio-electrical parameters of transmitters of a wireless network, to maximize
network coverage. We present a pure 0-1 Linear Programming formulation for the
WND that may contain an exponential number of constraints. Violated inequalities
of this formulation are hard to separate both theoretically and in practice. However,
a relevant subset of such inequalities can be separated more efficiently in practice
and can be used to strengthen classical MILP formulations for the WND. Preliminary computational experience confirms the effectiveness of our new technique both
in terms of quality of solutions found and provided bounds.

Fabio D’Andreagiovanni
Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB), Takustr. 7, D-14195 Berlin, Germany,
e-mail: d.andreagiovanni@zib.de
Carlo Mannino
Department of Computer and System Sciences, Sapienza Università di Roma, via Ariosto 25,
00185 Roma, Italy, e-mail: mannino@dis.uniroma1.it
Antonio Sassano
Department of Computer and System Sciences, Sapienza Università di Roma, via Ariosto 25,
00185 Roma, Italy, e-mail: sassano@dis.uniroma1.it
∗

This work was partially supported by the German Federal Ministry of Education and Research
(BMBF), project ROBUKOM, grant 03MS616E, and by the Italian Ministry of Education,
University and Research (MIUR), project “Design, optimization and analysis of next-generation
converged networks”, grant PRIN 2008LLYXFS.
This is the authors’ final version of the paper published in Pahl J., Reiners T., Vo S. (eds)
Network Optimization. Lecture Notes in Computer Science, vol 6701, pp. 51-56. Springer, Berlin,
Heidelberg. DOI: 10.1007/978-3-642-21527-8 7
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-21527-8 7

1

2

Fabio D’Andreagiovanni, Carlo Mannino and Antonio Sassano

1 Introduction
Wireless networks have shown a rapid growth over the past two decades and now
play a key role in new generation telecommunications networks. Scarce radio resources, such as frequencies, have rapidly became congested and the need for more
effective design methods arose. A general planning problem consists in establishing
the radio-electrical parameters (e.g., power emission and frequency) of the transmitters of a wireless network so as to maximize the overall network coverage. To
present our original contribution, in this paper we focus only on establishing power
emissions. This is actually a basic problem in all wireless planning contexts that can
be easily extended by introducing additional elements, such as frequencies [4, 5].
For our purposes, a wireless network can be described as a set of transmitters B
distributing a telecommunication service to a set of receivers T . Each transmitter
b ∈ B emits a radio signal with power pb ∈ [0, Pmax ]. The power pb (t) that receiver t
gets from transmitter b is proportional to the emitted power pb by a factor atb ∈ [0, 1],
i.e. pb (t) = atb · pb , commonly called fading coefficient. Among the signals received
from transmitters in B, receiver t can select a reference signal (or server), which is
the one carrying the service. All the other signals are interfering.
A receiver t is regarded as served by the network, specifically by server β ∈ B,
if the ratio of the serving power to the sum of the interfering powers (signal-tointerference ratio or SIR) is above a threshold δ [11], (SIR threshold), whose value
depends on the technology and the desired quality of service:
at β · pβ

µ + ∑b∈B\{β } atb · pb

≥δ

(1)

where the system noise µ > 0 is assimilated to an interfering signal with fixed (very
low) power emission.
For every t ∈ T , we have one inequality of type (1) for each potential server β ∈
B: in particular, we denote by SIR(t, b) the inequality (1) associated with receiver t
and server b. Receiver t is served if at least one of these inequalities is satisfied or,
equivalently, if the following disjunctive constraint is satisfied:
!
_

β ∈B

at β · pβ − δ ·

∑

atb · pb ≥ δ · µ

(2)

b∈B\{β }

Each linear inequality of the above disjunction is obtained by simple algebra from
the SIR expression (1).
If each receiver t ∈ T is associated to a value rt > 0 that expresses revenue obtained by serving t, the Wireless Network Design Problem (WND) consists in setting
the power emission of each transmitter b ∈ B and the server of each receiver in t ∈ T
with the aim of maximizing the overall revenue of served receivers.

Negative Cycle Separation in Wireless Network Design

3

2 A pure 0-1 Linear Programming formulation for the WND
The WND is often approached by solving a suitable Mixed-Integer Linear Program
(MILP): first, a binary variable xtb is introduced for every t ∈ T , b ∈ B, with xtb = 1
if and only if b serves t; then, variables xtb are used to replace each disjunction (2)
with a set of |B| linear constraint, that, however, include large positive constants,
the notorious big-M coefficients [5, 7]. The (linear) objective function aims to maximize the overall revenue from coverage, i.e. max ∑t∈T ∑b∈B rt · xtb and requires the
additional constraints:
(3)
∑ xtb ≤ 1 t ∈ T
b∈B

to ensure that each receiver is associated to at most one server. A vector x ∈
{0, 1}T×B satisfying (3) is a server assignment.
The resulting MILP presents severe drawbacks, highlighted in several works, e.g.
[5, 7, 8]. First, the coefficients in the SIR inequalities may vary over a very wide
range, with differences up to 1012 or even larger. This makes the constraint matrix
very ill-conditioned and the solutions returned by solvers are often inaccurate and
may contain errors. Also, the presence of big-M terms results in weak bounds thus
leading to very large search trees. To tackle these problems a number of different approaches were recently proposed. For a comprehensive introduction to these related
works, we refer the reader to [4, 5, 7].
In this paper, we propose an alternative pure 0-1 Linear Programming formulation for the WND, whose defining inequalities are linear constraints in the assignment variables xtb . Such inequalities are thus valid for all the formulations that are
derived from the previously introduced MILPs and can be included to strengthen
them.
Let now x̃ ∈ {0, 1}T×B be a server assignment and let Σ denote the set of all the
SIR inequalities SIR(t, b) and the lower and upper bounds constraints 0 ≤ pb ≤ Pmax
on power emissions. With x̃ we associate the subsystem I(x̃) of SIR inequalities (1)
whose corresponding variables x̃tb are activated, i.e:
I(x̃) = {SIR(t, b) ∈ Σ : x̃tb = 1}
It is easy to check if I(x̃), extended with lower and upper bounds on the variables
pb , is feasible. If this is the case, all of the assigned testpoints can actually be served
by the network, and we say that x is a feasible server assignment.
At this point, we can restate the WND as the problem of finding a feasible server
assignment that maximizes the revenue function. To this aim, a simple characterization of all the feasible server assignments goes as follows. Denote by IS the set of
subsystems I(x) such that x is not feasible. Then x̃ ∈ {0, 1}T×B is a feasible server
assignment if and only if x̃ satisfies the following system of linear inequalities:

∑

(t,b)∈I

x̃tb ≤ |I| − 1

∀ I ∈ IS

(4)

4

Fabio D’Andreagiovanni, Carlo Mannino and Antonio Sassano

The above system is in general very large and the inequalities must be generated
dynamically. Unfortunately, the separation of violated inequalities (4) is hard, both
theoretically and in practice [2, 10]. Moreover, it may entail some of the numerical
difficulties associate with the MILP formulations for the WND. Still, a relevant
subset of these inequalities can be separated more effectively, as we describe next.
To this end, we proceed in a similar way to [8]. Namely, we generate a new
system Σ ′ obtained from Σ by substituting each (1) with the system:
at β · pβ
≥δ
atb · pb

∀ b ∈ B \ {β }

(5)

where, to simplify the notation, we assume that B also contains the noise µ as a
fictitious transmitter with fixed power emission. It is not difficult to see that Σ ′ is a
relaxation of Σ and every infeasible subsystem of Σ ′ corresponds to an infeasible
subsystem of Σ . Basically, this relaxation corresponds to considering a receiver as
served if the power emission of its server suffices to contrast each interferer individually and the thermal noise. Or, alternatively, if its best server is “stronger” than its
strongest interferer. In [8] the authors show that, in most cases of practical interest,
this is indeed a good approximation of the original SIR constraint.
By assuming pb ∈ [ε , Pb ], with ε > 0 very small, and by taking the logarithm2 of
both left and right hand side multiplied by 10, the system Σ ′ can be rewritten as:
qb − qβ ≤ wtβ b

t ∈ T, β ∈ B, b ∈ B \ {β }

(6)

where qb = 10 log10 pb for all b ∈ B and wtβ b = ⌈10(log10 at β − log10 atb − log10 δ )⌉,
extended with the lower and upper bounds 10 log10 ε ≤ qb ≤ 10 log10 Pb , for all b ∈ B.
In this way, the system Σ ′ is transformed into a system of difference inequalities
(lower and upper bounds can be easily represented in this form as well), where
each constraint (6) is associated with a server β and a receiver t and thus with an
assignment variable xt β .
Now, given a generic system of difference constraints Σ d :
(i)

tv − tu ≤ luv , (u, v) ∈ A

(7)

where t ∈ IRA and l ∈ Z A , we can consider the associated weighted directed graph
G = (V, A), with weight function l. Then, it is well known that every infeasible
subsystem of (7) contains (the constraints corresponding to) the arcs of a negative
directed cycle of G [9]. Also, denoting by x ∈ {0, 1}A the incidence vector of (the
arcs corresponding to) a feasible subsystem of Σ d , then x is the set of solutions to:
(i)

∑uv∈C xuv ≤ |C| − 1, C ∈ C −
x ∈ {0, 1}A

where C − is the set of negative directed cycles of G.
2

This corresponds to rewriting all quantities in dB format.

(8)

Negative Cycle Separation in Wireless Network Design

5

In [6] we develop an exact approach to the separation of violated inequalities
(8.i). The resulting algorithm can be used to separate the violated inequalities associated with the system (6) (including upper and lower bounds on the q variables
expressed as difference inequalities) which correspond to negative directed cycles
in the associated directed graph. One of these cycles C corresponds to a subset of
constraints of (6) associated with the pairs IC = {(β1 ,t1 ), . . . , (βm ,tm )} ⊆ B× T (plus
possibly some lower and upper bound constraints).
One can show that β1 6= β2 6= . . . 6= βm and t1 6= t2 6= . . . 6= tm and the valid constraint:
(9)
∑ xtb ≤ |IC | − 1
(t,b)∈IC

may be added to the formulation. In our preliminary results, however, we limit to
consider cycle inequalities with |C| = 2 and separate them by enumeration.

3 Preliminary Computational Results
We test the performance of our new approach to WND on a set of 15 realistic instances, developed with the Technical Strategy & Innovations Unit of British Telecom Italia (BT Italia SpA). All the instances refer to a Fixed WiMAX Network [1],
deployable in an urban residential area and consider various scenarios with up to
|T | = 529 receivers, |B| = 36 transmitters, |F| = 3 frequencies, |H| = 4 burst profiles
(see Table 1). We remark that the experiments refer to a formulation that extends the
basic one considered in Section 1, by including frequency channels and modulation
schemes as additional decision variables. Such formulation is denoted by (BM) and
captures specific features of so-called Next Generation Networks like WiMAX [1].
For a detailed description of (BM), we refer the reader to [3].
For each instance, we present preliminary computational results obtained by
solving the big-M formulation (BM) and its corresponding Power-Indexed formulation (PI) [5]. We consider (BM) and (PI) formulations with and without the valid
inequalities (8) obtained for |C| = 2. Formulations strengthened through (8) are distinguished by adding S-, i.e. (S-BM) and (S-PI).
Experiments are run by imposing a time limit of 1 hour and by using a machine
with a 1.80 GHz Intel Core 2 Duo processor and 2 GB of RAM. Table 1 reports the
performance of the four considered formulations over the set of WiMAX instances.
We solve (BM) and (S-BM) by direct application of IBM ILOG Cplex 11.1 and we
report i) the upper bound UB0 obtained at node 0 of the branch-and-bound tree, ii)
the value |T ∗ | of the best solution found within the time limit and iii) the final integrality gap gap%. The presence of two values in some lines of the column |T ∗ | of
(BM) indicates that the coverage plans returned by Cplex contain errors and some
receivers are actually not covered. We instead solve (PI) and (S-PI) by the incremental algorithm WPLAN described in [5] and we report i) the upper bound UB0
obtained at node 0 when considering the basic set of power levels, and ii) the value
|T ∗ | of the best solution found by WPLAN within the time limit.

6

Fabio D’Andreagiovanni, Carlo Mannino and Antonio Sassano

Table 1 Comparisons between (BM) and (PI) with and without valid inequalities (8)

ID |T| |B| |F| |H|
I1
I2
I3
I4
I5
I6
I7
I8
I9
I10
I11
I12
I13
I14
I15

100
169
196
225
289
361
400
400
441
484
529
400
441
484
529

12
12
12
12
12
12
18
18
18
27
27
36
36
36
36

1
1
1
1
1
1
1
3
3
3
3
1
1
1
1

1
1
1
1
1
1
1
4
4
4
4
4
4
4
4

UB0
98.36
165.47
193.61
219.76
287.20
352.01
397.21
400.00
441.00
484.00
529.00
398.04
433.21
482.78
517.89

(BM)

(S-BM)

|T ∗ |

|T ∗ |

66 (70)
97
102 (105)
92
76 (77)
126 (132)
166
356
266 (270)
120 (122)
77
72 (74)
184
209
98 (105)

gap%
29.43
59.81
77.87
81.13
195.44
154.87
132.01
12.36
63.33
296.72
587
287.30
131.03
108.31
226.44

UB0
96.78
66 (70)
163.15
97
192.02 102 (105)
218.36
92
287.20 76 (77)
350.43
140
396.79
166
400.00
356
441.00 266 (270)
484.00 120 (122)
529.00
77
396.93 77 (78)
431.42
184
481.66
209
516.14
114

(PI)
gap%
27.68
57.39
75.11
79.36
194.92
138.76
131.32
12.36
63.33
296.72
587
264.85
129.77
107.56
198.57

UB0
90.77
153.12
179.35
202.44
274.62
337.22
386.07
396.53
438.28
479.10
523.15
389.61
414.93
472.44
503.32

(S-PI)
|T ∗ |
75
101
108
92
85
156
184
372
295
242
168
102
194
251
232

By adding the new valid inequalities (8) for |C| = 2, in most cases stronger
bounds are obtained at node 0 and smaller integrality gaps are reached within the
time limit. In particular, the benefits are particularly evident in the case of the big-M
formulation: in three cases, namely I6, I12, I15, the value of the best solution is
increased, even eliminating coverage errors (I6, I15).

References
1. Andrews, J.G., Ghosh, A., Muhamed. R.: Fundamentals of WiMAX. Prentice Hall, Upper
Saddle River, USA (2007)
2. Amaldi, E., Kann, V.; The complexity and approximability of finding maximum feasible subsystems of linear relations. Theor. Comput. Sci. 147, 12, 181210 (1995)
3. D’Andreagiovanni, F., Mannino, C.: An Optimization Model for WiMAX Network Planning.
In: Zhang, Y. (ed.) WiMAX Network Planning and Optimization, pp. 369–386. Auerbach
Publications, Boca Raton, USA (2009)
4. D’Andreagiovanni, F.: Pure 0-1 Programming Approaches to Wireless Network Design.
Ph.D. Thesis, Sapienza Università di Roma, Rome, Italy (2010)
5. D’Andreagiovanni, F., Mannino, C., Sassano, A.: GUB Covers and Power-Indexed Formulations for Wireless Network Design. Technical Report vol. 2 n. 14, Department of Computer
and System Sciences, Sapienza Università di Roma, Rome, Italy (2010)
6. D’Andreagiovanni, F., Mannino, C., Sassano, A.: Separating Negative Cycle Inequalities, in
preparation (2010)
7. Kennington, J., Olinick, E., Rajan, D: Wireless Network Design: Optimization Models and
Solution Procedures. Springer, Heidelberg, Germany (2010)
8. Mannino, C., Mattia, S., Sassano, A.: Wireless Network Design by Shortest Path. Comp. Opt.
and Appl. (2009) doi: 10.1007/s10589-009-9264-3

UB0
90.23
152.37
177.92
201.54
274.13
336.46
384.95
395.80
437.52
478.68
521.76
389.14
413.78
471.58
502.67

|T ∗ |
75
101
108
92
85
156
184
372
295
242
168
102
194
251
232

Negative Cycle Separation in Wireless Network Design

7

9. Nehmauser, G., Wolsey, L.: Integer and Combinatorial Optimization. John Wiley & Sons,
Hoboken, USA (1988)
10. Pfetsch, M.: The Maximum Feasible Subsystem Problem and Vertex-Facet Incidence of Polyhedra. Ph.D. Thesis, Technische Universität Berlin, Berlin, Germany (2002)
11. Rappaport, T.S.: Wireless Communications: Principles and Practice, 2nd Edition. Prentice
Hall, Upper Saddle River, USA (2001)

