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 cellulaires 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 équipements 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ésolution 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 frequency assignment are presented in the literature. With this approach each problem is treated separately. In this paper, we propose an integrated 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 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 connecter à 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 appelé 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 composée de 3 niveaux:

- le sous-système radio BSS (Base Station Sub-system) qui assure les transmissions 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 Controller) qui contrôlent un ensemble de BTS et permettent une première concentration 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 Subsystem) 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].

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 localisation 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’ensemble constitué par la BTS et les antennes fixées sur cette BTS. La configuration 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 A_{z} ensemble des antennes a qui peuvent couvrir tout ou une partie de la zone z. Z_{a} ensemble des zones z qui peuvent être couvertes partiellement ou totalement par l’antenne a. B_{a} ensemble des BSC b qui peuvent être connectées à l’antenne a. B_{z} ensemble des zones qui peuvent être connectées par une antenne pouvant être connectée à la BSC b. A_{b} ensemble des antennes a qui peuvent être reliées au BSC b. B_{m} ensemble des BSC b qui peuvent être connectées au MSC m. M_{b} ensemble des MSC m qui peuvent être connectées au BSC b. Paramètres

• E_{a}, E_{b}, E_{m} sont respectivement les coûts d’installation des BTS, des BSC et des MSC.

• d_{z} quantité de trafic demandée au niveau de la zone z.

• r_{z} revenu par unité de demande pour une zone z

• l_{ab} coût d’une liaison entre un BSC et une BTS.

• l_{bm} coût d’une liaison entre un MSC et un BSC.

• Q_{m} est le nombre maximal de BSC que pourrait connecter un MSC.

• Q_{b} est le nombre maximal de BTS que pourrait connecter un BSC.

• q_{a} la capacité de la BTS a de gérer le trafic issu des zones qu’elle couvre. Variables

• x_{za} est une variable donnant la part du trafic dans la zone z capté par une BTS a.

• variables de connexion: u_{ab} = 1 si la BTS a est connectée au BSC b et 0 sinon; u_{bm} = 1 si le BSC b est connectée au MSC m et 0 sinon.

• variables d’installation d’équipements y_{a} = 1 si le site a est choisi pour installer une BTS et 0 sinon; y_{b} = 1 si le site b est choisi pour installer un BSC et 0 sinon; y_{m} = 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:

R^{T} x = ∑_{a∈A} ∑_{z∈Z_{a}} r_{z}d_{z}x_{za}

x étant le vecteur des variables de couverture des différentes zones, x = (x_{za})_{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 des équipements:

C_{1}^{T} y = ∑_{a∈A} E_{a}y_{a} + ∑_{b∈B} E_{b}y_{b} + ∑_{m∈M} E_{m}y_{m}

y étant le vecteur des variables d’installation d’équipements, y = (y_{a}, y_{b}, y_{m})_{a∈A,b∈B,m∈M} C_{1} vecteur des coûts d’installation des équipements.

- coût de connexion des équipements du réseau:

C_{2}^{T} u = ∑_{b∈B} ∑_{a∈A_{b}} l_{ab}u_{ab} + ∑_{m∈M} ∑_{b∈B_{m}} l_{bm}u_{bm}

u étant le vecteur des variables d’installation d’arcs du réseau, u = (u_{ab}, u_{bm})_{a∈A,b∈B,m∈M} C_{2} 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) = C_{1}^{T} y + C_{2}^{T} 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 couverture des zones, l’installation des équipements et la topologie du réseau.

Contraintes de couverture des zones

• Chaque zone z doit être totalement couverte:

∑_{a∈A_{z}} x_{za} = 1, ∀z ∈ Z.  (1)

Dans ce cas, la demande est totalement satisfaite et R^{T} x = C^{te}.

• La part de la demande de trafic couverte par une antenne ne doit pas dépasser sa capacité:

∑_{z∈Z_{a}} d_{z}x_{za} − q_{a}y_{a} ≤ 0, ∀ a ∈ A.  (2)

Cette contrainte sert aussi de couplage entre les variables y_{a} et x_{za}. Une BTS non activée ne peut pas couvrir de zone.

• La part x_{za} de la demande de la zone z couverte par l’antenne a représente un pourcentage donc est au plus égale à 1:

x_{za} ≤ 1, ∀z ∈ Z, ∀a ∈ A_{z}.  (3)

Contraintes d’installation d’équipements

• Chaque zone z est gérée par au moins une BTS:

∑_{a∈A_{z}} y_{a} ≥ 1, ∀z ∈ Z.  (4)

• y_{a} = 0 signifie la non installation de l’équipement a et entraîne la non existence de lien avec un BSC. Si y_{a} = 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:

y_{a} − ∑_{b∈B_{a}} u_{ab} = 0, ∀a ∈ A  (5)

• Si une BTS a est choisie, il existe au moins un BSC b choisi qui puisse la connecter:

y_{a} − ∑_{b∈B_{a}} y_{b} ≤ 0, ∀a ∈ A.  (6)

• y_{b} = 0 signifie la non installation d’un BSC b et implique la non existence de lien avec un MSC. Si y_{b} = 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:

y_{b} − ∑_{m∈M_{b}} u_{bm} = 0, ∀b ∈ B.  (7)

• Il existe au moins un BSC b ∈ B_{z} qui connecte au moins une antenne a ∈ A_{z}:

∑_{b∈B_{z}} y_{b} ≥ 1, ∀z ∈ Z.  (8)

• Il existe au moins un MSC m qui connecte au moins un BSC b ∈ B_{z}:

∑_{m∈M_{z}} y_{m} ≥ 1, ∀z ∈ Z.  (9)

• Si un BSC b est choisi alors il existe au moins un MSC m choisi qui puisse le connecter:

y_{b} − ∑_{m∈M_{b}} y_{m} ≤ 0, ∀b ∈ B.  (10)

Contraintes de topologie du réseau

• Pour chaque zone z, il existe au moins un arc reliant un élément de A_{z} et un élément de B_{z} pour que celle-ci soit couverte:

∑_{b∈B_{z}} ∑_{a∈A_{z}} u_{ab} ≥ 1, ∀z ∈ Z.  (11)

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

∑_{b∈B_{a}} u_{ab} ≤ 1, ∀a ∈ A.  (12)

• Le nombre de liaisons entre un BSC b et les BTS qui sont dans son voisinage ne peut être supérieur à sa capacité:

∑_{a∈A_{b}} u_{ab} − Q_{b}y_{b} ≤ 0, ∀b ∈ B.  (13)

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

y_{b} − ∑_{a∈A_{b}} u_{ab} ≤ 0, ∀b ∈ B.  (14)

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

y_{m} − ∑_{b∈B_{m}} u_{bm} ≤ 0, ∀m ∈ M.  (15)

• Le nombre de liaisons entre un MSC m et les BSC qui sont dans son voisinage ne peut être supérieur à sa capacité:

∑_{b∈B_{m}} u_{bm} − Q_{m}y_{m} ≤ 0, ∀m ∈ M.  (16)

• 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:

u_{ab} − ∑_{m∈M_{b}} u_{bm} ≤ 0, ∀a ∈ A, ∀b ∈ B.  (17)

• 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:

u_{bm} − ∑_{a∈A_{b}} u_{ab} ≤ 0, ∀b ∈ B, ∀m ∈ M.  (18)

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

∑_{m∈M_{b}} u_{bm} ≤ 1, ∀b ∈ B.  (19)

• L’existence d’un arc implique l’installation des équipements qui forment ses extrêmités:

u_{ab} − y_{a}y_{b} ≤ 0, ∀a ∈ A, ∀b ∈ B,  (20)
u_{bm} − y_{b}y_{m} ≤ 0, ∀b ∈ B, ∀m ∈ M.  (21)

Contraintes sur les variables

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

x_{za} ≥ 0, ∀z ∈ Z, ∀a ∈ A_{z}.  (22)

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

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

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

u_{ab}, u_{bm} ∈ {0, 1}, ∀a ∈ A, ∀m ∈ M, ∀b ∈ B.  (24)

Remarque 1 Généralement la contrainte ∑_{a∈A_{z}} x_{za} = 1, ∀z ∈ Z est remplacée par les

contraintes suivantes:

\begin{aligned}∑_{a∈A_{z}} x_{za} & ≤ & 1, & ∀z ∈ Z (R.1), \\ ∑_{a∈A_{z}} x_{za} & ≥ & 0.98, & ∀z ∈ Z (R.2). \end{aligned}

(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:

(P′) \{ \begin{matrix}min & C_{1}^{T} y + C_{2}^{T} u − R^{T} x \\ sujet à: \\ & (1) à (24). \end{matrix}

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 y_{a} ou y_{b} est nulle alors u_{ab} = 0.

∗ si u_{ab} = 1, alors les variables y_{a} et y_{b} sont à la fois égales à 1. Or u_{ab} ne peut prendre que les valeurs 0 ou 1; la contrainte (20) est donc équivalente à:

\{ \begin{matrix}u_{ab} ≤ y_{a}, ∀ a ∈ A, ∀ b ∈ B, \\ u_{ab} ≤ y_{b}, ∀ a ∈ A, ∀ b ∈ B. \end{matrix}

De même, la contrainte (21) s’écrit:

\{ \begin{matrix}u_{bm} ≤ y_{b}, ∀b ∈ B, ∀m ∈ M, \\ u_{bm} ≤ y_{m}, ∀b ∈ B, ∀m ∈ M. \end{matrix}

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

En utilisant la contrainte d’égalité suivante ∑_{a∈A_{z}} x_{za} = 1, ∀ z ∈ Z,

le terme de la fonction objectif représentant le revenu engendré par la couverture des zones peut se simplifier de la manière suivante:

∑_{a∈A} ∑_{z∈Z}(−r_{z})d_{z}x_{za} = ∑_{z∈Z}(−r_{z})d_{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′), que l’on considère est le suivant:

(P) \{ \begin{matrix}min & C(y, u) = C_{1}^{T} y + C_{2}^{T} u \\ sujet à: \\ & (1) à (10), (15), (16), (17), (18), (22), (23), (24). \end{matrix}

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 variables y ou u. Le modèle peut s’écrire sous-forme matricielle de la manière suivante:

(P) \{ \begin{matrix}min & C(y, u) = C_{1}^{T} y + C_{2}^{T} u \\ sujet à: \\ & A(x) − g(y, u) ≤ 0; \\ & H(y, u) ≤ 0; \\ & (y, u) ∈ Y × U, x ∈ X. \end{matrix}

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 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 MR), 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 processus de résolution est un processus itératif au cours duquel le problème maître relaxé (P MR) va progressivement être enrichi d’informations provenant 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.

Posons : Y = {(y, u) ∈ Y × U : H(y, u) ≤ 0 }, le problème (P) peut alors s’écrire:

(P) \{ \begin{matrix}min & C_{1}^{T} y + C_{2}^{T} u \\ sujet à: \\ & A^{T} x ≤ g(y, u), \\ & x ∈ X, (y, u) ∈ Y. \end{matrix}

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

(PP) { min_{(y,u)∈Y} {CT 1 y + CT 2 u + inf_{x∈X}{0 : A^{T} x ≤ g(y, u)}}.

Posons :

v(y, u) = inf_{x∈X}{0 : A^{T} x ≤ g(y, u)} = max_{ϕ≥0}{ϕ^{T} g(y, u) : Aϕ ≤ 0}

ϕ étant le vecteur des variables duales.

V  = {(y, u) : A^{T} x − g(y, u) ≤ 0, pour au moins un x ∈ X}.

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

min_{(y,u)∈Y∩V} C_{1}^{T} y + C_{2}^{T} u.

(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 C_{1}^{T} y + C_{2}^{T} 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

(SP_{(\overline{y},\overline{u})}) \{ \begin{matrix}min & 0 \\ sujet à: \\ & ∑_{z∈Z_{a}} d_{z}x_{za} ≤ q_{a}\overline{y}_{a}, ∀a ∈ A, \\ & ∑_{a∈A_{z}} x_{za} = 1, ∀z ∈ Z, \\ & x ≥ 0. \end{matrix}

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 simplexe^{1} 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_{(\overline{y},\overline{u})}) est constant, ainsi donc toute solution réalisable est optimale. Pour voir si SP_{(\overline{y},\overline{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_{(\overline{y},\overline{u})}) de la phase I du sous-problème, pour (y, u) = (\overline{y}, \overline{u}) fixé s’écrit:

(SPA_{(\overline{y},\overline{u})}) \{ \begin{matrix}min & e^{T} t \\ sujet à: \\ & ∑_{z∈Z_{a}} d_{z}x_{za} + x_{a} + t_{a}^{1} = q_{a}\overline{y}_{a}, ∀ a ∈ A, & λ_{a} \\ & ∑_{a∈A_{z}} x_{za} + t_{z}^{2} = 1, ∀ z ∈ Z , & μ_{z} \\ & x, x_{a}, t ≥ 0. \end{matrix}

Où e = (1, 1, ..., 1), t^{1} = (t_{a}^{1}), t^{2} = (t_{z}^{2}), t = (t^{1}, t^{2}) et x = (x_{za}) Soit (\overline{x}, \overline{x}_{e}, \overline{t}) la solution optimale. Si e^{T} \overline{t} = 0, alors \overline{x} en est une solution optimale. Si par contre e^{T} \overline{t} > 0, alors SP_{(\overline{y},\overline{u})} est non-réalisable et les variables duales de SP A_{(\overline{y},\overline{u})} seront utilisées pour formuler la coupe de réalisabilité. Le problème dual du problème auxiliaire SP A_{(\overline{y},\overline{u})} s’écrit:

(DSPA_{(\overline{y},\overline{u})}) \{ \begin{matrix}max & ∑_{a∈A} −q_{a}\overline{y}_{a}λ_{a} + ∑_{z∈Z} μ_{z} \\ sujet à: \\ & −d_{z}λ_{a} + μ_{z} ≤ 0, ∀a ∈ A; ∀z ∈ Z, \\ & λ_{a} ≤ 1,  ∀a ∈ A, \\ & μ_{z} ≤ 1,  ∀z ∈ Z, \\ & λ_{a} ≥ 0,  ∀a ∈ A. \end{matrix}

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

Le sous-problème (SP_{(\overline{y},\overline{u})}) est réalisable, si et seulement si, ∑_{z∈Z} μ_{z} − ∑_{a∈A} λ_{a}q_{a}\overline{y}_{a} ≤ 0, d’après la théorie de la dualité.

Donc si {(λ^{i}, μ^{i}), i = 1, ..., p} est l’ensemble des rayons extrêmes de (DSP A_{(\overline{y},\overline{u})}), alors (y, u) ∈ V, si et seulement si

∑_{a∈A} −q_{a}\overline{y}_{a}λ_{a}^{i} + ∑_{z∈Z} μ_{z}^{i} ≤ 0, ∀i = 1, ..., p.

Le problème maître qui est équivalent au problème (P P) va s’écrire alors :

(PM) \{ \begin{matrix}min & C_{1}^{T} y + C_{2}^{T} u \\ sujet à: \\ & ∑_{a∈A} −q_{a}\overline{y}_{a}λ_{a}^{i} + ∑_{z∈Z} μ_{z}^{i} ≤ 0, ∀i = 1, ..., p (CR), \\ & (y, u) ∈ Y. \end{matrix}

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 MR), 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 (\overline{y}_{0}, \overline{u}_{0}) une solution optimale. Aller à l’étape 2. Étape 1: À la k − ième itération résoudre le problème maître relaxé P MR. Soit (\overline{y}_{k}, \overline{u}_{k}) une solution optimale. Étape 2: Résoudre le sous-problème auxiliare. Soit (\overline{x}_{k}, \overline{t}_{k}) 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 MR).

- Sinon, \overline{x}_{k} est réalisable et optimale pour le sous-problème (SP_{(\overline{y}_{k},\overline{u}_{k})}). L’algorithme s’arrête: (\overline{x}_{k}, \overline{y}_{k}, \overline{u}_{k}) 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.

3.2 Algorithme 2

Pour trouver une solution réalisable du problème dual (DSP A_{(\overline{y},\overline{u})}), on va diviser l’ensemble A en sous-ensembles qui facilitent le traitement de la première contrainte. Considérons une topologie (\overline{y}, \overline{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, −q_{a}\overline{y}_{a}, est nul si \overline{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 \overline{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 à A_{z}. 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 ∈ A_{z}, 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 \frac{μ_{z}}{d_{z}} ≤ λ_{a}, ∀a ∈ A_{z} ce qui implique que λ_{a} va prendre la plus grande valeur \frac{μ_{z}}{d_{z}} ≤ λ_{a}, ∀z ∈ Z_{a} À chaque itération, à partir de la topologie, (\overline{y}, \overline{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 : \overline{y}_{a} = 0\}, Ẑ = ∪_{a∈Â}Z_{a}.

- A_{1} l’ensemble des BTS choisies

A_{1} = \{a ∈ A : \overline{y}_{a} = 1\}.

- \underline{A} l’ensemble des BTS activées couvrant des zones qui peuvent être couvertes par au moins une BTS non activée.

\underline{A} = \{a ∈ A_{1} : Z_{a} ∩ Ẑ ≠ ∅\}.

- \overline{A} ensemble des BTS choisies couvrant des zones qui ne peuvent pas être couvertes par des BTS non choisies.

\overline{A} = \{a ∈ A_{1} − \overline{A} : Z_{a} ∩ Ẑ = ∅\}.

- \overline{Z} la réunion de zones qui peuvent être couvertes par une BTS appartenant à \overline{A}

\overline{Z} = ∪_{a∈\overline{A}}Z_{a}

- \underline{Z} la réunion des zones qui peuvent être couvertes par une BTS appartenant à \underline{A}.

\underline{Z} = ∪_{a∈\underline{A}}Z_{a}.

Ainsi la solution (\overline{λ}_{a}, \overline{μ}_{z}) va s’écrire :

\overline{λ}_{a} = \{ \begin{matrix}max_{z∈Z_{a}} \frac{1}{d_{z}} & si a ∈ \underline{A} ∪ \overline{A}, \\ 0 & sinon. \end{matrix} \overline{μ}_{z} = \{ \begin{matrix}1 & si z ∈ \overline{Z} ∪ \underline{Z}, \\ 0 & sinon. \end{matrix}

La coupe qu’on doit ajouter au problème maître s’écrit de la manière suivante:

− ∑_{a∈\underline{A}∪\overline{A}} \frac{q_{a}}{d_{z_{a}}} y_{a} + ∑_{z∈\overline{Z}∩\underline{Z}} 1 ≤ 0.

où \frac{1}{d_{za}} = max_{z∈Z_{a}} \frac{1}{d_{z}} , ∀a ∈ A.

Soit (\overline{λ}, \overline{μ}), avec \overline{λ} = (\overline{λ}_{a})_{a∈A} et \overline{μ} = (\overline{μ}_{z})_{z∈Z} le vecteur des multiplicateurs 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 (\overline{y}_{0}, \overline{u}_{0}) une solution optimale. Aller à l’étape 2. Étape 1: À la k − ième itération résoudre le problème maître relaxé Soit (\overline{y}_{k}, \overline{u}_{k}) une solution optimale. Étape 2: Déterminer (λ^{k}, μ^{k}) par les formules.

λ_{a}^{k} = \{ \begin{matrix}max_{z∈Z_{a}} \frac{1}{d_{z}} & si a ∈ \underline{A} ∪ Â, \\ 0 & sinon. \end{matrix} μ_{z}^{k} = \{ \begin{matrix}1 & si z ∈ Ẑ ∪ \underline{Z}, \\ 0 & sinon. \end{matrix}

Vérifier si les contraintes relaxées du sous-problème sont satisfaites : − Si ∑_{z∈Z} μ_{z}^{k} − ∑_{a∈A} λ_{a}^{k}q_{a}y_{a} > 0, alors le sous-problème est non réalisable on ajoute une coupe de la forme ∑_{z∈Z} μ_{z}^{k} − ∑_{a∈A} λ_{a}^{k}q_{a}y_{a} ≤ 0.

Retour à l’étape 1.

− Sinon, si ∑_{z∈Z} μ_{z}^{k} − ∑_{a∈A} λ_{a}^{k}q_{a}y_{a} ≤ 0, alors le sous-problème (SP_{(\overline{y}_{k},\overline{u}_{k})})

est réalisable et sa solution sera trouvée en résolvant le problème auxiliaire. Soit (\overline{x}) la solution optimale. L’algorithme s’arrête: (\overline{x}, \overline{y}_{k}, \overline{u}_{k}) 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 sousproblè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 Benders. 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 sousproblème auxiliaire. Les multiplicateurs optimaux du sous-problème auxiliaire 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 arbitraire à 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 contraintes de voisinage, une matrice des coûts des arcs des différents niveaux, une matrice des coûts des équipements et une matrice des capacités de ces équipements. Par exemple si on considère AZ = (AZ_{az}), a ∈ A, z ∈ Z la matrice de voisinage entre les BTS et les zones. AZ_{az} = 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 connecter 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 Benders1 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 = (Z_{Benders1} − Z_{cplex})/Z_{Benders1} où Z_{Benders1} est la valeur fournie par la procédure Benders1 et Z_{Cplex} 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.

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 constate 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 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 optimale avec un temps acceptable comparé à Cplex. Le gap non nul, défini par (Z_{Benders1} − Z_{cplex})/Z_{benders1}, 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 = (Z_{Benders2} − Z_{Benders1})/Z_{Benders2}. 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 optimale 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

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 fournit 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 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 Benders 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.

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 optimization theory and applications, vol.10 No 4,p. 237-260, 1972.

[4] C.Bauer, Minimisation of the impact of subscriber mobility on the resources of a GSM network, B.R.Haverkort 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, J.Mcg. 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 networks, AEU Int.J.Electron. 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.

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

[14] X. Lagrange, P.Goldlewski, S.Tabbane Réseaux GSM, Hermés Science Publications 5eme édition revue et augmentée, 2000.