Une approche basée sur la programmation par contraintes

pp. 1-21 1

1/21 ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003

Résumé

Cet article propose une approche basée sur la programmation par contraintes pourrésoudre le problème bien connu dans les réseaux de communications personnelles qui estcelui de l’affectation de cellules à des commutateurs. Il s’agit de déterminer une affectationdes différentes cellules du réseau à des commutateurs (dont les localisations sont fixes etconnues), qui minimiserait une fonction de coûts composée des coûts de relève entre toutesles cellules d’une part, et des coûts de liaison entre cellules et commutateurs d’autre part.De plus, toute solution devrait respecter la contrainte de capacité de chaque commutateur.Considérant qu’il s’agit là d’un problème NP-difficile, l’idée de base pour le résoudreconsiste à concevoir des techniques de filtrage efficaces pour réduire l’espace de recherchesur lequel des algorithmes de contrôle seront appliqués dans le but d’aboutir à des solutionsproches de l’optimum. Les résultats obtenus montrent qu’une bonne utilisation descontraintes donne des solutions exactes pour des réseaux de taille moyenne, et des solutionsassez voisines de celles obtenues par la recherche avec tabous, qui se trouve être lameilleure heuristique à date fournissant de bonnes solutions sur des réseaux de grandetaille.

Mots clés:

A CONSTRAINT PROGRAMMING APPROACH TO ASSIGN CELLS TOSWITCHES IN PERSONNAL COMMUNICATION NETWORKS

Abstract

This paper discusses the problem of assigning cells to switches in mobile networks. Itcan be summed up as finding an optimal assignment of cells to switches in order to minimizea cost function composed of the cost of handoff between cells and the cost of cabling bet-ween cells and switches. We propose here an algorithm based on constraint programmingfor this problem. The choice of this method is motivated by its active use of constraints in thesearch for solutions, which in turn leads to the reduction of the search space and the diffi-culty of the problem. We introduce a new Constraint Optimization Problem model for assi-gning cells to switches, a definition of a lower bound on the cost of each cell and a

Une approche basée sur la programmationpar contraintes pour affecter des cellules

à des commutateurs dans les réseaux cellulaires pour mobiles

Grâce AMOUSSOU*, Matthieu ANDRÉ*, Gilles PESANT*, Samuel PIERRE**

* Département de génie informatique, École Polytechnique de Montréal, C.P. 6079, succ. Centre-ville, Montréal,Québec, Canada H3C 3A7, courriel : [email protected].

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 1

development of search strategies, leading to an efficient way of finding the best solutions.Results showed that our algorithm leads to an optimum solution for medium size networksand can find good solutions for large size networks.

Key words:

Sommaire

I. INTRODUCTION

Dans les réseaux de communications personnelles, le territoire couvert ou la zone de cou-verturedesservie est généralement découpé en de petites surfaces géographiquement limitéeset communément appelées cellules. Celles-ci sont représentées par des hexagones dont lerayon varie de quelques centaines de mètres à quelques kilomètres au maximum. À l’intérieurde chacune de ces cellules se trouve un sous-système radioconstituant une station de baseouBTS(Base Station Transceiver) qui s’occupe des transmissions radio sur la cellule. Intégrés àla station de base, des canaux de signalisation vont permettre à l’abonné de communiqueravec la BTS et vice versa. Les stations de base sont à leur tour reliées à des contrôleurs de sta-tion de base ou BSC(Base Station Controller). C’est ce sous-système qui sert donc d’interfaceradio entre chaque terminal mobile et le réseau lui-même. Le sous-système réseau est à sontour constitué de commutateurs ou MSC (Mobile service Switching Center) installés à l’inté-rieur de quelques-unes des cellules choisies de manière stratégique. Dans ce contexte, le rôled’un commutateur est d’assurer l’interconnexion des différentes cellules du réseau mobileentre elles et aussi avec les autres réseaux de télécommunications avec ou sans fil.

Les terminaux mobiles sont en général utilisés en déplacement. Pour éviter des interfé-rences, deux cellules contiguës n’utilisent pas les mêmes canaux radio. La transmission doitdonc changer de canal chaque fois que le mobile passe d’une cellule à une autre. Ce proces-sus de transfert automatique de la communication d’une station de base à une autre est appelérelève(handoverou handoff). Concrètement, le système cellulaire contrôle en permanence lapuissance du signal entre le mobile et la station de base la plus proche. Dès que la puissancetombe sous un niveau donné, le système attribue automatiquement une nouvelle cellule aumobile. Ce transfert de cellules peut entraîner un changement de commutateur, auquel casdes opérations de mise à jour sont réalisées et on parle de relève complexe, sinon on a unerelève simple ne faisant intervenir qu’un même et unique commutateur.

Le choix d’une cellule se fait en tenant compte du niveau du signal. Généralement, ondéfinit un seuil en dessus duquel on considère que la puissance reçue est assez importantepour être prise en compte par une cellule. Les informations échangées par les usagers sont àleur tour gérées par le commutateur qui dessert cette cellule. Celle-ci est donc desservie par

2 G. AMOUSSOU– UNE APPROCHE BASÉE SUR LA PROGRAMMATION PAR CONTRAINTES

ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003 2/21

I. IntroductionII. Formulation classique

III. Adaptation à la programmation parcontraintes

IV. Analyse des résultatsV. ConclusionBibliographie (17 réf.)

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 2

un seul commutateur à la fois. Lorsque différentes cellules (situées à proximité) reçoiventtoutes des niveaux du signal supérieur au seuil, seule celle ayant le niveau le plus élevé assu-rera la prise en charge de l’usager. De ce fait, la communication sera relayée par le commu-tateur auquel ladite cellule est affectée. En considérant la Figure 1, plusieurs cas peuvent seprésenter lors du déplacement du mobile d’une cellule C1, reliée à un commutateur MSCi,vers une autre cellule Cj ayant un plus fort niveau de signal :

• Le mobile est pris en charge par la cellule C2. Dans ce cas, les deux cellules C1 et C2sont contrôlées par un même commutateur MSC2. Donc, la relève est simple et nenécessite pas des opérations de mise à jour de la base de données de l’usager. Seul lecommutateur MSC2 intervient dans cette opération.

• Le mobile est pris en charge par la cellule C0, qui est contrôlée par un commutateurdifférent MSC3. Dans ce cas, plusieurs informations sont échangées entre les deux com-mutateurs pour mettre à jour la base de données du réseau (localisation de l’usager,échange de protocoles, type d’appels, etc.). De plus, il peut arriver que certaines opé-rations, comme la facturation, continuent d’être effectuées par le commutateur MSC2.On aura ainsi une connexion de l’usager au commutateur MSC3, puis au commutateurMSC2 et enfin au réseau. On parle de relève complexe dont le coût est très élevé com-parativement à une relève simple.

La relève complexe constitue une opération sollicitant beaucoup de ressources de la partdu réseau et dont il convient de réduire autant que possible le coût. De ce fait, il serait sou-haitable d’établir une fréquence des relèves entre les différentes cellules, afin de pouvoirregrouper celles échangeant le plus fréquemment, sous le contrôle d’un même commutateur.

G. AMOUSSOU– UNE APPROCHE BASÉE SUR LA PROGRAMMATION PAR CONTRAINTES 3

3/21 ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003

FIG. 1. — Relève dans un réseau cellulaire.

Handoff in a cellular network.

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 3

Ces différentes considérations sont à la base du problème d’affectation de cellules à des com-mutateurs qui peut être énoncé de la manière suivante:

Étant donné un ensemble de cellules et de commutateurs de capacités finies, trouver uneaffectation des cellules à ces commutateurs qui minimise le coût total constitué du coût deliaison entre cellules et commutateurs d’une part, et du coût de relèves entre les cellulesd’autre part.

La résolution de ce problème doit donc prendre en compte les facteurs suivants: la topo-logie du réseau, la capacité des commutateurs et le volume des appels échangés par unité detemps dans chacune des cellules.

Plusieurs méthodes, pour la plupart des heuristiques, ont été proposées pour sa résolu-tion : Merchant et Sengupta [11, 12], recherche avec tabous [8, 13], algorithme génétique[5 – 7]. Ceux-ci ont résolu le problème suivant un schéma d’affectation simple, qui supposel’unicité de l’affectation dans la configuration du réseau. Une autre approche moins étudiéeest celle de la domiciliation double qui permet qu’une cellule puisse être affectée à deuxcommutateurs différents, auxquels elle sera reliée de manière alternative suivant les momentsde la journée. Dans l’un ou l’autre des cas, le problème à résoudre demeure très complexe etnécessite une approche heuristique.

Notre objectif dans cet article est d’appliquer les méthodes de la programmation parcontraintes (PC) au problème d’affectation unique. Pour ce faire, nous introduirons une nou-velle modélisation du problème. Celle-ci utilise des variables à domaine fini, ainsi que lescontraintes qu’elles doivent satisfaire. Par la suite, une propagation dynamique descontraintes du problème sur les différentes variables utilisées contribue à réduire leursdomaines respectifs et, par le fait même, la taille de l’espace de recherche à explorer. Deplus, diverses stratégies de recherche seront exploitées pour réduire le temps de calcul, sur-tout pour des problèmes de grande taille. L’utilisation de ces stratégies permettra de se rendrecompte très tôt des échecs et de limiter la recherche à des parties de l’arbre pouvant débou-cher sur de bonnes solutions.

La suite de l’article est organisée comme suit. Après cette première section d’introduc-tion, la section 2 présente une formulation classique du problème d’affectation, ainsi qu’uneanalyse de quelques unes des méthodes qui lui ont été appliquées. La section 3 décrit l’adap-tation du problème à la programmation par contraintes. Enfin, la section 4 présente une ana-lyse des résultats.

II. FORMULATION CLASSIQUE

Le problème d’affectation de cellules à des commutateurs peut être modélisé suivant plu-sieurs approches. Merchant et Sengupta [11, 12] l’ont formulé comme un problème de pro-grammation en nombres entiers: minimiser une fonction de coût, suivant un schémad’affectation tout en respectant les contraintes sur la capacité de chaque commutateur. Dansce qui suit, nous présenterons le premier modèle (basé sur le coût) réalisé suivant un schémasimple d’affectation.


ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003 4/21

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 4

II.1. Modélisation suivant la domiciliation simple

On suppose que le réseau dispose de n cellules et de m commutateurs dont les emplace-ments sont fixes et connus. À chaque commutateur doit être affecté un ensemble de cellulessuivant le volume des appels qu’il peut gérer. Pour chaque paire de cellules i et j (i ≠ j), ondéfinit les coûts suivants:

Hij – Coût par unité de temps d’une relève simple entre les cellules i et j ;H’ ij – Coût par unité de temps d’une relève complexe entre les cellules i et j ;Cik – Coût d’amortissement provenant du câblage entre la cellule i et son commutateur k.Soient le volume d’appels par unité de temps reçu par la cellulei (1 ≤ i ≤ n) et Mk la

capacité du commutateur k (1≤ i ≤ m).

L’objectif est de trouver une affectation des cellules aux commutateurs qui minimise lasomme totale des coûts de liaison et de relève et respecte la contrainte de capacité limitée dechaqueMSC. Pour décrire le problème, on introduit les n × mvariables binaires suivantes :

(1) Xik = 5On s’intéresse alors à exprimer le problème à l’aide de ces variables de manière à satis-

faire les contraintes qui y sont posées. Tout d’abord, au niveau des cellules, chacune d’ellesdoit être assignée à un et un seul commutateur. Cette condition peut être représentée par larelation:

(2) ^m

k= 1 Xik = 1 pour i = 1, …, n

D’autre part, si Cik désigne le coût d’amortissement de la liaison entre la cellule i et lecommutateurk, on peut exprimer le coût total de liaison entre toutes les cellules et les com-mutateurs auxquels elles sont reliées par la relation:

(3) ^n

i = 1 ^m

k= 1 Cik Xik

Pour représenter le coût total induit par les opérations de relève simple et complexe, onintroduit de plus les variables complémentaires suivantes:

(4) Zijk = Xik . Xjk pour i, j = 1, …, n et k =1, …, m

Ces variables permettent en effet de formuler mathématiquement le fait que deux cellulesi et j soient affectées à un même commutateur k par la propriété suivante:

(5) Zijk = 5Soit maintenant :

(6) Yij = ^m

k= 1 Zijk pour i, j = 1, …, n et i ≠ j

1 si i et j sont connectées au commutateur k0 sinon

1 si la cellule est reliée au commutateur k0 sinon


5/21 ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 5

Yij prend la valeur 1 si les cellules i et j sont connectées à un même commutateur et est égaleà 0 si elles sont reliées à des commutateurs différents.

Le coût des relèves simples et complexes par unité de temps s’exprime par :

(7) fhs = ^n

i = 1 ^n

j = 1 Hij . Yij

(8) fhc = ^n

i = 1 ^n

j = 1 H′ ij . (1 – Yij)

La fonction objectif globale composée de chacun des coûts prédéfinis s’écrit donc :

(9) f = ^n

i = 1 ^m

k= 1 Cik Xik + ^

n

i = 1 ^n

j = 1 Hij . Yij + ^

n

i = 1 ^n

j = 1 H′ ij . (1 – Yij)

Il s’agit alors de minimiser la fonction f sous les contraintes suivantes :

^n

i = 1 Xik = 1 pour i = 1,…, n

Xik = 0 ou 1 pour i = 1,…, n et k = 1, …, m

Zijk = Xik Xjk pour i, j = 1,…, n et k = 1, …, m

Yij = ^m

k= 1 Zijk pour i, j = 1,…, n et i ≠ j

De plus, on a la contrainte imposée par la capacité de chaque commutateur et suivantlaquelle le volume total d’appels engendré par toutes les cellules liées au commutateur k nedoit pas dépasser la capacité maximum de ce commutateur. Celle-ci se traduit par :

(10) ^n

i = 1 λi Xik ≤ Mk pour k= 1, 2, …, m

Pour simplifier la fonction f de la relation (9), on peut négliger le coût des relèves simplesdevant celui des relèves complexes qui utilisent plus de ressources. De ce fait, si on pose :

hij = H ′ ij – Hij ≈ H′ ij

qui représente le coût réduit par unité de temps d’une relève complexe entre les cellules i etj, f peut s’écrire comme suit :

f = ^n

i = 1 ^m

k= 1 Cik Xik + ^

n

i = 1 ^n

j = 1, j ≠ i

Hij Yij + ^n

i = 1 ^n

j = 1 (hij + Hij) (1 – Yij)

qui est équivalent à :

f = ^n

i = 1 ^m

k= 1 Cik Xik + ^

n

i = 1 ^n

j = 1, j ≠ i

Hij + ^n

i = 1 ^n

j = 1, j ≠ i

hij . (1 – Yij)


ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003 6/21

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 6

Puisque :

^n

i = 1 ^n

j = 1, j ≠ i

Hij

est une constante, le problème initial peut s’écrire sous la forme suivante :Minimiser

(11) f = ^n

i = 1 ^m

k= 1 Cik Xik + ^

n

i = 1 ^n

j = 1, j ≠ i

– H′ ij Yij

sous les contraintes :

Xik = 5^n

i = 1 Xik = 1 pour i = 1,…, n

Zijk = Xik Xjk pour i, j = 1,…, n et k = 1, …, m

Yij = ^m

k= 1 Zijk pour i, j = 1,…, n et i ≠ j

Yik = 5

^n

i = 1 λi Xik ≤ Mk pour k= 1, 2, …, m

Pour ramener le problème à un problème de programmation en nombres entiers, Merchant et Sengupta ont proposé de remplacer la contrainte non linéaire (4) par unensemble de contraintes équivalentes :

Zijk ≤ Xik

Zijk ≤ Xjk

Zijk ≥ Xik +Xjk – 1

Zijk ≥ 0

Tel que formulé précédemment, le problème d’affectation de cellules aux commutateurspeut être ramené à plusieurs types de problème largement étudiés en recherche opération-nelle, tels le problème de transport ou de localisation de concentrateurs et celui de partition-nement de graphes. Leur résolution par une méthode énumérative conduit généralement àune croissance exponentielle du temps d’exécution. En conséquence, on recherche une solu-tion plutôt proche de l’optimum, en développant des heuristiques ou méta-heuristiques derésolution pour ces types de problèmes reconnus NP-difficiles.

1 si i et j sont reliées au commutateur k0 sinon

1 si la cellule est reliée au commutateur k0 sinon


7/21 ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 7

II.2. Aperçu de quelques méthodes de résolution

Plusieurs heuristiques ont été développées pour la résolution de ce problème d’affecta-tion. Dans ce qui suit, nous passerons en revue les plus récents travaux effectués dans cecontexte et dont l’application au problème d’affectation fournit de bonnes solutions.

Méta-heuristique de recherche taboue

La méthode de recherche taboue constitue une amélioration de l’algorithme de descentequi permet d’éviter le piège du minimum local. Elle fut introduite en optimisation combina-toire par Glover [3, 4] pour la résolution de problèmes difficiles. C’est une méthode qui partd’une solution initiale supposée locale et sur laquelle différents mouvements sont effectuéspour arriver à une meilleure solution. Ainsi, pour y arriver, l’algorithme accepte de temps entemps des solutions qui n’améliorent pas toujours la solution courante. Le retour vers dessolutions déjà visitées est interdit en conservant une liste taboue Tde longueur k comportantles k dernières solutions jusque là visitées. Le choix de la prochaine solution est alors effec-tué sur un ensemble des solutions voisines ne comportant aucun des éléments de cette liste.Lorsque le nombre k est atteint, chaque nouvelle solution qui devient taboue remplace laplus ancienne dans la liste. L’exploration de l’espace de recherche peut être représenté parun graphe G = (X, A), où X désigne l’ensemble des solutions et A l’ensemble des arcs (x, m(x)), m(x)étant la solution obtenue en appliquant le mouvement m à x. Le graphe ainsiobtenu est symétrique car, pour chaque arc (x, m(x)), il existe un arc (m(x), x)obtenu enappliquant le mouvement inverse m-1 à m. La recherche taboue part donc d’une solution ini-tiale x0 qui est un nœud du graphe G, et cherchera dans G un chemin x0, x1, …, xp où xi = m(xi–1) avec i = 1, …, p. Les arcs (xi, xi–1) du chemin sont choisis en résolvant le pro-blème d’optimisation :

f (xi +1) = min f (xi)

Pour adapter la méthode au problème d’affectation, Houéto et Pierre [8] partent d’unesolution initiale obtenue à partir de la plus petite distance euclidienne. Une composante demémoire à court terme permet d’explorer le voisinage de cette solution tout en évitant lescycles. L’espace de recherche est choisi libre des contraintes de capacité sur les commuta-teurs mais respecte la contrainte d’affectation unique des cellules. Chaque nouvelle solutionobtenue est évaluée suivant deux critères. Le premier est lié au coût calculé à partir de lafonction objectif, le deuxième prend en compte une sanction introduite pour le non respect dela contrainte de capacité. On essaie alors de choisir, à chaque étape, la meilleure solutionsuivant ces deux critères. Trois structures de mémoires permettent d’éviter des cycles autourd’un optimum local et de raffiner la recherche : mémoire à court terme, mémoire à moyentermes, et mémoire à long terme. Ces structures sont détaillées dans [8]. Néanmoins, larecherche taboue quoiqu’utilisant certains mécanismes complexes pour aboutir aux solu-tions, n’exploite pas la notion de contraintes inhérente aux problèmes NP-difficiles.

Le recuit simulé

Le recuit simulé est une technique d’optimisation qui permet d’échapper au piège desminima locaux en autorisant, avec une certaine probabilité, une augmentation de la fonction


ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003 8/21

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 8

de coût [9]. Il s’inspire de la thermodynamique, où certains systèmes physiques atteignentleur état d’équilibre (minimum d’énergie) malgré un grand nombre d’états métastables pos-sibles. Au cours de cette opération, l’énergie peut localement augmenter avec une probabilitéproportionnelle à la température du système, suivant la loi de Boltzmann. Cette températurediminue au cours du temps pour amener à l’état final. Ainsi, dans le recuit simulé, une dimi-nution de la fonction sera toujours acceptée, alors qu’une augmentation de la fonction seraacceptée avec une probabilité qui dépend d’un paramètre correspondant à la température. Uncertain nombre de paramètres critiques doit être déterminé, tels que la solution initiale, latempérature initiale, le critère d’arrêt, etc.

Le recuit simulé a été appliqué au problème d’affectation. L’algorithme qui en résulte estle suivant :

Étape 1 : Créer la topologie initiale (au hasard, sans tenir compte de la contrainte decapacité).

Étape 2 : Choisir une solution voisine.Étape 3 : Si la solution est meilleure ou si la probabilité d’acceptation est satisfaite,

prendre cette solution comme nouvelle solution courante.Étape 4 : Diminuer la température du système en la multipliant par le facteur de recuit A.Étape 5 : Si le critère d’arrêt n’est pas satisfait, aller à l’étape 2, sinon fin de l’algorithme.

La solution trouvée est de très bonne qualité, mais pour certaines configurations l’algo-rithme de recuit simulé se laisse piéger par les minima locaux.

III. ADAPTATION À LA PROGRAMMATION PAR CONTRAINTES

L’introduction de la programmation par contraintes comme méthode de résolutionremonte aux années soixante avec le système Sketchpaddéveloppé par Sutherland (1963),considéré de nos jours comme étant l’un des pionniers dans ce domaine. Par la suite, cesméthodes ont servi de point de départ pour développer plusieurs langages de programmationbasés sur les contraintes et qui se sont montrés d’une certaine efficacité pour la maîtrise deproblèmes complexes comme celui de planification de tâches, de transport, d’allocation deressources, etc. C’est actuellement un domaine de recherche d’un grand intérêt. Dans ce quisuit, nous présenterons une brève description des concepts essentiels à sa compréhension,suivie d’une description des différentes étapes de son adaptation au problème d’affectationde cellules.

III.1.Concepts de base de la méthode de PC

Comme son nom l’indique, la programmation par contraintes est une technique qui estbasée sur les contraintes et les algorithmes de recherche de solution satisfaisant cescontraintes [10]. Elle part d’une modélisation où les variables ainsi que leurs domaines sontdéfinis de manière à limiter le nombre de combinaisons à considérer. Les contraintes sont


9/21 ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 9

par la suite appliquées sur les variables de modélisation et leur respect est testé suivant cer-tains algorithmes propres à la PC. Certaines heuristiques de contrôle de recherche sont finale-ment utilisées pour trouver une affectation des valeurs à toutes les variables du problème quisatisfasse les contraintes.

L’algorithme de retour-arrière est un algorithme complet de résolution de problème CSP

mais dont le temps d’exécution est exponentiel. L’exploration du domaine est réalisée entrois étapes : 1) Choix de la variable; 2) Choix de la valeur à donner à cette variable; 3) Si lasolution partielle viole une contrainte, alors défaire le dernier choix sinon aller à 1). Sitoutes les contraintes sont respectées, alors le problème admet une solution. La taille del’arbre de recherche explorée dépend du choix de la variable xi à instancier à chaque étapede l’algorithme.

Les cohérences de nœuds et d’arcs permettent de limiter le domaine des variables unairesou binaires à l’ensemble des valeurs respectant les contraintes du problème. Dans ce proces-sus, à chaque fois que le domaine d’une variable change, on révise le domaine de toute autrevariable qui lui est reliée par une contrainte. Il existe plusieurs versions de l’algorithme decohérence d’arcs parmi lesquels le AC-4 qui maintient une structure de liste pour chaquepaire <variable, valeur>, permettant ainsi une révision moins aveugle des variables affec-tées. Il existe des algorithmes de filtrage spécifiques à contraintes dites globales.

En considérant les problèmes d’optimisation, on désire trouver des solutions à un but quioptimisent une fonction de coût. La procédure d’optimisation par séparation etévaluationprogressive (“branch & bound”) s’intègre bien dans le modèle de résolution de la PC et peutêtre facilement exploitée dans la résolution des problèmes d’optimisation. Le principe decette méthode est de calculer une solution s,parmi l’ensemble des solutions réalisables pos-sibles T du problème et de continuer la recherche en ajoutant une contrainte supplémentairecout(t) < cout(s) (t∈ T) sur toute nouvelle solution. Lorsque la recherche se termine enéchec, le dernier coût total calculé donne le coût optimal (global) du problème. La poursuitede la recherche s’effectue en faisant un retour-arrière tout en conservant la structure del’arbre de dérivation courant ou par itération en développant un nouvel arbre de recherchetenant compte de la contrainte supplémentaire sur la borne supérieure du coût.

III.2.Formulation du problème d’affectation en PC

On considère donc un problème comportant n cellules et mcommutateurs dont les empla-cements sont connus. On définit les données suivantes :

• volDappels[i] : volume d’appels par unité de temps reçu par la cellule i ;• coutCab[i][k] : coût d’amortissement du câblage entre la cellule i et le commutateur k;• coutRel[i][ j] : coût par unité de temps d’une relève entre les cellules i et j ;• capacité[k] : capacité d’un commutateur en volume d’appels par unité de temps.

L’objectif est de trouver une affectation des cellules aux commutateurs qui respecte lacapacité limitée de chaque commutateur et qui minimise la somme des coûts de liaison et derelève. Pour cela, on doit tenir compte d’un certain nombre de contraintes. En effet, chaquecellule doit être affectée à un commutateur, parmi les m possibles. On utilise donc lesvariables suivantes :


ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003 10/21

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 10

(12) Commi ∈ {0, …, m – 1} pour i = 0…n – 1

Ces variables peuvent prendre une valeur appartenant au domaine {0, …, m– 1}, on parlealors de variables à domaine fini. Le domaine de ces n variables est donc, au début de larecherche, l’ensemble des commutateurs. Le problème d’affectation est résolu quand on afixé la valeur de ces variables en respectant les contraintes du problème. On remarque quel’utilisation de ces variables garantit l’unicité de l’affectation.

On introduit aussi la variable de coût couti pour i = 0…n – 1, qui représente le coût de lacellule, soit la somme du coût de câblage de la cellule i à son commutateur et du coût derelève de la cellule i. On remarque de plus que la relève, si elle existe, a toujours lieu entreune cellule et ses cellules voisines, ou adjacentes. Or, ces cellules sont au maximum aunombre de 6, à cause de leurs formes hexagonales. D’un point de vue mathématique, les cel-lules voisines j d’une cellule i peuvent aussi être définies comme étant les cellules avec les-quelles le coût de relève coutRel[ i][ j] est non nul. On décide alors de stocker cetteinformation pour chaque cellule dans la donnée voisins[i]. Avec cette donnée, pour calculerle coût de relève d’une cellule, on examine donc au plus 6. On a donc :

(13) couti = cout Cab[i]Commi] + ^ coutRel[i][ j] pour i = 0…n – 1j∈ voisins [i]/Commj ≠ Commi

La fonction de coût à minimiser est donc :

(14) ^n

i = 1 couti

La contrainte de capacité des commutateurs s’exprime comme suit :

(15) ^ volDappels[i] ≤capacité[k] pour k = 0…m – 1i/Commj = k

III.3. Représentation des contraintes du problème

La contrainte sur l’affectation unique étant déjà respectée par l’essence même desvariables modélisant le problème, nous n’avons défini que deux nouvelles classes decontraintes : CapCoherence( )et BorneInf( ). La classe de contraintes CapCoherence( )sert àexprimer la contrainte de capacité de l’équation (15). Elle utilise pour cela un algorithmeefficace qui permet notamment de mieux filtrer lors de la propagation, et qui est présenté à laFigure 2.

Avec cet algorithme, on retient la capacité résiduelle de chaque commutateur à chaqueétape de la recherche. Ensuite, quand on décide d’affecter une cellule à un commutateur k onvérifie que cette affectation ne viole pas la contrainte de capacité. On prévient ensuite lesfutures violations de la contrainte possibles en enlevant des domaines des variables toutes lesaffectations qui violeraient la contrainte de capacité.


11/21 ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 11

La seconde classe de contraintes BorneInf( )est utilisée pour rendre la recherche plusefficace. Elle n’est donc pas une contrainte intrinsèque du problème. L’idée de cettecontrainte est d’obtenir une borne inférieure des coûts de toutes les cellules, afin d’obtenirune borne inférieure du coût de la solution que l’on construit, et donc de savoir si cette solu-tion partielle pourrait améliorer la meilleure solution. Si ce n’est pas le cas, on arrêtera deconstruire cette solution partielle, et l’on coupera ainsi une partie de l’arbre de recherche,avec les gains de temps intéressants qui en résultent. Pour ce faire, à chaque fois que ledomaine d’une variable Commi est modifié, on répercute cette modification sur les bornesinférieures des coûts des cellules qui sont susceptibles d’être modifiées : la cellule concernéeet ses six cellules voisines. Le calcul de chaque borne inférieure d’une cellule est effectuétrès simplement à partir de l’ensemble des affectations possibles de cette cellule et de sesvoisines.

Cette contrainte introduit un filtrage supplémentaire aussi basé sur les bornes inférieuresde coûts. Appelons M le coût de la meilleure solution trouvée par l’algorithme (égal à l’infinisi aucune solution n’a été trouvée), et Ci la borne inférieure du coût de la cellule i. Lasomme de tous les Ci est S, c’est-à-dire la borne inférieure sur le coût de la solution qu’onpourrait obtenir à partir de la solution partielle courante. Ainsi, si S ≥ M, on sait que notresolution partielle ne pourra pas améliorer la meilleure solution. On doit donc s’assurer que S< M pour être certain que l’on fait une recherche dans la bonne direction. Partant de cettecondition, on peut améliorer le filtrage pour une cellule i, dont le domaine est constitué deplusieurs commutateurs. Soit S′ la nouvelle valeur de Set C′ i la nouvelle valeur de Ci si onaffecte la cellule i au commutateur k. On a :


ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003 12/21

Pour k allant de 0 à m FaireCapRes[k] = capacite[k]

Fin PourTant que le programme principal s’exécute Faire

Quand la variable Commi est fixée à k FaireCapa = CapRes[k] - volDappels[i]Si (Capa < 0) Faire

Echec annuler les modificationsSinon Faire

Pour toutes les cellules j non affectées FaireSi (Capa - volDappels[j] < 0) Faire

Retirer k du domaine de CommjFin Si

Fin PourCapaRes[k] = Capa

Fin SiFin Quand

Fin Tant que

FIG. 2.– Algorithme de CapCoherence( ).

CapCoherence algorithm.

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 12

S′ = S – Ci + C′ i

et coutCab[i][k] ≤ C′ i.On en déduit donc que S′ ≥ S – Ci + coutCab[i][k]. Or, on doit avoir S′< M, donc on doit

avoir :S– Ci + coutCab[i][k] < M

qui s’écrit aussicoutCab[i][k] < M – S + Ci.

Appelons coutCab[i][k] la borne inférieure du coût de relève de la cellule i si on l’affecteau commutateur k. On a donc

C′ i = coutCab[i][k] + coutRel[i][k].

On en déduit donc, comme précédemment, la condition suivante :

coutCab[i][k] + coutRel[i][k] < M – S+ Ci

Ainsi, toute valeur k du domaine de la cellule i qui ne satisfait pas ces deux conditionspeut être filtrée. L’algorithme complet de la contrainte est présenté à la Figure 3.


13/21 ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003

FIG. 3. – Algorithme de BorneInf( )

BorneInf algorithm.

Si le domaine de Commi est modifié FairePour toutes les cellules j voisines de i Faire

min = IntMaxPour chaque commutateur k de Faire

coutCell = coutCab[j][k]Si S – Cj + coutCell >= M Faire

Retirer la valeur k du domaine de la cellule jSinon Faire

Pour toutes les cellules c voisines de j FaireSi k n’est pas dans le domaine de Commc Faire

coutCell = coutCell + coutRel[j][c]Fin Si

Fin PourSi S – Cj + coutCell >= M Faire

Retirer la valeur k du domaine de la cellule jSinon

min = minimum(min, coutCell)Fin Si

Fin SiFin PourCj = min

Fin PourFin Si

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 13

Une fois les contraintes testées et certaines valeurs retirées du domaine, on procède àl’énumération. Les stratégies de choix de valeurs et de variables dans l’algorithme derecherche deviennent alors très importantes. Si on considère une représentation en arbre detoutes les solutions potentielles, ces stratégies permettent de contrôler l’ordre suivant lequelon examine les différentes branches de cet arbre. Ceci a pour but de diriger la recherche versdes branches de l’arbre plus susceptibles de donner de meilleures solutions, et d’éliminertrès tôt celles ne pouvant conduire à de meilleurs résultats.

III.4.Algorithme de recherche de solutions

Dans ce type de modélisation, les contraintes contribuent de manière efficace à laréduction de l’espace de recherche. Cependant, afin d’améliorer la performance de l’algo-rithme de séparation et d’évaluation progressive (“Branch&Bound”) utilisé, la stratégie dechoix des variables et des valeurs doit être examinée et peut s’avérer efficace suivant letype de problème.

En effet, dans le processus de recherche de solutions, les variables sont choisies successi-vement et leurs valeurs fixées. Lorsqu’une solution est trouvée, elle sert de borne supérieure àtoute nouvelle solution. Suivant le choix des variables, on peut aboutir à un processus nonréalisable qui sera suivi d’un retour-arrière pour essayer d’autres valeurs ou d’autres variablesen cas d’échec. Le choix des variables à fixer peut donc permettre de réduire l’espace derecherche surtout dans la résolution de problèmes combinatoires où l’on désire non une solu-tion réalisable mais la meilleure solution réalisable possible. Généralement, on utilise deuxprocédures de choix des variables: une sélection dynamique ou une sélection statique.

Dans le problème d’affectation de cellules, comme dans tout problème d’optimisation, ilapparaît plus raisonnable de commencer par les variables les plus contraintes, c’est-à-direcelles ayant le plus petit domaine et apparaissant dans plusieurs contraintes. Par exemplepour plusieurs cellules, on commencera par celles qui ne peuvent être affectées qu’à unnombre réduit de commutateurs. Trouver une affectation à ces cellules en premier lieu peutamener à se rendre compte très vite des échecs et réduire les temps d’exécution. C’est cequ’on appelle communément le principe de l’échec d’abord (First-Fail principle). Cepen-dant, la stratégie à adopter dépend du problème que l’on résout bien que suivant le mêmeprincipe de raisonnement.

Dans notre cas, nous avons choisi le moindre regret sur le coût de câblage. Cette stratégieconsiste à commencer par les variables ayant la plus grande valeur de différence entre le pre-mier plus petit coût et le second plus petit coût de câblage. De manière concrète, cela revientà affecter la cellulei au commutateur ayant le plus petit coût de câblage parmi tous les com-mutateurs auxquels la cellule i peut être affectée. Soit P le prix à payer en affectant la mêmecellule i à un autre commutateur ayant le second plus petit coût de câblage. On commencerapar les cellules pour lesquelles P est le plus grand car elles représentent les variables pourlesquelles on aura le plus grand regret, en les affectant à un commutateur plutôt qu’à unautre. De plus, dans les fichiers de données, on constate que la valeur du volume d’appelspeut varier d’un facteur dix entre deux cellules. Or, plus la cellule a un volume d’appelsimportant, plus il va être difficile de l’affecter à un commutateur à cause de la contrainte decapacité. De plus, si l’on commence par affecter une cellule avec un important volume d’ap-


ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003 14/21

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 14

pels à un commutateur, ce dernier va avoir une capacité résiduelle fortement réduite, etmoins de cellules vont pouvoir y être affectées. En conséquence, les domaines des variablesvont être réduits et l’on risque ainsi de pénaliser des cellules avec un regret important et unvolume d’appels faible. Il faut donc commencer par affecter les cellules avec un faiblevolume d’appels qui pénaliseront peu les autres cellules. Pour tenir compte de cette donnée,on pondère donc la valeur donnée par le calcul du regret de la cellule par le volume d’appelsde la cellule.

Une fois la variable choisie, on doit essayer différentes valeurs de son domaine à lui attri-buer. L’ordre de sélection des valeurs ne permet pas de réduire l’espace, mais permet de gui-der la recherche vers des solutions avec des coûts réduits. Pour cela, on définit qui est laborne inférieure du coût de la cellule i si on l’affecte au commutateur k. Cette valeur est biensûr variable et sera naturellement mise à jour par la contrainte BorneInf( ). Ainsi, chaque foisqu’une cellule est choisie, on commence par la relier au commutateur tel que le coût de lacellule résultant soit à priori minimal.

Ainsi, pour le choix des variables, on commence par celles ayant le plus de chanced’échouer lors de l’optimisation du problème; pour le choix des valeurs, on est plutôt inté-ressé à attribuer de bonnes valeurs, pouvant conduire à un coût proche de l’optimum.

Les principales étapes du programme sont :

Étape 1 : Lire tous les fichiers et données du problème et initialiser les différentesvariables;

Étape 2 : Poster toutes les contraintes utilisées dans l’algorithme;Étape 3 : Quand il y a changement du domaine, appliquer la contrainte BorneInf( );Étape 4 : Si la valeur d’une cellule est fixée, appliquer la contrainte CapCohérence( );Étape 5 : Générer les variables Commi suivant les différentes stratégies de recherche défi-

nies. Les variables sont choisies suivant le moindre regret Différentes valeurssont par la suite attribuées à ces variables suivant le plus petit coût pour la cel-lule. Ces étapes sont répétées tant que toutes les variables ne sont pas fixées.

Étape 6 : La fonction qui minimise le coût total est réalisée par l’appel à setObjMin(sum).Elle met en mémoire la dernière valeur de la variable de coût trouvée, ajouteune nouvelle contrainte sur la borne supérieure du coût total à chaque itération.Cette procédure est exécutée tant qu’il existe encore des solutions au problème.Lorsqu’il n’y en a plus, le solveur retient la dernière solution trouvée et fournitle résultat.

IV. ANALYSE DES RÉSULTATS

Dans le but de mesurer la performance de l’algorithme, nous l’avons soumis à une sériede tests. Différents cas ont été considérés avec des nombres variables de cellules et de com-mutateurs. Dans ce qui suit, nous démontrerons d’abord l’utilité de la classe de contraintesBorneInf( ). Nous présenterons ensuite les résultats obtenus à partir de la mise en œuvre denotre adaptation de l’algorithme de séparation et d’évaluation progressive. Enfin, nous feronsune comparaison de nos résultats avec ceux trouvés par d’autres approches heuristiquestelles la recherche taboue, l’algorithme génétique et le recuit simulé.


15/21 ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 15

IV.1. Environnement d’exécution des tests

Les données nécessaires ont été générées par un programme Matlab et extraites de [8][13]. Les cas tests générés supposent que le coût de liaison d’une cellule à un commutateurest proportionnel à la distance qui les sépare, avec un coefficient de proportionnalité égal àl’unité. Le taux d’appel γi d’une cellule i est déterminé suivant une loi gamma de moyenne etde variance égales à l’unité. Les temps de séjour des appels à l’intérieur des cellules sontdistribués selon une loi exponentielle de paramètre 1. Le taux de relève entre les cellules estévalué en tenant compte des cellules avoisinantes. Si par exemple une cellule possède k voi-sins, l’intervalle [0,1] est divisé en k+1 sous-intervalles en choisissant k nombres aléatoiresdistribués uniformément entre 0 et 1. Pour un appel qui prend fin à l’intérieur d’une cellule jdonnée, on peut avoir deux issues : soit l’appel est transféré à la ièmecellule voisine (i =1, …, k)avec une probabilité de relève rij égale à la longueur duièmeintervalle, soit l’appel est coupéavec une probabilité égale à la longueur du k+1èmeintervalle. Les cellules sont alors considé-rées comme des files d’attente M/M/1 formant un réseau de Jackson. Les taux d’arrivées α i

dans les cellules à l’équilibre sont obtenus en résolvant le système:

α i – ∑j α j rij = γi avec i = 1, …, n

On choisit comme volume d’appel λ i d’une cellule i, la longueur moyenne de sa filed’attente. Le taux de relève hij est défini par :

hij = λi. rij

La capacité des commutateurs est déterminée comme suit :

Capacité = (1+K/100)/m ∑i λi

où K est choisi uniformément entre 10 et 50, ce qui permet d’obtenir une capacité de commutateur supérieure de 10 à 50 % au volume d’appel des cellules et m représente lenombre de commutateurs.

On dispose de 6 séries de 15 jeux de données, avec 15 cellules et 2 commutateurs, 30 cel-lules et 3 commutateurs, 50 cellules et 4 commutateurs, 100 cellules et 5 commutateurs,150 cellules et 6 commutateurs, 200 cellules et 7 commutateurs. On couvre ainsi un grandnombre de configurations, des plus simples aux plus complexes. Le langage de programma-tion par contraintes utilisé est ILOG Solver (version 4.4). Les ordinateurs utilisés sont des SunMicrosystems Ultra 10 Model 440, stations de 64 bits, avec un processeur 440 MHz UltraS-PARC-III , et 1024 Mo de mémoire vive. Étant donné que les temps de calculs peuventatteindre plusieurs jours, dès que les configurations deviennent complexes, nous sommesparfois contraints à ne donner les résultats que pour des configurations simples.

IV.2. Effet de la contrainte BorneInf ( ) sur la recherche de solution

L’introduction de la contrainte BorneInf ( )a introduit un gain de performance importantpour notre algorithme. Cette contrainte implique bien sûr un effort de calcul supplémen-taire à l’algorithme, qui doit calculer cette borne inférieure à chaque fois que le domaine


ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003 16/21

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 16

d’une variable est modifié. Mais, cet effort est rentable, ce calcul de borne inférieure per-mettant de réduire la taille de l’arbre de recherche. Pour s’en convaincre, nous avonsregardé le nombre d’échecs auxquels doit faire face l’algorithme lors de la recherche del’optimum. En effet, ce nombre d’échecs traduit le nombre d’essais inutiles qu’a dû réaliserl’algorithme, essais conduisant évidemment à des pertes de temps. Cette observation estcomplétée par l’étude du temps total d’exécution de l’algorithme. Nous l’avons réalisé pourles 15 jeux de données de la configuration à 15 cellules et 2 commutateurs. Pour trouverl’optimum pour l’ensemble de ces 15 fichiers, il a fallu 0.14 seconde et 441 échecs à l’algo-rithme utilisant la contrainte. Sans la contrainte, le nombre total d’échecs passe à 368705 etle temps total à 109.79 secondes. Il est donc clair que cette contrainte améliore grandementles performances de l’algorithme.

IV.3. Recherche de l’optimum

La recherche de l’optimum est bien sûr utopique pour l’ensemble des configurations exis-tantes. Il est en effet clair que la programmation par contraintes, même si elle réduit énormé-ment la taille de l’arbre de recherche, doit toujours explorer un très grand nombre depossibilités pour trouver l’optimum, et se trouve donc limitée par la vitesse du processeur etle temps dont l’utilisateur dispose. Cependant, il est toujours intéressant de connaître l’opti-malité pour des problèmes de petite taille. Sa connaissance peut éventuellement amener desanalystes à dégager des propriétés intéressantes, et constitue également un critère définitifd’évaluation des heuristiques développées pour le problème.

Nos expériences ont permis de trouver l’optimum très rapidement pour des problèmes à30 cellules et 3 commutateurs. Il a en effet fallu 8 secondes à l’algorithme pour trouver l’op-timum de l’ensemble des 15 jeux de données. Pour 50 cellules et 4 commutateurs, le tempsde calcul a aussi été raisonnable, car il n’a fallu que 1 heure et 5 minutes pour réaliser lamême opération. Par contre, pour les problèmes de plus grande taille, plusieurs journées decalculs n’ont pas suffi.

Ce faisant, on a pu constater que l’algorithme a un très bon comportement en débutd’exécution, à savoir que la première solution trouvée possède un coût très proche de l’opti-mum (quand on le connaît). La Figure 4 présente l’écart moyen, pour l’ensemble des jeux dedonnées d’une configuration, par rapport à la meilleure solution connue du problème. Cettemeilleure solution a été obtenue soit par la programmation par contraintes, soit par une heu-ristique telle que la recherche taboue [8]. C’est donc un optimum prouvé pour 30 cellules et3 commutateurs, et 50 cellules et 4 commutateurs.

On constate que l’on se trouve en moyenne à 1.11 % de la meilleure solution connue.Cette première solution peut donc constituer une heuristique intéressante pour résoudre leproblème.

Une autre vision peut être de laisser l’algorithme tourner pendant un temps choisi parl’utilisateur, la solution obtenue constituera alors une autre heuristique pour le problème.On a ici choisi de laisser pour chaque fichier de données, un temps en secondes égal aunombre de cellules multiplié par le nombre de commutateurs. Les résultats obtenus parcette version limitée dans le temps sont, comme on peut le voir à la Figure 5, très intéres-sants, et démontre le bon comportement de notre algorithme qui converge très rapidement


17/21 ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 17

vers une bonne solution. Ces résultats se trouvent en moyenne à 0.25 % de la meilleuresolution.

IV.4. Comparaison avec d’autres méthodes heuristiques

Le problème d’affectation de cellules à des commutateurs a été résolu avec diversesméthodes heuristiques [1, 2, 8, 13, 17]. Nous avons donc confronté les solutions obtenues parnotre adaptation avec celles des autres heuristiques afin d’en dégager son efficacité. Étantdonné que notre algorithme requiert un temps d’exécution trop important pour les problèmesde grande taille, nous avons utilisé une version limitée dans le temps, comme précisé plushaut. Nous avons aussi soumis à la comparaison les résultats donnés par la 1e solution denotre algorithme.

À la Figure 5, on constate que la version limitée dans le temps de notre algorithme donnetoujours en moyenne les meilleurs résultats, et que la 1e solution trouvée par notre algorithmeest avantagée par les problèmes de grande taille. Si la comparaison se fait sur les tempsd’exécution, la palme revient alors à la 1e solution trouvée par notre algorithme qui est tou-jours obtenue en une fraction de seconde, suivie de près par la recherche taboue qui est trèsrapide et s’exécute en quelques secondes. Le recuit simulé et la PC limitée dans le tempsnécessitent des temps d’exécution nettement plus importants, atteignant plusieurs minutespour les problèmes de grande taille. Il ne faut cependant pas oublier que l’importance du


ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003 18/21

FIG. 4. – Distance moyenne à la meilleure solution de la 1re solution.

Average distance of the first solution to the best solution.

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 18

temps de calcul est ici moindre, car on résout un problème de conception préalable à l’instal-lation d’un réseau. On imagine donc que le concepteur peut être prêt à attendre quelquesheures de calcul si cela lui permet d’économiser des sommes d’argent importantes.

V. CONCLUSION

Dans cet article, nous avons développé et mis en œuvre une adaptation de la programma-tion par contraintes au problème d’affectation de cellules à des commutateurs dans lesréseaux de communications personnelles. Ce problème qui consiste essentiellement àminimiser une fonction de coût composée de coûts de liaisons et de relèves, tout en respec-tant des contraintes de capacité des commutateurs. Considérer toutes les combinaisons pos-sibles pour en dégager la meilleure conduit très vite à une explosion combinatoire et ne peutêtre effectué en un temps polynomial. Ainsi, pour un nombre de cellules supérieur à 15, lesméthodes heuristiques jusque là développées ne fournissent pas de solutions exactes à ceproblème.

Avec les récentes techniques développées en programmation par contraintes, il est pos-sible d’utiliser de manière active les contraintes du problème pour guider la recherche et res-treindre le domaine des valeurs prises par les variables de modélisation. De ce fait, enexploitant les techniques de résolution développées en recherche opérationnelle, il est pos-sible de guider la recherche et d’espérer aboutir à de bonnes solutions.


19/21 ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003

FIG. 5.– Comparaison de plusieurs méthodes

Comparison between some methods.

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 19

L’algorithme utilisé est basé sur les techniques de résolution sur domaine fini. Larecherche des bonnes solutions est réalisée par le biais des stratégies qui permettent de choi-sir efficacement à chaque itération les meilleures variables ainsi que les valeurs à leur assi-gner parmi tout l’ensemble possible. La performance de l’algorithme a été améliorée grâce àla détermination d’une borne inférieure sur le coût de chaque cellule dont l’insertion commecontrainte dans l’algorithme a permis d’aboutir très rapidement à une bonne solution initialeréalisable. Cette nouvelle classe de contraintes ajoute beaucoup de robustesse à la méthodepuisqu’elle est propagée dynamiquement sur toutes les variables à chaque changement deleur domaine.

De manière générale, les solutions que nous avons obtenues sont satisfaisantes. Pour desproblèmes de taille réaliste allant jusqu’à 50 cellules et 4 commutateurs, nous avons pu obte-nir assez rapidement l’optimum. Pour les problèmes de plus grande taille, une version limitéedans le temps de l’algorithme donne de bonnes solutions, comme a pu le montrer une com-paraison faite avec plusieurs autres heuristiques adaptées à ce problème. De manière géné-rale, le comportement de l’algorithme est très bon pendant les premières minutes de sonexécution. De cette comparaison, il ressort aussi que la méthode proposée est la première àpouvoir fournir des solutions optimales pour des réseaux d’une taille moyenne (jusqu’à 50cellules et 4 commutateurs).

Le problème d’affectation de cellules à des commutateurs pose encore plusieurs défis. Laméthode de programmation par contraintes étant relativement récente, plusieurs pistes sontencore à explorer dans l’adaptation de cette méthode à la résolution dudit problème. Lesfuturs travaux de recherche pourraient par exemple combiner les différentes heuristiques derecherche développées sur le problème afin d’accroître la performance de la méthode.

Manuscrit reçu le 30 novembre 2001Accepté le 17 novembre 2002

BIBLIOGRAPHIE

[1] AMOUSSOU(G.-E.), PESANT (G.), PIERRE(S.), « Affectation de cellules à des commutateurs par programmationpar contraintes »,IEEE CCECE’2001, May 13-16, 2001, Toronto, Canada.

[2] BEAUBRUN (R.), PIERRE(S.), CONAN (J.), « An efficient Method for Optimizing the Assignment of Cells to MSCsin PCSNetworks ». Proceedings 11th Int. Conf. on Wireless Comm., Wireless 99, 1, July 1999, Calgary (AB),pp. 259-265.

[3] GLOVER (F.), « Tabu Search : A Tutorial », INTERFACES, 20, n°4, 1990a, pp. 74-94.[4] GLOVER (F.), TAILLARD (E.), DE WERRA(D.), « A user’s guide to tabu search », Annals of Operations Research,

41, n°3, 1993, pp. 3-28.[5] HEDIBLE (C.), PIERRE(S.), « A Genetic Algorithm for Assigning Cells to Switches in Personal Communication

Networks », soumis pour publication en Juillet 2001, IEEE Transactions on Systems, Man, and Cybernetics.[6] HEDIBLE (C.), PIERRE (S.), « Algorithme génétique pour l’affectation des cellules à des commutateurs dans les

réseaux de télécommunications personnelles », in Proceedings of the IEEE CCECE’2000, May 6-10, 2000,Halifax, Canada, pp. 1077-1081.

[7] HOLLAND (J.-H.), « Adaptation in Natural and Artificial Systems », The University of Michigan Press, AnnArbor, Michigan 1975.


ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003 20/21

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 20

[8] HOUÈTO(F.), PIERRE(S.), « Affectation heuristique de cellules à des commutateurs dans les réseaux cellulairesmobiles », Annales des Télécommunications, 56, n°3-4, 2001, pp. 184-197.

[9] K IRKPATRICK (S.), GELATT (JR.C.D.), VECCHI (M.P.), « Optimization by Simulated Annealing », Science, 220,1983, pp. 671-680.

[10] MARIOTT (K.), STUCKEY (P.J.), « Programming with constraints : an introduction », MIT Press, 1998.[11] MERCHANT (A.), SENGUPTA (B.), «Multiway graph partitionning with applications to PCS networks».

Proceedings IEEE INFOCOM‘94, The Conference on Computer Communications, 2, 1994, pp. 593-600.[12] MERCHANT (A.), SENGUPTA (B.), «Assignment of Cells to Switches in PCSNetworks», IEEE/ACM Transactions

on Networking, 3, n°5, 1995, pp. 521-526.[13] PIERRE (S.), HOUÈTO (F.), « A Tabu-Search Approach for Assigning Cells to Switches in Cellular Mobile

Networks », accepté pour publication en Mai 2001, sous presse, Computer Communications.[14] PIERRE (S.), QUINTERO (A.), DE MONTGOLFIER (A.), « Affectation de cellules aux commutateurs dans les

réseaux mobiles: interactions des algorithmes génétiques, de recuit simulé et de recherche taboue », soumispour publication en Juin 2001, INFOR.

[15] QUINTERO (A.), PIERRE (S.), « Comparative Study of Tabu Search, Parallel Genetic Algorithms and SimulatedAnnealing for Assigning Cells to Switches in Cellular Mobile Networks », soumis pour publication en Juin2001, IEEE Transactions on Parallel and Distributed Systems.

[16] QUINTERO (A.), PIERRE (S.), « Hybrid and Parallel Genetic Algorithm Approaches for Assigning Cells toSwitches in Cellular Mobile Networks », soumis pour publication en Mai 2001, Journal of Parallel Algorithmsand Applications.

[17] SAHA (D.), BHATTACHARJEE (P.S.), MUKHERJEE(A.) ,« Heuristics for assignment of cells to switches in a PCSN: a

comparative study », IEEE International Conference on Personal Wireless Communication, 1999, pp.331-334.

BIOGRAPHIES

Matthieu ANDRÉ a recu un diplôme d’ingénieur de l’École Supérieure d’Électricité, France, en 2001, et unM.Sc.A en génie électrique de l’Ecole Polytechnique de Montréal en 2002. Il occupe depuis 2002 un poste d’ingé-nieur de recherche chez Gaz de France. Son principal domaine d’intérêt est l’optimisation.

Grâce AMOUSSOU a recu un diplôme d’ingénieur de l’Institut des Télécommunications de Siant-Petersbourg,Russie, en 1998, et un M.Sc.A en génie électrique de l’École Polytechnique de Montréal en 2001. Son principaldomaine d’intérêt est la planification de réseaux de télécommunications sans fil.

Gilles PESANT a obtenu un baccalauréat (1987) et une maîtrise (1990) en informatique de l’Université McGill,puis un doctorat en informatique de l’Université de Montréal en 1996. Après un stage postdoctoral en rechercheopérationnelle au Centre de recherche sur les transports (CRT), il s’est joint à l’École Polytechnique de Montréal oùil occupe le poste de professeur agrégé au Département de génie informatique. Ses intérêts de recherche gravitentautour de la programmation par contraintes et ses applications en confection d’emplois du temps, logistique destransports et planification des télécommunications. Il est membre de l’ACM et du comité de rédaction de la revue«Journal of Heuristics» publiée par Kluwer.

Samuel PIERRE est professeur titulaire au Département de génie informatique, directeur du Laboratoire derecherche en réseautique et informatique mobile (LARIM ) et titulaire de la Chaire de recherche industrielleCRSNG/Ericsson en systèmes réseautiques mobiles de prochaines générations de l’École Polytechnique de Montréal.Ses domaines de spécialisation incluent les réseaux de communications, l’informatique mobile, l’intelligence arti-ficielle répartie et apprentissage électronique (e-learning). Il a à son actif plus de 200 publications scientifiques dont5 livres, 5 chapitres de livres, 2 ouvrages collectifs édités. Il a reçu de nombreuses distinctions, dont le « Prix de lameilleure communication de recherche » aux Neuvièmes journées internationales sur les systèmes experts et leursapplications (en télécommunications) tenues en France en 1989, et le « Prix Poly 1873 pour l’excellence en ensei-gnement et en formation ». Il est éditeur associé de la revue IEEE Communications Letters et membre du comité édi-torial de la revue internationale Telematics and Informatics, publiée par Elsevier Science. Il a agi comme GeneralChair de plusieurs conférences internationales et est membre de plusieurs comités de programmes de conférencesinternationales et de conseils scientifiques.


21/21 ANN. TÉLÉCOMMUN., 58, n° 3-4, 2003

1773-Her/Telecom 58/3-4 19/03/03 16:59 Page 21

Documents

Une approche basée sur la programmation par contraintes