Conception Topologique des Réseaux de

Télécommunication Cellulaires par la

Décomposition de Benders
M. El M. Diop∗ A. Benchakroun† P. Mahey‡

September 8, 2006

Abstract
La conception topologique des réseaux de télécommunication cel-
lulaires de type GSM est un procédé complexe qui se traitait en deux
problèmes séparés, un problème de localisation des différents équipe-
ments et un autre pour la couverture des zones ou pour l’allocation de
fréquences. Nous développons dans ce rapport un modèle qui comprend
à la fois l’aspect localisation et l’aspect couverture des différentes zones
sans tenir compte de l’aspect allocation de fréquences. Un modèle de
programmation linéaire mixte est proposé. Avec la taille du problème
une résolution directe serait non réaliste. Un algorithme de résolution
utilisant la méthode de Benders est présenté. Des résultats numériques
montrant l’efficacité des méthodes proposées par rapport à une résolu-
tion directe du modèle classique par Cplex sont donnés.

Abstract
Designing a GSM telecommunication network is a tough work. To
handle this problem many problems such as location, coverage and fre-
quency assignment are presented in the literature. With this approach
each problem is treated separately. In this paper, we propose an inte-
grated model combining location problem, link plane and the coverage
of all areas without frequency allocation. Our model is presented as a
large scale mixed linear integer programming. Due to the size of the
problem, a direct solution could be unrealistic, that’s why we propose
an approach based on Benders decompostion method. The numerical
experiments performed on large scale problems show that the solutions
obtained with our approach is better than those given by Cplex.
∗
Université de Sherbrooke, Département de Mathématiques, Sherbrooke, Canada,
†
Université de Sherbrooke, Département d’Informatique, Sherbrooke, Canada,
‡
Limos, ISIMA, Université Blaise Pascal, Clermont-Ferrand, France.

1
1 Introduction
Dans ce rapport, on présente la conception topologique des réseaux de
télécommunication cellulaires (CTRTC) de type GSM. La CTRTC consiste,
étant donné un ensemble de sites prédéfini pour l’installation d’équipements,
à sélectionner un sous-ensemble à activer et à trouver un plan pour les con-
necter à moindre coût. Ce coût est constitué des coûts d’installation et de
connexion des sites. Un réseau de télécommunication cellulaire de type GSM
est composé d’un ensemble d’équipements reliés entre eux. Il est destiné à
offrir un service de communication sans fil aux abonnés demeurant dans une
région divisée en zones.
L’objectif principal d’un système radiomobile est de permettre l’accès
au réseau téléphonique à partir d’un terminal portatif, communément ap-
pelé portable ou mobile, sur toute l’étendue du territoire à couvrir. Une
liaison radioélectrique est utilisée entre le terminal portatif et le réseau.
Le réseau GSM se présente sous la forme d’une structure hiérarchisée com-
posée de 3 niveaux:
- le sous-système radio BSS (Base Station Sub-system) qui assure les trans-
missions radioélectriques et gère la ressource radio. Il est composé de: BTS
(Base Transceiver Station) qui sont des émetteurs-récepteurs et qui assurent
l’interface entre la partie mobile et la partie fixe; BSC(Base Station Con-
troller) qui contrôlent un ensemble de BTS et permettent une première con-
centration des circuits.
- le sous-système d’acheminement appelé réseau fixe NSS (Network Sub-
System). Il est composé de: MSC (Mobiles-services Switching Center) qui
représentent les centres de communication assurant l’interconnexion avec le
réseau fixe et le routage, HLR (Home Location Register) qui sont des bases
de données qui gèrent les abonnés, VLR(Visitor Location Register) qui sont
des bases de données qui mémorisent les données d’abonnement des abonnés
présents à l’intérieure d’une zone géographique.
- le sous-système d’exploitation et de maintenance OSS (Operation Sub-
system) qui permet à l’exploitant d’administrer son réseau.
L’introduction de la mobilité dans les réseaux de télécommunication
a nécessité la définition de nouvelles fonctions par rapport aux réseaux fixes
classiques. Le système doit connaı̂tre la position de chaque terminal mobile
pour pouvoir le joindre (fonction d’itinérance). Contrairement aux réseau de
téléphonie fixe où un numéro correspond à une adresse physique fixe (prise
de téléphone), le numéro d’un terminal mobile devient du point de vue du
réseau, une adresse logique constante à laquelle il faut faire correspondre
une adresse physique qui, elle, varie au gré des déplacements [14].

2
 Dans la littérature beaucoup de travaux sur la conception de réseaux
de télécommunication ont porté sur les réseaux d’accés locaux. Dans [6], le
modèle qui est développé consiste à relier un noeud origine à un ensemble
de noeuds terminaux qui ont un flot de demande à satisfaire. Sur chaque
arc une des deux sortes de technologies disponibles, à savoir fibre optique ou
cuivre, doit être installée. La méthode de décomposition de Benders a été
utilisée pour résoudre le modèle. Dans le domaine du cellulaire et surtout
dans les réseaux de type GSM, les publications deviennent rares. Certains
travaux se sont limités à développer des modèles d’optimisation de la local-
isation des antennes tout en satisfaisant une meilleure couverture des zones
[13]. D’autres travaux ont porté sur une modélisation regroupant, dans le
même problème, la détermination d’un plan d’installation des antennes et
d’allocation des fréquences [8] et [9]. Dans [4], l’auteur nous présente une
minimisation de l’impact de la mobilité des abonnés sur les ressources dans
un réseau de type GSM.

La conception d’un réseau de téléphonie cellulaire se pose comme suit:

étant donné un ensemble de sites candidats à l’installation d’équipements
et les prévisions de trafic, déterminer un plan d’installation et de connexion
des équipements, qui permettrait de satisfaire toute la demande au niveau
des cellules au moindre coût.

Ce rapport est organisé de la manière suivante: à la section 2 on

présente une formulation du modèle, la section 3 est consacrée à l’approche
de résolution par la méthode de Benders, dans la section 4 on donne les
résultats numériques pour conclure dans la section 5.

2 Formulation du Modèle classique

Dans l’approche que l’on considère, le terme antenne ou BTS désigne l’ensem-
ble constitué par la BTS et les antennes fixées sur cette BTS. La configura-
tion de chaque antenne est prédéfinie.
Notation
Les notations ci-dessous sont utilisées tout au long de ce travail. A, B, et M
sont respectivement les ensembles des sites prédéfinis pour l’installation des
BTS, des BSC et des MSC. Z est l’ensemble des zones à couvrir.
Constantes
Az ensemble des antennes a qui peuvent couvrir tout ou une partie de la

3
zone z.
Za ensemble des zones z qui peuvent être couvertes partiellement ou totale-
ment par l’antenne a.
Ba ensemble des BSC b qui peuvent être connectées à l’antenne a.
Bz ensemble des zones qui peuvent être connectées par une antenne pouvant
être connectée à la BSC b.
Ab ensemble des antennes a qui peuvent être reliées au BSC b.
Bm ensemble des BSC b qui peuvent être connectées au MSC m.
Mb ensemble des MSC m qui peuvent être connectées au BSC b.
Paramètres
• Ea , Eb , Em sont respectivement les coûts d’installation des BTS, des
BSC et des MSC.
• dz quantité de trafic demandée au niveau de la zone z.
• rz revenu par unité de demande pour une zone z
• lab coût d’une liaison entre un BSC et une BTS.
• lbm coût d’une liaison entre un MSC et un BSC.
• Qm est le nombre maximal de BSC que pourrait connecter un MSC.
• Qb est le nombre maximal de BTS que pourrait connecter un BSC.
• qa la capacité de la BTS a de gérer le trafic issu des zones qu’elle couvre.
Variables
• xza est une variable donnant la part du trafic dans la zone z capté par
une BTS a.
• variables de connexion:
uab = 1 si la BTS a est connectée au BSC b et 0 sinon;
ubm = 1 si le BSC b est connectée au MSC m et 0 sinon.
• variables d’installation d’équipements
ya = 1 si le site a est choisi pour installer une BTS et 0 sinon;
yb = 1 si le site b est choisi pour installer un BSC et 0 sinon;
ym = 1 si le site m est choisi pour installer un MSC et 0 sinon.

2.1 Définition de la fonction économique

L’objectif de tout opérateur de télécommunication, en fournissant du service,
est de tirer le maximum de profit généré par la couverture des zones pour
rentabiliser les investissements. La mise en place des équipements entraı̂ne
des coûts d’installation et de connexion tandis que l’exploitation du réseau
va générer des revenus.
La fonction économique va donc être composée de deux termes:

* le revenu total engendré par la couverture des zones:

4
 X X
RT x = rz dz xza
a∈A z∈Za
x étant le vecteur des variables de couverture des différentes zones,
x = (xza )z∈Z, a∈A .
R représente le vecteur des revenus engendrés par la couverture des
zones.
* la somme des coûts encourus par le déploiement des équipements:
- coût d’installation
X des
X équipements:
X
T
C1 y = Ea ya + Eb y b + Em y m
a∈A b∈B m∈M
y étant le vecteur des variables d’installation d’équipements,
y = (ya , yb , ym )a∈A,b∈B,m∈M
C1 vecteur des coûts d’installation des équipements.
- coût de X
connexion
X des équipements
X X du réseau:
C2T u = lab uab + lbm ubm
b∈B a∈Ab m∈M b∈Bm
u étant le vecteur des variables d’installation d’arcs du réseau,
u = (uab , ubm )a∈A,b∈B,m∈M
C2 vecteur des coûts de liaison des équipements.
Il s’agit dans cette étude de minimiser P (x, u, y) avec:
P (x, u, y) = C(u, y) − R(x), où C(u, y) = C1T y + C2T u.
Notons que le coût de couverture des zones n’est pas pris en compte car
les liaisons entre les BTS et les zones à couvrir sont faites à l’aide d’ondes
radio-électriques. Cette couverture dépend des échanges entre l’usager dont
l’appareil est en mode veille et la BTS qui capte son signal. Les coûts de
maintenance et d’entretien du réseau ne sont pas aussi pris en compte dans
cette étude.

2.2 Définition des contraintes

Nous allons définir trois ensembles de contraintes qui caractérisent la cou-
verture des zones, l’installation des équipements et la topologie du réseau.

Contraintes de couverture des zones

• Chaque zone z doit être totalement couverte:
X
xza = 1, ∀z ∈ Z. (1)
a∈Az

Dans ce cas, la demande est totalement satisfaite et RT x = C te .

5
 • La part de la demande de trafic couverte par une antenne ne doit pas
dépasser sa capacité:
X
dz xza − qa ya ≤ 0, ∀ a ∈ A. (2)
z∈Za

Cette contrainte sert aussi de couplage entre les variables ya et xza .

Une BTS non activée ne peut pas couvrir de zone.

• La part xza de la demande de la zone z couverte par l’antenne a

représente un pourcentage donc est au plus égale à 1:

xza ≤ 1, ∀z ∈ Z, ∀a ∈ Az . (3)

Contraintes d’installation d’équipements

• Chaque zone z est gérée par au moins une BTS:
X
ya ≥ 1, ∀z ∈ Z. (4)
a∈Az

• ya = 0 signifie la non installation de l’équipement a et entraı̂ne la non

existence de lien avec un BSC. Si ya = 1, l’installation d’une antenne
implique sa connexion avec un unique BSC. Donc l’activation de tout
site a prédéfini pour l’installation d’une BTS, équivaut à l’existence
d’une liaison entre a et au plus un BSC:
X
ya − uab = 0, ∀a ∈ A (5)
b∈Ba

• Si une BTS a est choisie, il existe au moins un BSC b choisi qui puisse
la connecter:
X
ya − yb ≤ 0, ∀a ∈ A. (6)
b∈Ba

• yb = 0 signifie la non installation d’un BSC b et implique la non

existence de lien avec un MSC. Si yb = 1, l’installation du BSC b
implique sa connexion avec un unique MSC. Donc l’activation de tout
BSC b ∈ B équivaut à l’existence d’une liaison entre b et au plus un
MSC m:
X
yb − ubm = 0, ∀b ∈ B. (7)
m∈Mb

6
 • Il existe au moins un BSC b ∈ Bz qui connecte au moins une antenne
a ∈ Az :
X
yb ≥ 1, ∀z ∈ Z. (8)
b∈Bz

• Il existe au moins un MSC m qui connecte au moins un BSC b ∈ Bz :

X
ym ≥ 1, ∀z ∈ Z. (9)
m∈Mz

• Si un BSC b est choisi alors il existe au moins un MSC m choisi qui

puisse le connecter:
X
yb − ym ≤ 0, ∀b ∈ B. (10)
m∈Mb

Contraintes de topologie du réseau

• Pour chaque zone z, il existe au moins un arc reliant un élément de

Az et un élément de Bz pour que celle-ci soit couverte:
X X
uab ≥ 1, ∀z ∈ Z. (11)
b∈Bz a∈Az

• Une BTS a ne peut être connectée qu’à un unique BSC b:

X
uab ≤ 1, ∀a ∈ A. (12)
b∈Ba

• Le nombre de liaisons entre un BSC b et les BTS qui sont dans son
voisinage ne peut être supérieur à sa capacité:
X
uab − Qb yb ≤ 0, ∀b ∈ B. (13)
a∈Ab

• Si un BSC b est activé alors il existe au moins un arc le reliant à une

BTS a:
X
yb − uab ≤ 0, ∀b ∈ B. (14)
a∈Ab

7
 • Si un MSC m est activé alors il existe au moins un arc le reliant à un
BSC b:
X
ym − ubm ≤ 0, ∀m ∈ M. (15)
b∈Bm

• Le nombre de liaisons entre un MSC m et les BSC qui sont dans son
voisinage ne peut être supérieur à sa capacité:
X
ubm − Qm ym ≤ 0, ∀m ∈ M. (16)
b∈Bm

• Un lien existe entre une BTS a et un BSC b s’il existe au moins un

lien entre un MSC m et le BSC b:
X
uab − ubm ≤ 0, ∀a ∈ A, ∀b ∈ B. (17)
m∈Mb

• Un lien existe entre un MSC m et un BSC b s’il existe au moins un

lien entre une BTS a et le BSC b:
X
ubm − uab ≤ 0, ∀b ∈ B, ∀m ∈ M. (18)
a∈Ab

• Un BSC b ne peut être connecté qu’à un seul MSC m:

X
ubm ≤ 1, ∀b ∈ B. (19)
m∈Mb

• L’existence d’un arc implique l’installation des équipements qui for-

ment ses extrêmités:

uab − ya yb ≤ 0, ∀a ∈ A, ∀b ∈ B, (20)
ubm − yb ym ≤ 0, ∀b ∈ B, ∀m ∈ M. (21)

Contraintes sur les variables

• La variable de couverture d’une zone doit être positive:

xza ≥ 0, ∀z ∈ Z, ∀a ∈ Az . (22)

• Les variables d’installation d’équipements sont binaires:

ya , y b , y m ∈ {0, 1}, ∀a ∈ A, ∀b ∈ B, ∀m ∈ M. (23)

8
 • Les variables d’activation d’arcs sont binaires:

uab , ubm ∈ {0, 1}, ∀a ∈ A, ∀m ∈ M, ∀b ∈ B. (24)

Remarque 1 X
Généralement la contrainte xza = 1, ∀z ∈ Z est remplacée par les
a∈Az
contraintes suivantes:
X
xza ≤ 1, ∀z ∈ Z (R.1),
a∈A
Xz
xza ≥ 0.98, ∀z ∈ Z (R.2).
a∈Az

(R.1) et (R.2) signifient qu’une part minimale de trafic de chaque zone

doit être couverte afin d’offrir une meilleure qualité de service. Le taux
de couverture minimale est fixé par l’opérateur suivant la qualité de service
visée. La valeur 0.98 de la contrainte (R.2) est donnée à titre indicatif. Pour
notre part nous avons opté pour un modèle avec la contrainte égalitaire car,
comme nous le verrons plus loin, cela ne complique pas le modèle mais au
contraire permet de simplifier la fonction objectif et facilite la résolution du
modèle avec l’approche de décomposition de Benders.

2.3 Modèle de conception

Le modèle mathématique peut s’écrire alors:

 min
 C1T y + C2T u − RT x
0
(P ) sujet à:

 (1) à (24).

2.3.1 Linéarisation de contraintes

Les contraintes (20) et (21) ne sont pas linéaires. Afin d’obtenir un problème
linéaire nous allons procéder à une linéarisation de ces contraintes.
• La contrainte (20) implique que :
∗ si l’une au moins des deux variables ya ou yb est nulle alors uab = 0.
∗ si uab = 1, alors les variables ya et yb sont à la fois égales à 1.
Or uab ne peut prendre que les valeurs 0 ou 1; la contrainte (20) est donc
équivalente à: (
uab ≤ ya , ∀ a ∈ A, ∀ b ∈ B,
uab ≤ yb , ∀ a ∈ A, ∀ b ∈ B.

9
De même, la contrainte (21) s’écrit:
(
ubm ≤ yb , ∀b ∈ B, ∀m ∈ M,
ubm ≤ ym , ∀b ∈ B, ∀m ∈ M.

Le modèle (P ) peut être simplifié en remarquant que les contraintes (11),

(12), (13), (14), (19), (20) et (21) peuvent être suprimées puisqu’elles sont
implicitement contenues dans d’autre contraintes.

2.3.2 Simplification de la fonction économique

X
En utilisant la contrainte d’égalité suivante xza = 1, ∀ z ∈ Z,
a∈Az
le terme de la fonction objectif représentant le revenu engendré par la cou-
verture
X X des zones peutX se simplifier de la manière suivante:
(−rz )dz xza = (−rz )dz .
a∈A z∈Z z∈Z

2.3.3 Modèle de référence

Ces différentes modifications faites, le modèle de référence, qui est équivalent
au problème (P 0 ), que l’on considère est le suivant:

 min
 C(y, u) = C1T y + C2T u
(P ) sujet à:

 (1) à (10), (15), (16), (17), (18), (22), (23), (24).

On définit les ensembles suivants:

X = {x : (1) et (22), soient vérifiées}, Y = {y : (23), soit vérifiée},
U = {u : (24), soit vérifiée}.
G(x, y, u) = A(x) − g(y, u), représente la matrice des contraintes liant les
variables x et (y, u) et H(y, u) la matrice des contraintes fonction des vari-
ables y ou u.
Le modèle peut s’écrire sous-forme matricielle de la manière suivante:

C(y, u) = C1T y + C2T u



 min
 sujet à:



(P) A(x) − g(y, u) ≤ 0;
H(y, u) ≤ 0;





(y, u) ∈ Y × U, x ∈ X.


La méthode de Benders semble être une méthode appropriée pour résoudre

ce type de problème. C’est une méthode bien adaptée pour traiter des

10
problèmes dans lesquels interviennent deux groupes de variables différents,
de telle sorte que la fixation des variables de l’un des groupes, dites variables
compliquantes, réduit le problème initial en un problème de programmation
linéaire facile à traı̂ter.
Notre modèle regroupe deux types de problèmes: un problème de
détermination d’une topologie représentée par la variable (y, u) et un autre
problème de couverture des zones représentée par la variable (x). Ainsi il
s’agit de trouver une topologie capable de couvrir toutes les zones à moindre
coût. Ce qui donne une motivation d’appliquer la méthode de Benders.
Dans les prochains paragraphes, on applique l’algorithme de Benders
au modèle et dans la dernière partie on va présenter les résultats numériques.

3 Approche de résolution utilisant la méthode de

décomposition de Benders
La méthode de décomposition de Benders a été initialement développée
par Benders en 1962, [10], pour résoudre des problèmes de programmation
linéaires mixtes. Geoffrion a proposé une généralisation de la méthode au
cas non linéaire, sous certaines conditions, [3]. Cette décomposition a été
appliquée au problème de conception de réseau dans différentes situations
telles que le problème de localisation de concentrateurs, l’optimisation de la
conception topologique. Cette méthode a été utilisée aussi pour résoudre la
conception de reseaux d’accés locaux avec deux sortes de technologies [6],
pour résoudre la conception de réseaux avec une structure d’arbre [1] et pour
trouver une solution au problème d’affectation de capacités et de flots dans
un réseau de communication, [12].
Le problème se partitionne en deux composantes : la première, appelée
Problème Maı̂tre Relaxé (P M R), contient la définition de l’ensemble des
variables s = (y, u), la seconde, le Sous-Problème (SP ), contient la définition
de l’ensemble des variables x, où les variables s = (y, u) sont fixées. Le pro-
cessus de résolution est un processus itératif au cours duquel le problème
maı̂tre relaxé (P M R) va progressivement être enrichi d’informations prove-
nant du (SP ). Au bout d’un certain nombre fini d’itérations, le processus
soit fournit une solution optimale, soit indique la non-réalisabilité du système
de contraintes.
Le problème (P) est composé de 2 types de variables : les variables
entières y et u qui représentent respectivement les variables d’installation et
de liaison des équipements, et les variables continues x qui représentent la
couverture des zones.

11
Posons : Y = {(y, u) ∈ Y × U : H(y, u) ≤ 0 }, le problème (P) peut alors
s’écrire:


 min C1T y + C2T u

 sujet à:
(P)

 AT x ≤ g(y, u),


x ∈ X, (y, u) ∈ Y.

La projection de (P) sur l’espace des variables (y, u) s’écrit:


(PP) min {C1T y + C2T u + inf {0 : AT x ≤ g(y, u)}}.
(y,u)∈Y x∈X

Posons :

v(y, u) = inf {0 : AT x ≤ g(y, u)} = max{φT g(y, u) : Aφ ≤ 0}

x∈X φ≥0
φ étant le vecteur des variables duales.
V = {(y, u) : AT x − g(y, u) ≤ 0, pour au moins un x ∈ X}.

Alors le problème suivant est équivalent au problème (P P ):

min C1T y + C2T u.

(y,u)∈Y∩V

(y, u) ∈ Y ∩ V si et seulement si (φi )T g(y, u) ≤ 0, où φi représentent

l’ensemble des vecteurs générateurs qui engendrent {Aφ ≤ 0}.


 min C1T y + C2T u

 sujet à:

 φT g(y, u) ≤ 0,


(y, u) ∈ Y.

Le sous-problème correspond au problème de programmation linéaire suivant

(pour (y, u) fixé) :
Sous-problème


 min 0




 sujet à: X
dz xza ≤ qa y a , ∀a ∈ A,



(SP(y,u) ) z∈Z
Xa

xza = 1, ∀z ∈ Z,







 a∈Az

x ≥ 0.

12
Deux méthodes sont utlisées pour déterminer le vecteur des multiplicateurs
qui permettent de construire la coupe. Une première méthode décrite par
l’algorithme 1 consiste à utiliser la méthode des deux phases du simplexe1
pour déterminer les multiplicateurs optimaux. La deuxième méthode décrite
par l’algorithme 2, exploite les caractéristiques de la structure du réseau pour
trouver les multiplicateurs.

3.1 Algorithme 1
L’objectif du sous-problème (SP(y,u) ) est constant, ainsi donc toute solution
réalisable est optimale. Pour voir si SP(y,u) admet une solution réalisable ou
non, on applique la méthode des deux phases du simplexe. La première
phase, par l’intermédiaire du problème auxiliaire permettra de tester la
réalisabilité du sous-problème et de déduire les multiplicateurs optimaux.
Le sous-problème auxiliaire (SP A(y,u) ) de la phase I du sous-problème, pour
(y, u) = (y, u) fixé s’écrit:

eT t


 min




 sujet à: X
dz xza + xa + t1a = qa y a , ∀ a ∈ A, λa



(SPA(y,u) ) z∈Z
Xa
xza + t2z = 1,

∀z ∈Z, µz







 a∈Az

x, xa , t ≥ 0.

Où e = (1, 1, ..., 1), t1 = (t1a ), t2 = (t2z ), t = (t1 , t2 ) et x = (xza )

Soit (x, xe , t) la solution optimale. Si eT t = 0, alors x en est une solution
optimale.
Si par contre eT t > 0, alors SP(y,u) est non-réalisable et les variables duales
de SP A(y,u) seront utilisées pour formuler la coupe de réalisabilité. Le
problème dual du problème auxiliaire SP A(y,u) s’écrit:
 X X

 max −qa y a λa + µz



 a∈A z∈Z
 sujet à:



(DSPA(y,u) ) −dz λa + µz ≤ 0, ∀a ∈ A; ∀z ∈ Z,
λa ≤ 1, ∀a ∈ A,




µz ≤ 1, ∀z ∈ Z,





λa ≥ 0, ∀a ∈ A.


1
Utilisée souvent pour trouver une solution réalisable de base initiale avant de démarrer
la méthode du simplexe.

13
Le sous-problème (SP(y,u) ) est réalisable, si et seulement si,
X X
µz − λa qa y a ≤ 0, d’après la théorie de la dualité.
z∈Z a∈A
Donc si {(λi , µi ), i = 1, ..., p} est l’ensemble des rayons extrêmes de
(DSP A(y,u) ), alors (y, u) ∈ V , si et seulement si
X X
−qa y a λia + µiz ≤ 0, ∀i = 1, ..., p.
a∈A z∈Z
Le problème maı̂tre qui est équivalent au problème (P P ) va s’écrire alors :




min C1T y + C2T u
 sujet à:


X X
(PM) −qa y a λia + µiz ≤ 0, ∀i = 1, ..., p (CR),



 a∈A z∈Z
(y, u) ∈ Y.



Une approche de relaxation va être utilisée pour résoudre le problème (P M ).

À chaque itération une partie des contraintes (CR) est considérée, dans un
problème appelé problème maı̂tre relaxé, (P M R), qui sera résolu. Les autres
contraintes seront rajoutées à ce problème au fur et à mesure que cela est
nécessaire. L’algorithme de résolution est défini de la manière suivante:
Algorithme de résolution 1:
Étape 0:
Résoudre une version relaxée du problème maı̂tre ne contenant pas de coupe
de réalisabilité. Soit (y 0 , u0 ) une solution optimale. Aller à l’étape 2.
Étape 1:
À la k − ième itération résoudre le problème maı̂tre relaxé P M R. Soit
(y k , uk ) une solution optimale.
Étape 2:
Résoudre le sous-problème auxiliare. Soit (xk , tk ) sa solution optimale.
Vérifier si les contraintes relaxées du sous-problème sont satisfaites.
- Si la fonction objectif du sous-problème auxiliaire est strictement positive
alors déterminer les vecteurs de multiplicateurs optimaux et générer la coupe
de réalisabilité. Retourner à l’étape 1 pour former un nouveau (P M R).
- Sinon, xk est réalisable et optimale pour le sous-problème (SP(yk ,uk ) ).
L’algorithme s’arrête: (xk , y k , uk ) est une solution optimale pour le problème
original.
Dans la sous-section suivante, nous donnons une procédure qui permet
de générer les coupes de réalisabilité sans avoir à résoudre le sous-problème
auxiliaire.

14
3.2 Algorithme 2
Pour trouver une solution réalisable du problème dual (DSP A(y,u) ), on
va diviser l’ensemble A en sous-ensembles qui facilitent le traitement de
la première contrainte. Considérons une topologie (y, u) fournie par le
problème maı̂tre. Le terme qui contribue à diminuer la valeur de la fonction
objectif est le coefficient négatif de la variable λ. Ce coefficient, −qa y a , est
nul si y a = 0, c’est-à-dire si la BTS a n’est pas choisie. Remarquons que le
fait de prendre λa = 0 pour toute BTS a telle que y a = 1, ne contribuera pas
nécessairement à augmenter la valeur de la fonction objectif. Nous utilisons
ainsi la procédure suivante:
Pour toute zone z ∈ Z :
Soit, toutes les BTS pouvant connecter z sont choisies. Dans ce cas en
posant µz > 0, λa sera non nul pour chaque BTS a appartenant à Az . La
première contrainte permet de voir que ces BTS contribueraient à diminuer
la valeur de la fonction objectif à cause de leur coefficient négatif. Donc en
posant µz = 0 cela implique que λa = 0, ∀a ∈ Az , et évite une diminution
de la fonction objectif
Soit, la zone peut être couverte à la fois par au moins une BTS choisie et
une non choisie.
La valeur de λa pour une BTS a non choisie n’influe pas sur l’augmentation
de la fonction objectif car son coefficient est nul.
Comme µz contribue à la maximisation, on lui alloue la plus grande valeur
possible qui est 1. La première contrainte donne µdzz ≤ λa , ∀a ∈ Az ce qui
implique que λa va prendre la plus grande valeur µdzz ≤ λa , ∀z ∈ Za
À chaque itération, à partir de la topologie, (y, u) fournie par le (PMR), on
définit les ensembles suivants:
- Â l’ensemble des BTS non choisies et Ẑ l’ensemble des zones qui peuvent
être couvertes par ces BTS.
 = {a ∈ A : y a = 0}, Ẑ = ∪a∈ Za .
- A1 l’ensemble des BTS choisies
A1 = {a ∈ A : y a = 1}.
- A l’ensemble des BTS activées couvrant des zones qui peuvent être cou-
vertes par au moins une BTS non activée.
A = {a ∈ A1 : Za ∩ Ẑ 6= ∅}.
- A ensemble des BTS choisies couvrant des zones qui ne peuvent pas être
couvertes par des BTS non choisies.

15
 A = {a ∈ A1 − A : Za ∩ Ẑ = ∅}.
- Z la réunion de zones qui peuvent être couvertes par une BTS appartenant
à A
Z = ∪a∈A Za
- Z la réunion des zones qui peuvent être couvertes par une BTS appartenant
à A.
Z = ∪a∈A Za .
Ainsi la solution (λa , µz ) va s’écrire :
 max 1
 (
si a ∈ A ∪ A, 1 si z ∈ Z ∪ Z,
λa = z∈Za dz µz =

0 sinon. 0 sinon.

La coupe qu’on doit ajouter au problème maı̂tre s’écrit de la manière suiv-

ante: X qa X
− ya + 1 ≤ 0.
d za
a∈A∪A z∈Z∩Z

1 1
où dza = max , ∀a ∈ A.
z∈Za dz
Soit (λ, µ), avec λ = (λa )a∈A et µ = (µz )z∈Z le vecteur des multiplica-
teurs engendré par la procédure ci-dessus.
Dans ce qui suit on décrit l’algorithme de résolution utilisant la procédure
précédente.
Algorithme de résolution 2:
Étape 0:
Résoudre une version relaxée du problème maı̂tre ne contenant pas de coupe
de réalisabilité. Soit (y 0 , u0 ) une solution optimale. Aller à l’étape 2.
Étape 1:
À la k − ième itération résoudre le problème maı̂tre relaxé Soit (y k , uk ) une
solution optimale.
Étape 2:
Déterminer (λk , µk ) par les formules.
 max 1
 (
si a ∈ A ∪ Â, 1 si z ∈ Ẑ ∪ Z,
λka = z∈Za dz µkz =

0 sinon. 0 sinon.

Vérifier
Xsi les contraintes
X relaxées du sous-problème sont satisfaites :
k k
− Si µz − λa qa ya > 0, alors le sous-problème est non réalisable on
z∈Z a∈A

16
 X X
ajoute une coupe de la forme µkz − λka qa ya ≤ 0.
z∈Z a∈A
Retour à l’étape
X 1. X
− Sinon, si µkz − λka qa ya ≤ 0, alors le sous-problème (SP(yk ,uk ) )
z∈Z a∈A
est réalisable et sa solution sera trouvée en résolvant le problème auxiliaire.
Soit (x) la solution optimale.
L’algorithme s’arrête: (x, y k , uk ) est une solution optimale pour le problème
original.
Dans la section suivante, nous présentons les résultats numériques de
quelques instances du modèle de synthèse de la conception topologique de
réseaux de télécommunication cellulaires. Les solutions sont fournies par
Cplex, [5], par la méthode de décomposition de Benders qui utilise le sous-
problème auxiliaire pour la génération des coupes (qu’on note Benders1) et
par l’algorithme de Benders utilisant la coupe de réalisabilité définie dans
la section 3.2 (qu’on note Benders2). Le programme utilisé pour générer les
paramètres de manière aléatoire, faute d’avoir des données réelles, fournit
des instances avec un nombre élevé de variables. Une instance, par exemple,
ayant 200 zones à couvrir par environ 75 BTS, peut compter plus de 10 000
variables.

4 Résultats numériques
L’objectif des tests numériques est d’évaluer la qualité de la solution fournie
par les deux algorithmes basés sur la méthode de décomposition de Ben-
ders. Un ordinateur Pentium 4, 1.5Ghz et 261 Mo de RAM a été utilisé
pour exécuter les algorithmes. Le modèle global simplifié est codé en C++
et résolu par Cplex 8.0 Callable Library. L’algorithme de Benders est aussi
implémenté en C++ de deux manières : une première qui fait appel, à
chaque itération, à Cplex pour résoudre le problème maı̂tre et le sous-
problème auxiliaire. Les multiplicateurs optimaux du sous-problème auxili-
aire permettent de générer les coupes de réalisabilité. On le note Benders1.
L’autre manière consiste à résoudre le problème maı̂tre par Cplex et d’utiliser
la procédure de génération de coupe décrite à la sous-section 3.2 et notée
Benders2. Le temps limite de résolution, noté T L, a été fixé de manière ar-
bitraire à 10 heures. Les instances utilisées pour les tests numériques ne sont
pas extraites de données réelles d’un réseau de télécommunication mais sont
créées par un programme qui génère aléatoirement les différents paramètres
du modèle. En sortie on va avoir des matrices en 0 − 1 représentant les con-
traintes de voisinage, une matrice des coûts des arcs des différents niveaux,

17
une matrice des coûts des équipements et une matrice des capacités de ces
équipements. Par exemple si on considère AZ = (AZaz ), a ∈ A, z ∈ Z la
matrice de voisinage entre les BTS et les zones. AZaz = 1 si la BTS a
peut couvrir la zone z. Les données communes de toutes les instances sont
définies comme suit. La demande de trafic pour une zone (cellule) donnée
est comprise entre 2 et 4 sans tenir compte des périodes de faible ou de forte
demande. La capacité de chaque BTS, en quantité de trafic qu’elle peut
écouler est fixée entre 10 et 12. Le nombre de BTS qu’un BSC peut con-
necter est compris entre 20 et 25. Le nombre maximal de BSC qu’un MSC
peut connecter est compris entre 10 et 12 ou entre 20 et 22. Ces données
sont arbitrairement fixées. Le nombre de zones qu’une BTS peut couvrir est
implicitement limité par la définition de la capacité de la BTS. Les instances
sont divisées en trois groupes. Les instances de type I sont constituées de
réseaux de petite taille qui ont moins de 10 000 variables, le type II de
taille moyenne, jusqu’à 30 000 variables, et le type III représente les réseaux
de grande taille, qui ont plus de 30 000 variables. Les tableaux 1, 2 et 3
résument les résultats obtenus en résolvant les instances de type I, II et III
par Cplex et par l’algorithme de Benders1. Les tableaux 4 et 5 comparent
les algorithmes de Benders1 et Benders2. La colonne Z représente le nombre
de zones (cellules) à couvrir. Au niveau de chaque tableau, les ensembles A,
B et M représentent respectivement le nombre de sites disponibles prédéfinis
pour l’installation des BTS, BSC et MSC. Le nombre d’itérations de Ben-
ders1 est en général égal à 3, raison pour laquelle on n’a pas eu besoin
de mettre une colonne pour cela. La colonne N représente le numéro du
problème pour des instances ayant les mêmes paramètres. Sur les instances
de grande taille Cplex ne parvient pas, la plus part du temps à fournir la
valeur optimale. De ce fait la dernière colonne du tableau 3 mesure la marge
existante entre les deux valeurs trouvées par Cplex et par l’algorithme de
Benders1. La marge est définie par gap = (ZBenders1 − Zcplex )/ZBenders1
où ZBenders1 est la valeur fournie par la procédure Benders1 et ZCplex celle
donnée par Cplex. L’unité de temps sur tous les tableaux est la seconde.
Dans ce qui suit, nous allons d’abord faire une comparaison entre les résultats
de Cplex et ceux de Benders1, ensuite une comparaison des deux algorithmes
de Benders.
Instances de type I
Le tableau 1 montre que pour les problèmes de petite taille les temps de
résolution de Cplex et de Benders1 sont sensiblement les mêmes. Les deux
méthodes fournissent la solution optimale. Ce faible temps de résolution de
Cplex est naturellement dû à la taille des instances.

18
 Méthodes
Paramètres Cplex Benders1
Z A B M N Temps (s) Temps(s)
9 6 3 2 v1 0.03 0.02
12 6 3 2 4 0.03 0.02
25 6 3 2 v1 0.03 0.02
49 17 2 1 1 0.07 0.04
50 23 3 2 v1 0.03 0.02
69 25 2 1 2 5 0.09
84 27 2 1 3 0.25 0.44
90 32 3 2 v1 0.03 0.02
96 35 2 1 1 91 0.09

Table 1: Instances de type I: comparaison Benders1-Cplex

Instances de type II

Méthodes
Paramètres Cplex Benders1
Z A B M N Temps (s) Temps (s)
105 40 3 2 1 TL 1.5
150 55 3 2 1 TL 3
180 60 5 2 2 5011 3
186 68 3 2 2 1120 2
204 75 3 2 1 34 2
234 95 3 2 1 TL 539
234 95 3 2 4 TL 4
234 95 3 2 5 TL 3
256 115 7 2 1 TL 550

Table 2: Instances de type II: comparaison Benders1-Cplex

Sur les instances de taille moyenne, compilées dans le tableau 2, Cplex de

la même manière que Benders1 fournit la solution optimale. Mais on con-
state qu’avec le temps de résolution qui atteint la limite, Cplex commence
à peiner. La colonne 7 montre le faible temps de résolution de Benders1.
Instances de type III
Les résultats des instances de types III sont compilés dans le tableau 3.
Cplex rencontre d’énormes difficultés avec ces instances. Souvent le temps

19
limite de résolution ne lui suffit pas pour atteindre la solution optimale. Il
fournit simplement une borne supérieure.
Quant à l’agorithme Benders1, il parvient à fournir la solution opti-
male avec un temps acceptable comparé à Cplex. Le gap non nul, défini par
(ZBenders1 − Zcplex )/Zbenders1 , montre que Cplex atteint la limite de temps
sans fournir la solution optimale. Le sous-problème auxiliaire est résolu en
général en peu de temps, mais c’est le problème maı̂tre qui prend beaucoup
de temps avec l’augmentation de la taille des instances. On a remarqué

Méthodes
Paramètres Cplex Benders1
Z A B M N Temps (s) Temps (s) gap
300 150 5 2 1 TL 9977 0.0008
350 180 5 2 2 TL TL 0
350 180 5 2 4 TL 15013 0.0015
400 375 3 2 1 TL 333 0.0014
500 450 3 2 2 TL 329 0.0013

Table 3: Instances de type III: comparaison Benders1-Cplex

aussi que le temps de résolution de Benders1 ne dépend pas uniquement

de la taille du problème mais aussi de la forme de la matrice de voisinage
BTS-Zones et des paramètres de l’instance pour les problèmes de grande
taille. C’est pourquoi on note souvent des instances ayant le même nombre
d’équipements qui sont résolues avec un écart considérable de temps. Les
tableaux 4 et 5 présentent une comparaison entre les résultats obtenus par
les deux algorithmes de Benders. Le gap, représenté par la dernière, colonne
est défini par gap = (ZBenders2 − ZBenders1 )/ZBenders2 .
Sur les instances de petite taille les deux méthodes fournissent la solution
optimale en très peu de temps. Sur les instances de taille moyenne les deux
algorithmes arrivent à fournir la valeur optimale. Mais le temps de résolution
de Benders1 plus élevé que celui Benders2. Avec les instances de grande
taille, on remarque que la méthode Benders2 arrive à obtenir la solution op-
timale avec un temps de résolution inférieur à celui Benders1. Plus la taille
de l’instance augmente plus Benders1 rencontre des difficultés à résoudre
l’instance. Le tableau 5 montre que la méthode de Benders1 s’arrête souvent
avec la limite de temps sans fournir la solution optimale alors que Benders2
trouve la solution optimale en un temps acceptable. Donc l’algorithme de
Benders2 a permis non seulement d’améliorer la qualité de la solution mais
de réduire le temps de résolution sur les instances de grande taille. Le gap

20
 Méthodes
Paramètres Benders1 Benders2
Z A B M N Temps (s) Temps (s) gap
204 75 3 2 1 3 1 0
234 95 3 2 1 539 769 0
234 95 3 2 3 22 4 0
256 115 7 2 1 TL 37 -0.0030
256 115 7 2 4 TL 22 -0.0028
300 150 5 2 1 9977 602 0
300 150 5 2 3 8705 66 0

Table 4: Instances de type II: comparaison Benders1-Benders2

négatif sur les tableaux 4 et 5 s’explique par le fait que Benders1 ne four-
nit pas la valeur optimale de l’instance. Quand il est nul alors les deux
algorithmes fournissent la valeur optimale. Dans des tests préliminaires qui

Méthodes
Paramètres Benders1 Benders2
Z A B M N Temps (s) Temps (s) gap
300 150 5 2 6 TL 143 -0.0008
350 180 5 2 2 TL TL -0,0018
350 180 5 2 4 15013 47 -0.0015
450 280 5 2 1 TL 19 -0.0006
450 280 5 2 2 TL 18 -0.001
450 280 5 2 2 TL 255 -0.001

Table 5: Instances de type III: comparaison Benders1-Benders2

ne figurent pas sur les tableaux précédents, sur certaines instances Cplex
s’arrête bien avant la limite de temps pour une mémoire insuffisante, “out
of memory”.

5 Conclusion
Dans ce travail, nous avons construit un modèle mathématique pour le
problème de la conception topologique des réseaux de télécommunication
cellulaires. Ce modèle regroupe deux types de problèmes: un problème

21
de localisation et de connexion des équipements (variables binaires) et un
problème de couverture des zones (variables continues). La structure du
modèle nous a amené naturellement à utiliser la décomposition de Ben-
ders qui s’est avérée trés efficace et particulièrement lorsque la coupe de
réalisabilité est générée de manière constructive (algorithme2) à partir de
la structure particulière du réseau. Cet algorithme a permis d’améliorer la
qualité de la solution et de réduire le temps de résolution sur les instances
de grande taille là où Cplex ne parvient pas à fournir une solution optimale.
Il reste bien entendu à tester la méthode sur des instances réelles (par souci
de confidentialité les opérateurs ne fournissent pas leurs données réelles).
Une façon alternative d’aborder le problème est de le modéliser comme un
problème de flot et d’utiliser la relaxation lagrangienne pour le résoudre.

22
References
[1] A. Benchakroun, J. A. Ferland et V. Gascon, Benders decomposition for
Network design problems with underlying tree structure, Investigacion
Operativa, p.165-180, 1998.

[2] A. Benchakroun, Un modèle de planification des réseaux de distribution

d’énergie électrique, Thèse de Doctorat. Université de Montréal 1988.

[3] A.M. Geoffrion, Generalized Benders decomposition, Journal of opti-

mization theory and applications, vol.10 No 4,p. 237-260, 1972.

[4] [Link], Minimisation of the impact of subscriber mobility on the re-

sources of a GSM network, [Link] et al.(Eds): TOOLS 2000,
LNCS 1786, p. 132-144, 2000.

[5] CPLEX optimization, inc. CPLEX: using the CPLEX callable library,
version 4.0 CPLEX copyright 1989-1995 CPLEX optimization.

[6] C.D. Randazzo, H.P.L. Luna et P. Mahey, Benders decomposition for

local access network design with two technologies, Discrete Mathematics
and theoretical Computer Science 4, p.235-246, 2001.

[7] F. Chauvet, E. J-Lagreze, L. Pajou, B. Rottembourg, Planification

de réseaux mobiles: problèmatique, modélisation, méthodes rapport de
recherche.

[8] F.F. Mazzini et G.R. Mateus, A mixed-integer programming model for

the cellular telecommunication network design, p.65-76, 2001.

[9] F.F. Mazzini, G.R. Mateus, [Link]. Smith Lagrangean based methods for
solving large-scale cellular network design,wireless networks, p.659-672,
2003.

[10] J.F. Benders, Partitioning procedures for solving mixed integer variables
programming problems, Numerische Methematik, 4: p.238-252,1962.

[11] M. Shahbaz, topological network design of mobile communication net-

works, AEU [Link]. Commun. 50 N 4, p.240-246, 1996.

[12] P., Mahey, A., Benchakroun, F., Boyer,Capacity and flow assignment of
data networks by generalized Benders decomposition, Journal of Global
Optimization, vol.20, 2, p.173-193, 2001.

23
[13] R. Mathar and T. Nielsen, Optimum positioning of base stations for
cellular networks, Wireless Networks 6, p.421-428, 2000.

[14] X. Lagrange, [Link], [Link] Réseaux GSM, Hermés Science

Publications 5eme édition revue et augmentée, 2000.

24