Multiflots de coût minimal avec fonctions de coût concaves

77

MULTIFLOTS DE A

COUT MINIMAL AVEC FONCTIONS DE

p a r

Michel M I N O U X * ancien dl~ve dc l'Ecole Polytechnique

A

COUT CONCAVES

R~SUM~. - - Le probl~me du multiflol de cost minimal sur un graphe (non oriental) a d'importantes applications dans le domaine de la planification des rdseaux de communication. Lorsque les fonctions de cost (sur les ardtes) sont concaves, il existe un tr~s grand hombre d'oplimums locaux et lc probl~me est de nature tr~s combinaloire. On donne tout d'abord un algorilhme de type s @ a r a t i o n e t d v a l u a t i o n p rog re s s ive permettant de le rdsoudre dans le cas des fonctions de coCtt lindaires avec c@t fixe. L'auteur donne ensuile un certain nombre de mdlhodes approchdes de rdsolulion applicables au cas gdndral des fonctions concaves, d i f fd ren t i ab l e s ou non . Les nom- breuses expdriences de calcul effectudes monlrent que les solutions fournies par les mdthodes approchdes sont souvent optimales, et toujours tr~s proches de l'optimalitd. De plus, des rdseaux de grande faille (200 nceuds el mdme plus) peuvent dtre traitds en an temps de calcul raisonnable (quelques minutes) sur un calculateur dlectronique. Les principales applications coneernant la planification d long terme des rdseaux de tdldcommuni-

cations et le probl~me de la tdlddistribution ~ une source, sont exposds en conclusion.

ABSTRACT. - - The min imum cost multicommodity network flow problem on a (non oriented) graph G has important applications in the area of telecommunication network design and planning. When the cost functions (on the edges) are concave, there exist a huge number of local optima and the problem appears to be highly combina- torial in nature. First we describe a Branch and Bound type algorithm which gives the solution in the case where all cost functions are linear, wilh fixed costs. Then we derive some approximate methods for the general case of concave cost functions, d i f f e r en t i ab l e or no t . Numerous computationnal results indicate that the solutions given by these approximate me/hods are often optimal and always very close to optimality. Moreover, they allow lhe lreatment of large scale networks up to 200 nodes and more, within a reasonable computation time (a fcw minutes on a computer). Finally, the most important applications are rnentionned in the conclusion.

PLAN. - - I. Introduction. I I : Formulation du probl~me. I I I : Caractdrisation des solutions. IV : Caractdrisation des solutions optimales. V : Recherche des optimums locaux par la mdthode des lindarisations successives. V I : Un algorithme pour le cas des fonctions de coflt lindaires avec co~t fixe. V I I : Mdthodes approchdes.

V I I I : Rdsultats de calcul. I X : Applications.

I . I N T R O D U C T I O N

Le p r o b l 6 m e du m u l t i f l o t de c o o t m i n i m a l su r u n

g r a p h e G ( n o n oriental) a d ' i m p o r t a n t e s a p p l i c a t i o n s

darts le d o m a i n e de la p l a n i f i c a t i o n des r 6 s e a u x de

c o m m u n i c a t i o n : r 6 s e a u x t d l 6 p h o n i q u e s , r 6 s e a u x d ' o r d i -

n a t e u r s , r d s e a u x de t 6 l d i n f o r m a t i q u e , etc. Darts t o u s

ces e x e m p l e s , les f o n c t i o n s de c o o t s o n t c o n c a v e s

(ou p e u v e n t ~tre a p p r o x i m ~ e s p a r les f o n c t i o n s con-

caves ) ; ceci r6 su l t e du p h d n o m 6 n e d ' d c o n o m i e

d '6che l l e (ou loi des v o l u m e s 6 c o n o m i q u e s [ 8 ] ) : le

c o o t d ' u n e u n i t 6 de riot s u p p l d m e n t a i r e su r une a r~ te

de G d~cro i t a v e c le r iot t o t a l qu i la t r a v e r s e .

On m o n t r e ( tans les p a r a g r a p h e s I I e t I I I que ce

p r o b l b m e 6 q u i v a u t h la r e c h e r c h e du m i n i m u m (l'u:~e

f o n c t i o n c o n c a v e sur u n d o m a i n e c o n v e x e ( t r o n ~ o n

c o n v e x e ) .

I1 en rdsu l t e qu ' i l ex i s t e g 6 n 6 r a l e m e n t u n n o m b r e

t r~s 6lev6 d ' o p t i m u m s l o c a u x , l ' o p t i m u m g loba l

( abso lu ) ne p o u v a n t 6 t re d6fini que c o m m e l ' o p t i m u m

local de c o o t m i n i m a l . L a c o m b i n a t o i r e es t tel le

q u ' a u c u n e m 6 t h o d e c o n n u e ne p e r m e t a c t u e l l e m e n t

(te c a l cu l e r des s o l u t i o n s exactes p o u r des g r a p h e s de

t a i l l e m 6 m e m o d 6 r 6 e (20 nceuds , 50 a rcs ou ar6 tes) .

On pas se en r e v u e , a u c h a p i t r e IV, u n c e r t a i n

h o m b r e de p r o p r i 6 t 6 s des s o l u t i o n s o p t i m a l e s ( loca les

ou g loba les ) du p r o b l 6 m e . Au c h a p i t r e V, on r a p p e l l e

u n e m d t h o d e efficace de ca lcu l des o p t i m u m s l o c a u x :

la m 6 t h o d e des l i n 6 a r i s a t i o n s success ives .

P o u r le cas p a r t i c u l i e r des f o n c t i o n s de c o o t

l in6a i res avec c o o t fixe, u n a l g o r i t h m e e x a c t d u

t y p e S.E.P. ( S @ a r a t i o n e t ] E v a l u a t i o n P r o g r e s s i v e , ou :

branch and bound) es t p r o p o s 6 a u c h a p i t r e VI . P o u r

le cas # n 6 r a l des f o n c t i o n s de c o o t n o n l inda i res e t

n o n ( l i f f6ren t iab les , u n c e r t a i n h o m b r e de m 6 t h o d e s

de r 6 s o l u t i o n a p p r o c h 6 e s o n t d o n n 6 e s au c h a p i t r e V I I .

Les r d s n l t a t s de ca lcu l d u c h a p i t r e V I I I m o n t r e n t

que les s o l u t i o n s f o u r n i e s p a r les m 6 t h o d e s a p p r o c h 6 e s

s o n t t r6s s o u v e n t o p t i m a l e s (e t t o u j o u r s t rbs p r o c h e s

de l ' o p t i m a l i t 6 ) .

Que lques a p p l i c a t i o n s s o n t en f in s u g # r d e s a u

c h a p i t r e IX .

L a t e r m i n o l o g i e e m p l o # e , en t h d o r i e des g r a p h e s ,

sera c o n f o r m e h celle de B e r g e [2, 3]. P r 6 c i s o n s p a r

* I n g d n i e u r c o n t r a c t u e l au C N E T - I s s y , g r o u p e m e n t RI~SEAUX ET CENTRES DE COMMUTATION, d d p a r t e m e n t ]~TUDES EN COMMUTATION ET RI~SEAUX.

1 / 1 6 ANN. TEL~COMMUNIC., 31, n ~ 3-4, 1976

78 M. M I N O U X . -- M U L T I F L O T S D E C O U T M I N I M A L A V E C F O N C T I O N S D E G O U T C O N C A V E S

ailleurs les nota t ions suivantes :

Y2 Si Y = est un M-veeteur , on d~signe par yT

le veeteur transpose. D'au t re part , le support du veeteur Y est l 'ensemble des eoordonndes non nulles de Y et on le no t e r a : supp ( Y ) = {u / gu =/= 0}.

Pour terminer , si A et B sont deux sous-ensembles d 'un ensemble E, on notera A-B l 'ensemble des ~l~- ments de A qui n ' a p p a r t i e n n e n t pas ~ B, e t :

A �9 B = ( A - - B ) U ( B - - A )

la difference sym6trique de A e t de B.

I I . F O R M U L A T I O N D U PROBLi~ .ME

I I .1 . Le r6seau de communica t ion 6tudi6 est

caract~ris6 par la donn~e d ' u n ensemble X de N centres X = {xl, x 2 .... x2v} (correspondant h des sources ou ~ des pui ts de trafic).

On notera G = [X, U] le graphe complet non orient6 construi t h par t i r de ces N nceuds. Chaque

ar~te u ~ U correspond h u n couple de centres :

(x~, x~) x~ ~ X,

x ~ X .

O n p o s e M = = - - 1 ) / 2 .

Lorsqu 'on associe h chaque arfite u ~ U de G un nombre r~el Yu >1 0 (appeld capacit~ de l'arfite), on

d6finit un rdseau : R = [ G, Y]. Le M-vecteur Y : (Y1, Y2, ..., YM) T e s t appel6

vecteur descriptif du r~seau R (ce vecteur caract~rise exactement le rdseau physique que l 'on d6sire construire).

I I .2 . Par ailleurs, le graphe G es t parcouru par N ( N - - 1 ) ] 2 ro t s inddpendants, not6s ~13' p o u r :

i = 1 .. . . . N , j = 1 . . . . . N e t i < j .

Par convent ion, le riot ~0ij a xi comme nceud source et x1 comme nceud puits, et sa valeur est une donn6e imposde dll (la valeur d ' un r o t d 'un certain produi t

d 'origine x~ et d 'ext r6mit6 x~ est la quant i t~ totale de ce produi t qui circule dans le graphe entre x~ et

x~).

(N. B. - - Pour certains couples (xl, xj) (i < j) , la valeur dii peut ~tre nulle.)

En convenan t que dii =

I D ] = [d~l i

J

sera appelde la matrice des ou simplement , matrice des

0 pour i >~ j, a matr ice

= 1, ..., N

1, ..., N

demandes point h point demandes. Dans tou t ce

qui suit, nous supposerons que la matr ice [D] est telle que le graphe non oriental: [X, A], off

A = {(x~xj)/i < j e t dli ~ O} est connexe.

I I .3 . Le probl6me est de construire un r~seau

R = [G, Y] (en ins ta l lan t sur les ar~tes de G des capacit6s Y1, Y2, . . . , YM) pe rme t t an t de satisfaire simultandment toutes les demandes d~1 au moindre cofit.

Ceci revient h rechercher un mult if lot de valeur fix6e et de cofit min imal sur un graphe non orient6 [33 h 35].

I I . 4 . Pour cela, on se donne, pour chaque ar~te u e U, une fonction r reprdsentant le cofit d ' ins ta l la t ion d 'une capacit6 Yu sur l 'ar~te u.

Nous supposerons que les fonctions (I)u satisfont les hypoth6ses suivantes :

Hypoth~se H 1)elles sont d6finies sur [0, + oo],

continues sur ]0, + oo[ et positives, s t r ic tement croissantes, sur [0, + 00[. D 'au t re part ,

(I)u(0)---- 0 et ~Pu(Yu) > 0 pour Yu > 0.

Hypoth~se H 2) elles sont concaves, c'est-h-dire qu'elles vdrifient :

(Pu(;~l y l + k2 y2) /> klapu(y1) + Z2qbu(y2 ) ,

avec ~1 ~> 0, k2 /> 0 et ;~1+ ;~2= 1.

HypothOse H 1 ) e x p r i m e s implement le fait que route ins ta l la t ion de capacitd suppl6mentaire est coO-

teuse et que le cofit doit ~tre nul si on n ' ins ta l le aucune capacit6.

HypothOse H 2) revieut h supposer (lorsque la fonc- t ion (I)u est ddrivable) que la ddriv6e est monotone non croissante. D 'un point de r ue prat ique, ceci t ra- dni t le fair que le coflt marginal d 'une uni t6 de riot suppldmentaire d iminue avec la capacit6 installde (ph6nom6ne d'6conomie d'~cheIle ou loi des volumes 6conomiques [8, 24]).

I1 est commode de dist inguer les diff~rents types de fonctions suivants :

Type 0 : fonction lindaire passant par l 'origine :

r Yu)-- yuYu (V Yu >~ 0).

Type 1 : fonction lin6aire avec ordonn6e ~ l 'origine :

O~(0) = o,

r 8u+ 7uYu (pour Yu > 0),

avec 8u > 0.

Type 2 : fonctions concaves lin6aires par morceaux,

continues sur ]0, + oo[, mais non pa r tou t d~rivables. Elles pourront ~tre considdr6es comme enveloppe inf6rieure d 'un nombre fini de fonctions de type 0 ou de iype 1.

Type 3 : fonctions concaves d6rivables sur ]0, + oo[,

rmus utiliserons, par exemple, des fonctions de la

ANN, T~L~COMMUNIC., 31, n ~ 3-4, 1976 2/16

M. M i N O U X . -- M U L T I F L O T S D E c o U T M I N I M A L A V E C F O N C T I O N S D E COUT C O N C A V E S 79

forme K u ( Y u ) ~, off Ku est une constante et ~ un

param6tre (0 < ~ < 1).

Remarque.

Si l 'arSte u e s t interdi te pour certaines raisons dans

la solution (c'est-h-dire qu 'on ne peut y installer de capacit6), il suffira d 'y associer la fonction :

Ou( Y u ) = + ~ pour Yu > O.

Ainsi, la formula t ion prd@dente permet de rendre compte de probl6mes prat iques dans lesquels le graphe G n 'es t pas complet.

II.5. Soit Y = ( Y t , Y~ ..... Y M) T"

Ddmonstration. ~ peut fitre ddfini par un ensemble

d ' in6quat ions lin6aires expr imant la compatibil i t~

d ' u n riot de plusieurs produits sur un graphe non

oriental, dont les arStes sont munies de capacit6s [27,

331.

Par ailleurs, si Y r R M+ est vecteur D-admissible, alors Y + Z e s t encore D-admissible,

VZ > 0 ( Z ~ R M+).

Lc tron~on ~ comporte donc un certain nombre de rayons extrdmaux (cf. [5, 31]), ainsi qu ' un certain nombre de points extrdmes que nous allons m a i n t e n a n t caract~riser.

Le vecteur Y sera dit D-admiss ible si les capacitds Yu(u E U) permet ten t d'6couler s imul tandment sur G les diff6rents riots q~ij de valeurs d i j .

On appelle clomaine d'admissibil i td relatif h la matr iee de demandes D l 'ensemble des vecteurs Y E R M+ D-admissibles. I1 sera notd :

= {Y G R M+ / Y est D-admissible}.

II.6. Les d6finitions qui prdc6dent pe rmet ten t de formuler le probl6me sous la forme d 'un programme d 'opt imal isa t ion non lin6aire sous contraintes :

l Min O(Y) = Z (~u( Yu), (p) ueU

y ~ ) c RM+.

L ' appar tenance du vecteur Y au domaine ~ d6finit l 'ensemble des contraintes de (P). Avan t de rechercher des solutions optimales, il est donc impor t an t de caract6riser l 'ensemble ~).

III. CARACTI~RISATION DES SOLUTIONS

On appelle solution de (P) tou t vecteur Y appar- t e n a n t h ~ . On appelle graphe associd h la solution Y le graphe partiel G ( Y ) = [X, U'], off:

U ' = supp ( Y ) = {uE U / Yu > 0},

D'apr6s l 'hypoth6se du paragraphe II-2, G(Y) est toujours connexe.

III.2. Routage et uniroutage.

On appelle routage l 'opdrat ion consis tant h associer h chaque riot (?lj une ou plusieurs chagnes:

Lr.. (r = 1, rij)

jo ignan t xt et xj clans G en pr6cisant quelles quanti t6s

1 ~.e. cr rlj doivent s'6couler sur cbaque de r o t a i j , ,3, ..., .. tj

chaine :

r t j ( ~, r = dij).

r = l t j

Un routage pent donc 6tre consid6r6 comme une

application f, R N2 -~f R M+ qui, h la matrice D = [dlj]

associe le vecteur Y = [Yu] = f(D) par la proc6dure suivante ;

a) Yu = O, V u E U,

b) pour t o u s l e s couples (xi , xj) (i < j ) ,

c) pour r = 1, ..., rij :

faire Yu = Yu + rij v u ~ Lrij ,.

re tourner en b).

Un uniroutage est un routage pour lequel :

r i~= 1 ( V x i , x 3).

Un vecteur uniroute est un vecteur Y a R M+, tel que Y = f(D), off f est un uniroutage.

L'intdr~t des vecteurs uniroute appara i t dans le thdor~me 2 (III.4).

III.1. Th6orSme 1.

Le domaine d 'admissibil i t6 ~ relatif h une matrice de demandes :

D = [diJli = 1 . . . . , N ,

j = 1 . . . . , N .

est un tron~on convexe de R M+ (*).

(*) Un tron~on couvexe est un polySdre convexe non born6.

III.3. Lemme 1.

Lorsque les fonctions q)u sont de type 0, une solu-

t ion optimale fl distance finie du probl~me (P) correspond (en l 'absence de d6g6n6rescence) h u n vecteur uniroute.

Ddmonstration. Lorsque Ou(Yu) = yu Y u , le coflt de passage d 'une uni t6 de r o t sur une ar~te u quelconque

de G ne d6pend pas de la capacitd Y u . Dans ces conditions, uue solution de coflt minimal est obtenue

3/16 ANN. Tg;I,~COMM(:NJC., 31, n ')~ 3-4, 1976

8 0 M. M I N O U X . -- M U L T I F L O T S D E C O U T M I N I M A L A V E C F O N C T I O N S D E C O U T C O N C A V E S

pa r un i routage de chaque riot ~i~ sur une plus cour te chaine ( re la t ivement aux longueurs yu) de xi h x1 dans G. S'il existe un cycle de longueur n6gat ive (en par t icul ier , s'il existe une ar~te de longueur n4gative), l ' o p t i m u m de (P) est non bornd (--o0).

Lorsqu ' i l n 'ex is te pas de cycle de longueur n6gative, on peu t d6finir un ensemble de plus courtes chaines sur le graphe G [6, 10]. Lorsqu ' i l existe deux chaines de m4me longueur entre xl et x l , alors le probl6me (P) a d m e t une infinit6 de solutions opt imales (d4gdn6- rescence). En l ' absence de d6g6n6rescence, la solut ion op t imale es t unique et correspond h un vec teur uniroute.

III.4. Th6orSme 2.

Les poin ts ex t remes de 9 correspondent h des vecteurs uniroute.

Ddmonstration. L'ensemble des points ex t remes de 9 est l ' ensemble des solut ions opt imales non d6gd- n6rdes et h d is tance finie des p rogrammes lindaires

i M i n y - Y , = u Y u ,

Y ~ 9 c R M+,

lorsque y pa rcour t R M+. D'apr6s le Lemme 1, ils cor respondent h des vecteurs

uniroute .

Lorsque la fonction (I)(Y) est s@arable , c 'est-fi-dire :

(P(r) = E Ou( ru), uEU

T = (Tu)uEu est un sous-gradient de (I) en Yo si et seulement si Tu est un sous-gradient de r en yOu.

IV.2. Th6or~me 3.

Une condi t ion n6cessaire pour que Y* soit o p t i m u m (absolu) de (P) est que Y* soit solut ion op t imale du p rogramme lin6aire :

! M i n T . ( Y - - Y*) , (PL)

Y e 9

pour tou t T e a a p ( y %

Ddmonstralion.

Si, pour T ~ b(I)(Y*), Y* n 'es t pas solut ion op t imale de (PL), alors il existe Y e D tel q u e :

T . ( Y - - Y*) < 0 ;

d 'apr6s la concavit~ de (I):

(I)(Y) ~< (I)(Y*) + T . (Y - - Y*) < (I)( Y*) ,

ce qui cont red i t l ' op t imal i t6 (globale) de Y*. Le corollaire su ivant mont re que l 'on peu t (sans

perdre l 'op t imal i t6 ) l imi ter la recherche de l ' o p t i m u m absolu de (P) aux seuls points extr4mes de ~D. Cet i m p o r t a n t rdsul ta t sera sys t6ma t iquemen t utilis6 dans la suite.

IV. C A R A C T I ~ R I S A T I O N D E S S O L U T I O N S O P T I M A L E S I V . 3 . Coro l la ire 1.

I V . 1 . R a p p e l de q u e l q u e s propri6t6s des f o n c - t i o n s c o n c a v e s .

E t a n t donn6e une fonct ion concave (D(Y) de l~M---~ R, on note dom ((I)) le domaine de d6finition de (I) et in t -dom ((I)) l ' in t6r ieur du domaine de d6finition. Pour une fonction (I) diffdrentiable en yo, on note grad (I)(yo) le g rad ien t de (I) en yo, et on a la propri6t4 fonda- menta le su ivante :

(I:)(Y) ~< (I)(yo) + grad (I)(y0). ( y _ yo) (V Y ff RM).

Pour les fonctions concaves non diff6rentiables, on gdn6ralise la not ion de g rad ien t pa r la not ion de sous- g r a d i e n t : on di t que T = [T1, T2, . . . , TM] est un sous-gradient de (I) en yo si et seulement s i :

(I)(Y) ~< r 1 7 6 2 4 7 T . ( Y - - yo) ( V Y e R M).

On note ~q)(yo) l ' ensemble des sous-gradients de (I) en yo. ~(I) est un ensemble convexe ferm6, appel6 le sous-diff6rentiel de (I) en yo.

Toute fonct ion (I)(Y) concave propre (c 'est-~-dire [(I)(Y)[ < -t- oo VV z dora ((I))) poss6de un sous- g rad ien t en t ou t po in t Y E in t -dom ((I))[22, th6o- r6me 2, p. 495].

Soit l ' o p t i m u m absolu Y* de (P) est un po in t ext r4me de 9 (vecteur uniroute) , soit il existe un po in t ext r4me de 9 op t imum absolu de (P).

Ddmonstration. Si la solut ion op t imale de (PL) est unique (non d6g6ndr4e) pour un sous-gradient :

T ~ bO(Y*) ,

alors Y* est un poin t extr4me de ~), donc un vec teur uni route (d 'apr6s le Lemme 1).

Si Y* n 'es t pas poin t ex t reme de 9 , cela veu t dire que Y* est combinaison lindaire convexe de p points ex t remes :

y , = : q y a + ~ y 2 q _ . . .q- ~ p y v ,

P

avec y l : / : y 2 . . . . . V:YP et 0 < c r ( ~ : q = 1) ,

- - ~2 Ya + "- + ~p Yp posons : Y = f i g . On a :

Y * = ~1Y1+ (1 --r162 Y 0 < cq < 1,

p o s o n s : H = Y - - yt , . on a :

Y = Y * + e l H e t : y l = y , _ ( l _ e l ) H.

En u t i l i san t la coneavit6 de qb et la propri6t6 des sous-gradients , on a, pour T ~ bO(Y*) :

ANN. T~LI~COMMUNIC., 31, n ~ 3-4, 1976 4/16

M. M I N O U X . M U I , T I F L O T S DE COUT M I N I M A L AVEC F O N C T I O N S DE COUT CONCAVES 8 1

O(Y) ~< q)(Y*)+ - t T . / 4

et (I)(Y1) ~< O(Y*) -- (l -- 71) �9 T . H .

Comme Y* est op t imum absolu, ceei implique

T - H = 0 et : O ( Y * ) = (I)(Ya) = qb(y). Done Y~ est aussi op t imum absolu de (P), et c'est

un point extreme de 5). Ceei 4tant, la condit ion d 'opt imal i t6 donn6e par le

lhdor~me 3 ne suflit pas h caract6riser sans ambiguit6 l ' op t imum global de (P). En effet, elle est 6galement v6rifi6e par beaucoup d 'autres poinls du tron~on fl)

qu 'on appelle des optimums loeaux (ceci provient du f a r que (P) n 'es t pas un programme math6mat ique

eonvexe [14, 40]).

Le r4sultat su ivant donne une condit ion suflisante pour qu ' un vecteur yo a 9) soit op t imum local de (P).

IV.4. Th6or~me 4.

Si y o ~ ~) est solution optimale unique (non d6g6-

ndrde) de (PL) :

i Min T . ( Y - - yo) , (PL) Y E ~ ,

pour tous les sous-gradients T e 5(I)(Y~ alors yo est

un op t imum local de (P).

Ddmonstration. Par hypoth&e, on a donc :

T . ( Y - - yo) > 0 V Y c ~ ( Y @ yo),

et y T c S q b ( Y ~

Rappelons que l 'existence d 'un sous-gradient en yo implique l 'existence de d6riv6es direct ionnelles:

(I)'(d) -- lira ((I)( yo + kd) - - dP( yO))lZ k . + O +

et que : O'(d) Min { T . d }

Tr 5(I){ yO)

[22, th6or6me 16, p. 512].

On a donc O'(d) > 0, V d = Y - yo (direction

rdalisable) et par suite yo est op t imum local de (P).

I V . 5 . C o r o l l a i r e 2 .

Si la fonction qb(Y) est diff6rentiable, et si yo est solution optimale unique (non d6gdn6r6e) de :

l in grad qb(yo) . ( y _ yo)

Y G ~ ,

alors yo est op t imum local de (P).

Les r6sultats suivants conduiseut ~ une caract6ri- sation beaucoup plus fine de l ' op t imum global de (P).

toute ar6te vG F, on a i t :

E o,~(r ~ r ~ ~ ,~c r-{v} ~E F

D~monstration. Consid6rons la solution Ya construite h part ir de yo en dOroutant la totalit6 du flot Yv ~

passant sur l'arfite v sur la chaine F - - { t , } .

On a : y l = y o v u ~ p ,

Yv~= O,

et y l = yo u + y v O v u E F _ {v}.

Evidemment , Ya ~9) et :

O(Y~) -- O( V ~ = Y, qbu(rO + yo) _ y~ Ou(Y~ ,,~F {v} ~r

Pour que y0 soit op t imum global de (P), il faut

que l 'on ait ( I ) (Ya ) - (I)(Y ~ >/ 0, d'ofi le r&ul ta t .

Evidemment , ce rdsultat n 'est gu6re utilisable en

prat ique puisqu' i l implique un tr6s grand hombre de

vdrifications (au tan t que de cycles darts G). C'est pourquoi nous 6non~ons le th6or6me suivant :

IV.7. Th6or~me 6.

Soit yo une solution de (P) et soit v = (xi , xj)

tel que Yv ~ > 0. Soit L la chaine jo ignant xi "~ xj duns G - - { v } , telle que :

w(L) = E Ou( r ~ + r ~ - q)~( r ~ uEL

soit minimal .

Pour que la condit ion n6cessaire dn tb6or6me 5 soit v6rifi6e, il faut et il sulIit que :

w(L) - - Or(Y~ /> 0.

V v ~ U v6rif iaut : Yv ~ > 0.

Ddmonstralion. Elle se d&luit du lhdor~me 5 on consid6rant :

V v E U(Yv ~ > 0) le cycle P - - L U {v}.

Remarque.

Lorsque les condit ions ndcessaires des th6or6mes 5 ou 6 ne sour pas v6rifi6es, on met en 6vidence une solution Y 1 telle que qb(y1) < dp(Yo). Ce r6sultat cst h la base ties m6thodes itdratives qui serout expos6es au chapitre VI.

V. R E C H E R C H E D E S O P T I M U M S L O C A U X P A B L A M I ~ T H O D E

D E S L I N I ~ . A R I S A T I O N S S U C C E S S I V E S

I V . 6 . T h 6 o r S m e 5 ( Z a d e h [ 3 8 ] ) .

Une condit ion n6cessaire pour que yo soit op t imum global de (P) est que, pour tou t cycle F tie G e t pour

Nous supposerons ici que les fonctions qbu sont diff6- rentiables sur [0, + cx~[. Pour rechercher un point extrSme satisfaisant les conditions n@essaires d 'opti-

malit4 globale, la d6monstrat ion du thdor6me 3 sugg6re la mdthode itdrative suivante :

5/16 A~-~-. 'r~:~.~::t:o.~,Mvx,:., 31, ,,o, 3-4, 1:~76

82 M . M I N O U X . - M U L T I F L O T S D E G O U T M I N I M A L A V E C F O N C T I O N S D E G O U T C O N C A V E S

V.1. Algorithme (A 1).

a) Pa r t i r d 'une solut ion ini t iale donn6e y0.

b) A l ' i t6 ra t ion t, soit y t la solution courante .

dOu Calculer : ytu = d Y ~ (Ytu) la d6rivde de la fonc-

t ion (I)u au po in t Y~u.

c) D6finir yt+l comme un po in t ext r4me de

solut ion op t imale d e :

l M i n y t . y = ~ y t u . Y u , (PL) u

Y a ~ .

d) Si (I)(yt+l) < ~ ( y t ) , f a i r e t = t § 1 et r e tourner

en b.

Si ( I ) ( y t + l ) = ~ ( y t ) fin de la proc6dure.

Cette m6thode est connue, en p r o g r a m m a t i o n ma th6mat ique , sous le nom de mdthode des lindari-

sations successives [14, 17, 40].

A l '6 tape c du calcul, la r6solution du probl6me (PL) revient (cf. Lemme 1) h rechercher un ensemble

de plus courtes chaines sur le graphe G dont les arfites sont munies des longueurs ytu (Noter que l ' hypo- th6se H 1 impl ique y~t > 0, donc l ' absence de cycles de cofit n6gatif .) Ceci rev ient h calculer un ensemble de plus courts chemins po in t h po in t sur le graphe G' d6dui t de G en rempla~an t chaque arfite u = (xi , xj) pa r deux arcs (x~, xi) et (x j , x~) de longueurs 6gales h celle de u. On ut i l isera pa r exemple l ' a lgor i thme de F l o y d [10], de Dantz ig [6] ou une de ses var ian tes [12].

V.2. Convergence.

L 'a lgo r i t hme (A 1) converge en un hombre fini d ' i t4 ra t ions vers un po in t sa t i s fa isant la condi t ion ndcessaire d ' op t ima l i t6 du th6or6me 3.

Ddmonstration. La suite des valeurs :

(I)(yo), (I)(y1) . . . . . ( I ) ( y t )

est monotone , d6croissante au cours des i t6rat ions. En effet :

(I)(yt+l) 4 (I)(yt) 4- grad (I)(yt) . ( yt+l _ y t ) <. (I)( y t ) .

Le caract6re fini de la convergence p rov ien t du fai t que ~ a un nombre fini de poin ts ex t remes et qu 'on ne passe j amais deux fois pa r le m~me poin t ext r4me t a n t que la convergence n ' e s t pas obtenue.

Enfin, lorsque ( I ) ( y t + l ) = ( I ) (y t ) , on a :

O(Yt ) = ~ ( y t + l ) <~ O ( y t ) 4- grad (I)(Yt). ( y t + l _ y t ) ,

d 'ofl grad (I)(Yt).(Yt+Z _ y t ) >~ O,

et p a r suite le po in t yt+l sa t i s fa i t la condi t ion ndcessaire du th6or6me 3.

D 'apr6s B. Yaged [34, 35], la m6thode converge tou jours en un pe t i t nombre d ' i t6ra t ions . Pa r ailleurs,

notre expdrience [25] nous a permis de fixer entre 8 et 10 le nombre maximal d ' i td ra t ions ndcessaires, et de cons ta te r que ce nombre ne d @ e n d p r a t i q u e m e n t pas de la tai l le du probl6me trai td.

V.3. In f luence de la so lu t ion de d6part. I n s u f - f i sance de la m 6 t h o d e .

Par contre, le r6sul ta t ob tenu d6pend de fa~on tr6s cr i t ique de la solut ion de d6par t yo.

Ainsi, pour les fonctions de cofit de type 1, nous d6montrerons (cf. th6or6me 8 ci-dessous) que l ' a lgo- r i thme A 1 converge tou jours en une seule itdration et que la solution y1 ob tenue est tel le q u e :

supp (Y1) c supp (Y~

(au t remen t dit , G(Y 1) est un graphe par t i e l de G(y0)).

Dans le cas g6n6ral, on cons ta te que le cofit de la solut ion y t obtenue pa r l ' a lgor i thme (A 1) ne repr6- sente qu 'une am61ioration marg ina le assez faible du cofit de la solut ion y0 ; en r6alit6, des ~carls de l'ordre

de 30 ?t 40 ~ par rapport ?t la solution optimale sont courants : t ou t ddpend de la qual i td de la solut ion de d6par t utilisde (cf. aussi 7adeh [38]). C'est ce qui l imite cons iddrablement l ' in t6r6t de l ' a lgor i thme (A 1) pour la rdsolut ion du problbme (P). En r6alit6, le probl6me (P) est de na tu re essent ie l lement combina-

loire : il s 'agi t , en fait , pa rmi t ous l e s op t imums locaux, de t rouver un o p t i m u m local de cofit minimal . Or, le hombre d ' op t imums locaux peu t ~tre fan tas t iquemen t g r a n d : clans le cas des fonct ions de cofit de type 1, nous allons voir qu ' i l peu t y avoir a u t a n t d ' o p t i m u m s locaux que de graphes par t ie l s connexes de G! (cf. th6or6me 7, w VI-1).

D E S

VI. U N ALGOI:tITHME P O U B LE GAS

F O N C T I O N S DE C O U T L I N / ~ A I B E S AVEC C O U T F I X E

Nous consid6rons ici la classe des probl6mes (P) pour lesquels les fonctions de cofit sont de type 1,

c 'es t -h-dire d6finies V u E U, pa r :

l Ou(0) = 0,

Ou( Y u ) = 8u 4- yu . Yu pour Yu > 0,

(~u > 0 , u u ~ U) .

Le probl6me (P) dev ien t alors dans ce c a s :

l Min (~(Y) = ~_~ (~u 4- yu . Yu ) , (P 1) uEsupp(Y)

Y e f f ) .

ANN. TI~LI~COMMUNIC., 31 , n ~ 3-4 , 1 9 7 6 6/16

M. M I N O U X . -- M U L T I F L O T S D E C O U T M I N I M A L A V E ( ; F O N C T I O N S D E C O U T C O N C A V E S 83

VIA. Th6orbme 7 : caract6risation des optimums locaux.

Soil S c U un sous-ensemble d 'ar~tes de G tel que le graphe par t ie l Gs = [X, S] soit connexe.

Soit y0 un po in t ex t reme de 9) solut ion d e :

l M i n y . Y - - ~ y u Y u , u E U

avee YES1) et supp (Y) c S .

Alors yo est un op t imum local de (P 1).

Ddmonstration. Soit Y~ un point quelconque de {D, y1 # yo.

E t pour kE] O, 1[ so i t : Y = y o + k ( Y i - - yo) .

Posons : S l - supp (Yi) el : S ~ supp (Y~

�9 Supposons d ' abo rd que S 1 c S O .

On a supp ( Y ) = S o et comme par ddfinit ion de yo on a : y Y~ ~> y yO, on en conclut q u e :

@(y) 7> @(yo).

�9 Supposons ma in t enan t que S 1 r S ~

Alors, V)~ E ]0, 1[,

S = supp ( Y ) - - S o U S ~ et il existe y E S ~ - S ~

A l o r s : ~ ( Y ) = ~ ( Y ~ k y ' ( Y a - - y 0 ) § ~] 8u, uE S1-S ~

d'ofl : di)(Y) >~ qb(YO)+ k y . ( Y 1 - - y 0 ) + 8v.

Si y (Yi ) /> y(i7o), alors on a : ~(17 ) >~ O(Y~

Si y (Yl ) < y(i7o) , alors il suffit de ehoisir :

G X < _ y . ( y ~ _ yo) P ~ 1 7 6

O(Y) > 00( yo).

Dans t o u s l e s cas, on a prouv6 que dans un cer ta in voisinage de yo :

O(Y) 7> (I)( yo) .

d 'oh l ' op t imal i t6 locale de yo.

Alors Ie probl6me (PL) (cf. V- l ) d e v i e n t :

l in T . ( Y - - y0) ,

Y E ~ ,

et la solution Y~ de (PL) est telle q u e :

yo = 0 ~ T u = + ~ ~.~ Ylu= O,

done supp (Y1) c supp (Y~

et d 'apr6s le thdor6me 7, c 'es t un op t imum local de (P 1).

VI.3. Nouvelle formulation du problbme (P 1).

D'apr6s le th6or6me 7, on peu t assoeier $ tou t graphe par t ie l connexe Gs de G un op t imum local de (P 1). Le thdor6me 8 indique qu 'on peu t l ' ob ten i r en recherchant uu ensemble de plus courtes chaines sur G s - - [X, S], off chaque ar~te u e S est munie de la longueur y u .

Pour tou t ensemble S c U, ddfinissons T(S) p a r :

y(S) = iV[in y . Y ~ yu" Y u ,

( l ) , ~=t I Sous les eont ra in tes :

Y E 0 ) et s u p p ( Y ) c S ,

(par convent ion y ( S ) - - + oo si G a - [X, S] n 'es t pas eonnexe) et a(S) - ~] au �9

uES

Alors le probl6me (P 1) est 6quivalent h rechereher S* c U solution d e :

(P;) T ( S * ) - 8 ( S * ) = Min { y ( S ) § 8(S)} s o u

(le nombre de par t ies de U est : 2 M, ee qui fai t bien appa ra i t r e iei le caraet6re eombina to i re du probl6me).

VI.4. Une m6thode de s6paration et d'6va- luation progressive (S.E.P.).

VI.2. Th6orbme 8.

Soit yo un po in t extrfime quelconque de ~ . Si yo est pris comme solut ion de ddpar t , alors la

mdthode des l indar isat ions successives (a lgor i thme A 1) condui t tou jours en une i tdra t ion h u n o p t i m u m local de (P 1), solut ion d e :

i M i n y . Y = ~ yu" Yu, uEU

Y E ~ ,

supp (Y) c supp (Y~ .

Ddmonstralion. Le vecteur T - ( T u ) u = I . . . M ddfini par :

T u = + O o si Y~ 0

T u = Yu s i YOu > 0

est un sous-gradient de q) en yo.

Le probl6me (P~) peu t ~tre vu comme un pro- g ramme en hombres entiers : il suff~t d 'associer une var iable enti6re ~u h valeurs darts {0, 1} h chaque ar~te u E U.

Alors (P[) est dquivalent fi:

' Min y . Y + 8 . ~ ,

t a v e c : Y E ~ c RM+, (2) ( Y - - A . ~ <~ O,

e (0, l i M .

off A est une grande eons tan te posi t ive e t :

= G , G ..... ~M) T.

(L '6quivalenee est obtenue en r e m a r q u a n t que, ndcessairement , h l ' o p t i m u m de (2) :

Yu > O ~ ~ u = l

et {,~= 0 ~ Y ~ = 0).

7 / 1 6 ANN. 'FELI'COMMUNIC., 31, n ~ 3-4, 1976

84 M. MINOUX. -- MULTIFLOTS DE COUT MINIMAL AVEC FONCTIONS DE COUT CONCAVES

Plus prdc isdment , (2) a p p a r t i e n t h la ca tdgor ie de

p r o g r a m m e s en n o m b r e s en t ie rs di ts h cofils fixes ou

h charge fixe (en angla is : fixed charge problems) [13,

18, 23, 32].

P o u r ce t t e classe de p rob l~mes , la difficultd pro-

v i e n t du fa i t que les so lu t ions op t ima le s con t inues

sont gdndra l emen t tr~s 61oigndes des solu t ions op t i -

males enti~res. La m d t h o d e que nous al lons p r6sen te r

est du t y p e r eche rche par sdparation el dvaluation

progressive (SEP OU b r a n c h and b o u n d p o u r les au t eu r s

anglo-saxons) . E l le a dtd uti l isde avec succ~s p o u r

cer ta ins p rob l~mes s imila i res [23, 32].

Dans le p rob l~me (P~), l ' e n s e m b l e de solu t ions cor-

r e spond h l ' e n s e m b l e des par t i es de U.

L'arbre de ddcision 73 associd au p rob l~me (PI') es t

le g r aphe or ient6 sans cycles ddfini de la fagon

s u i v a n t e :

- - les nceuds de 73 c o r r e s p o n d e n t a u x par t i es de

U. Si les nceuds de 73 son t indic6s pa r t = 1, ..., 2 M,

on n o t e r a U(t), la pa r t i e de U c o r r e s p o n d a n t au

nceud t de 73;

- - (l, t') est un arc de 73 si e t s e u l e m e n t s i :

U( t ' ) c U(t) e t IU(t')I = I U ( l ) l - 1.

On di t que t e s t le pr6d6cesseur (un ique) de l ' ; t ' est

un successeur d i rec t de l ;

- - la rac ine de l ' a r b o r e s c e n c e est le nceud t = 1,

te l que U ( I ) = U.

IU(/)I sera appel6 le n i v e a u du nceud l dans l 'arbre73.

U n nceud l ' t e l qu ' i l ex is te un c h e m i n de l h t' dans 73

est appeld un successeur de t. V t on a :

U U(t ' ) = U(t) t' successeur direct de t

L'ensemble des successeurs directs d 'un nceud t

reprdsente donc une couoerlure de U(I).

Remarque.

Darts la p l u p a r t des e x e m p l e s d ' a p p l i c a t i o n de la

m d t h o d e SEP, l ' e n s e m b l e des successeurs d i rects d ' u n

nceud t r e p r f s e n t e une parlition du sous -ensemble des

solu t ions associ6 au nceud l. C e p e n d a n t , ce t t e c o n d i t i o n

n ' e s t pas ind i spensab le au succ6s de la m f t h o d e : il

suflit que ce soi t une couverlure. C'es t le cas qui v a

se p r f s e n t e r ici. E n effet, il es t faci le d ' i n t e r d i r e une

ar~te u darts la so lu t ion , c ' e s t -h -d i re d ' ex ige r Yu = 0 ;

mais p o u r impose r la pr6sence d ' u n e arfite u dans la

so lu t ion , il f a u d r a i t t en i r c o m p t e de la c o n t r a i n t e

Yu > 0, ce qu i se ra i t b e a u c o u p plus difficile.

Une [onction d'dvaluation (ou fonc t ion m i n o r a n t e

sur 73) est une fonc t ion g ddfinie V t ~ 73 et te l le que :

(3) g(t) ~< Min {T(S)-~ 8(3)} S c U(t)

( m i n i m u m pris sur tons les sous -ensembles S c U(I)

te ls que G s = [X, S] soi t connexe ) e t :

(4) l ' successeur de I =~ g(l ' ) /> g ( l ) .

On vdrif ie que la fonc t ion :

g(l) = y(U( l ) ) + Min {8(S)} S c U(t)

G S connexe

est une fonc t i on d ' d v a l u a t i o n qu i vdrif ie (3) e t (4).

Le p r e m i e r t e r m e y(U(t ) ) est o b t e n u en r e c h e r c h a n t

un e n s e m b l e de plus cour t e s cha ines sur le g r aphe

pa r t i e l : G(t) = [X, U(I)] d o n t les ar~tes son t m u n i e s

des longueurs yu (cf. VI-3) .

Le second t e r m e co r re spond h la r echerche , sur

G(t) d ' u n g raphe pa r t i e l c o n n e x e de l o n g u e u r t o t a l e

m i n i m a l e lo r sque les ar~tes u ~ U(t) son t m u n i e s des

longueurs 8u > 0 (arbre de l o n g u e u r t o t a l e min ima le ) .

On sa l t qu ' i l ex is te des a l g o r i t h m e s tr~s eflicaces p o u r

r~soudre ce p rob l~me ( a l g o r i t h m e de K r u s k a l [20, 28]).

L ' i n td r~ t de la fonc t ion g(l) es t le s u i v a n t : si yo

est une so lu t ion de (P 1) (par exemple , une b o n n e

so lu t ion approchde) et si p o u r un noeud t de 73 on a :

g(l) ~> (I)( y o ) ,

alors il est inu t i l e d ' e x p l o r e r les successeurs du nceud t

dans l ' a rb r e de ddcision.

Si g(l) es t une b o n n e a p p r o x i m a t i o n du m i n i m u m

dans (3), on 6vi te ainsi la desc r ip t ion d ' u n e i m p o r -

t a n t e pa r t i e de l 'arborescenee 73.

V I . 5 . A l g o r i t h m e ( A 2 ) .

P o u r un nceud l ~ 73, on note , p red (t) le pr6ddces-

seur i m m ~ d i a t de l e t : v(l) l ' a r~ te de G tel le q u e :

U(I)) = U(I ' ) - - {,(l)} off : t ' = p r e d (l).

A une 6 tape que l conque , on no te T l ' e u s e m b l e des

nceuds de 73 examin6s , et T o c T l ' e n s e m b l e des

nceuds p e n d a n t s (de degr6 1). On pose t = I TI.

a) Soi t yo une so lu t ion de ( P 1 ) e t z o = (D(Y ~

(si on ne conna i t pas de solu t ion , z o = + oo).

T = {1} ; T o = {1} ; [ : 1 ; g ( 1 ) = 0 ;

p red ( 1 ) : 0 ; ~ ( 1 ) ~ 0.

b) D 6 t e r m i n e r le nceud t o te l q u e :

g(lo) : Min {g(l)} tET O

Si g ( t 0 ) > z 0 = FIN, yo est so lu t ion o p t i m a l e de

cofi t z o , s inon :

c) U ( t o ) = U

t ~ t o .

d) t ' = p red (l) ;

fa i re : U(to) = U(to) - - {v(t)}.

�9 S i t ' :/= O, fa i re t = t ' e t r e t o u r n e r e n d ) .

�9 Si t ' = O, a l ler e n e ) .

e) P o u r tous les arcs u ~ U(to) s u c c e s s i v e m e n t :

�9 poser U ' = U ( l o ) - - {u};

�9 si G ' = [X, U ' ] n ' e s t pas connexe , r e t o u r n e r

en e), s inon :

ANN. TI~LI~COMMUNIC., 31, n ~ 3-4, 1976 8/16

M. M I N O U X . M U L T I F L O T S D E ( ; O U T M I N I M A L A V E ( ; F O N C T I O N S D E C O U T C O N C A V E S 8 5

�9 calculer Y solution optimale de :

I Min ,( . Y,

Y ~ ~ ) ,

s u p p ( ~ ) = U ' ;

�9 s o i t : z : y . Y - t - 8 ( s u p p (Y) ) ;

si ~ < Zo, poser : z o - ~ et y o = i-v.

�9 Calculer g - - y . Y + Min {8(S)} S o U '

(i S c 0 n n e x e

si g >~ zo, retourner en e), sinon :

�9 faire: [ : i + 1 ;

poser : T TuO} ; g ( i ) = ~ ; TO= TOu{i}

pred 0) l o ; v(i) u,

et re tourner e u e ) .

f) Faire T ~ T ~

retourner en b).

L 'algori thme (A 2) peut n@essiter l ' examen d 'une fraction impor tante de l 'arborescence ~ complete (cf. [25, 32], et les r6sultats du chapitre VIII) . Son champ d 'appl icat ion restcra donc limitd aux probl~mes de

petite taille :

(N ~< 10 nmuds, M ~< 20 ar~tes).

Au chapitre VII I , il sera utilis6 pour valider un

certain hombre de mdthodes approch6es.

VI.6. G6n6ralisation aux fonctions de type 2. Cas des fonctions de type 3.

Uue fonction (I)u de type 2 peut 6tre consid6rde comme l 'enveloppe infdrieure (l 'un nombre fini de fonctions de type 1: (I~u I , (1),~ 2 . . . . . (I)tt//

caract6risdes par les param~tres :

(8~u, y~) (8~ , ~u) ... (8~ ~u ~) .

On remarque alors que l 'on obt ient un probl~me dquivalent en rempla~ant l 'ar~te u par p ar~tes:

U 1, 112 , . . .~ H l)

de m6mes extrdmit6s et dont les fonctions de coflt seraient respect ivement q b~u , -.., (l)u p . La gdn6rali- sation de l 'a lgori thme (A 2) aux foncgions de type 2 est alors imm6diate (5 condi t ion de considdrer le graphe G comme un muttigraphe).

Consid6rons m a i n t e n a n t les probl~mes (P) avec fonctions de type 3. Une fonction (1)u de type 3 peut ~tre considdr6e comme l 'enveloppe infdrieure d 'une infinit6

de fonctions de type 1. D'apr~s ce qui pr@~de, le probl6me (P) serait alors 6quivalent h un probl~me

(P 1) sur un mult igraphe compor tan t un hombre infini d'ar~tes. Ceci montre bien la na ture extra- ordinairement combinaloire des probl~mes de ce type

et laisse supposer qu ' aucun algorithme ne permet t ra jamais de les r6soudre de fagon exacte, m6me pour des graphes G de petite taille (N ~ 10, M ~ 20).

Ceci montre, en revanche, tou t l ' int6rfit qu' i l peut

y avoir ~ ddvelopper de bonnes m6thodes approchdes.

C'est ce point que nous allons m a i n t e n a u t examiner.

VII. M~THODES APPBOCH~ES

L'idde de base, ddjh sugg6r6e par de nombreux auteurs [9, 25, 38, 39], consiste h par t i r d 'une solution initiale yo et h l 'amdliorer i t6ra t ivement en n'effec-

tuan t , ~ chaque ~tape, que des modifications locales

du graphe associ6 ~ la solution courante, telles q u e :

- - suppression d 'une ar~te,

- - addit ion d 'une ar~te,

- - 6change de deux ar~tes.

Dans [38], Zadeh donne un certain nombre de tests d6duits du thdor~me 5, permet t an t d'am61iorer localement une solution. Cependant, il ne pr6cise pas, lorsqu'il y a l e choix, dans quel ordre il faut supprimer, a jouter ou 6changer les ar~tes. D 'aut re part , il fait

l 'hypoth~se (malheureusement pas toujours v6rifi6e en pratique) que les fonctions qbu song de la forme:

(I),,(ru) = tu. +(Y~) ,

off lu est la longueur de l 'ar~te u et ~ une fonction (de type 1, 2, 3), ident ique pour toutes les ar~tes u e U.

Nous donnons ci-apr6s deux algorithmes, appli-

cables aux probl6mes (P), avec fonctions de types 1, 2 ou 3, qui ue supposent pas la d6rivabilit6 des fonctions (l)u. Pour le cas des fonctions de type 3, l 'expdrience montre qu' i l esg difficile de calculer rap idement la diff6rence de coflt r6sul tant de l'addilion d 'une ar~te ou de l'dchange de deux ar~tes. Aussi les algo-

ri thmes (A 3) et (A 4) proc~dent-ils par suppression d'ar~tes en ut i l i sant le thdor~me 6.

VII.1. Algorithme (A 3).

a) i t6ration t = 0.

Soit yo une solution de ddpart (vecteur uniroute) et soit QOj la chaine jo ignant xi "h xj sur laquelle s'6coule le riot ~ij duns eette solution.

b) A l ' i t6rat ion t, soit yt la solution courante.

Pour toutes les ar6tes v = (xi , xj) ~ supp (y t ) successivement :

�9 d6germiner la plus courte chaine Lv entre x/ et x 1 dans G--{v}, oh les ar6tes u ~ U - - { v } s o n t m u n i e s

des longueurs : (I)u(Ytu + Ytv) - - (I)u(Y~) , soit W(Lv) sa longueur.

�9 Calculer : 5(v) w(Lv) - - (I)v(Ytv) �9

e) D6terminer v v6r i f ian t :

A(v) Mix {A(u)} uEsupp(yt)

9/16 A ~ . TELECOMMUN'IC., 31, n ~ 3-4, 1[,176

8 6 M. MINOUX. -- MULTiFLOTS DE COUT MINIMAL AVEC FONCTIONS DE COUT CONCAVES

Si A(v)~> 0 FIN la solution yt est (localement) optimale, sinon :

d) d~finir yt+~ comme la solution (veeteur nni- route) dans laquelle chaque riot ~01j s'~coule sur la

chaine : ~t+ l t t

~ t + t t i~ = Oi~ @ Lv si veO~j, faire t = t + 1 et re tourner en b).

Remarque 1.

N' impor te quelle solution de d~part peut ~tre

utilis~e. Par exemple, si h chaque ar~te u ~ U on associe un nombre lu (longueur) :

(a) un routage aux plus courtes chaines sur G, ou un graphe part iel connexe de G.

(b) un routage sur l ' a rbre de longueur totale

minimale.

Remarque 2.

A l 'dtape b) de l 'a lgor i thme (A 3), on recherche bien la plus courte chaine entre x~ et xj sur le graphe G

tout entier (sauf l 'ar~te v). Par suite, la chaine Lv obtenne peut conteni r une ar~te u ~ supp (Yt). Duns

ce cas, il se produi t un ~change des ar~tes u et v.I1 peut m~me arriver que plusieurs ar~tes de Lv n 'appar - t i ennen t pas ~ supp (Yt). I1 est int~ressant de noter que l 'a lgor i thme (A 3) n ' exc lu t pas de telles possibi- litds. La m~me remarque s 'applique h l 'a lgori thme

(A 4). L '6tape b) de l 'a lgor i thme (A3) comporte la

recherche d 'une plus courte chaine entre x~ et x I dans G - - (v} mun i de longueurs toutes positives (el. l 'hypo-

th~se H 1 du w II-4). Pour cela, l 'a lgori thme de

Dijkstra [7] on une var iante [37] peut ~tre avan ta - geusement utilisC Le nombre de calculs n6cessaires croit comme N 2 (mais il peut ~tre bien inf6rieur lors-

qu 'on recherche un plus court chemin entre deux

nceuds x~ et xj dorm,s).

Si M ' = [supp (Y~ I e s t le hombre d'ar~tes duns la solution de d6part, le temps de calcul peut ~tre born6 ( h u n facteur pros) par une fonction en (M')2NL Cependant , en t e n a n t compte du fait que deux solutions cons6cutives sont toujours peu diff6rentes (leur composantes ne different que sur un cycle de G), on peut d iminuer consid6rablement le temps de calcul. Duns l 'a lgor i thme suivant , seulement un pet i t hombre de A(v) est recalculd h chaque it6ration.

VII.2. Algorithme (A 4).

a) I t6rat ion t = 0.

Soit y0 une solution de d6part (vecteur uniroute) et soit Q0y la ehaine sur laquelle s'6coule le riot q~ij darts cette solution.

b) Pour toutes les ar6tes v = (x , , x~) ~ supp (yo)

successivement :

�9 soit Lv la plus courte chaine entre xi et xj duns

G - - {v} lorsque les ar~tes u G U - - {v} sont munies des longueurs :

Cu(yO + VO) _ Ou(Y~

et soit W(Lv) sa l ongueu r ;

�9 calculer A ( v ) = w ( L v ) - (I)v(Yv~

c) A l ' i tdrat ion t, soit yt la solution courante.

Ddterminer v ~ supp (Yt) vdrifiant :

A ( v ) = Min {A(u)} uEsupp(yt)

s o i t : v = ( x i , x i) .

d) Soit Lv la plus courte chaine entre xi et xj clans

G--{v} lorsque les ar~tes u ~ U--{v} sont munies

des longueurs : yt o.( u + Vv) - o ~ ( v ~ )

et soit W(Lv) sa longueur.

�9 Si w(Lv) - - Ov(Ytv) > Min (h(u)} . uEsupp(yt)

u~=v

Alors : faire A(v )= W ( L v ) - Ov(Y t) et re tourner

en c). Sinon :

e) Si w(Lv)--(Pv(Ytv) /> 0 FIN = la solution yt est (localement) optimale. S inon :

f) Ddfinir yt+l comme la solution (vecteur uni-

route) dans laquelle chaque flot q0ti s'dcoule sur la

chaine : l Ot+l t ~ij = Qij s i v • Q~j,

r t ~ij = Qi] @ Lv si v ~ O~],

faire t = t + 1, A ( v ) = 0, et re tonrner en c).

In tu i t ivement , le principe de cet algori thme peut

s 'expliquer de la mani~re suivante. On commence par calculer, h par t i r de la solution

de ddpart yo, une premiere dvaluat ion A(v) de la

var iat ion de cofit consdcutive h la suppression d 'une ar~te v quelconque, et ceci pour routes les ar~tes v = 1 . . . . , M (dtape h). Le tab leau A(v) est ensuite progressivement modifi6 au cours des it6rations.

Pla~ons-nous h une i terat ion t queleonque apr~s qu ' un certain nombre d'ar~tes aient ~t~ dlimindes et certains A(u) ~ventuel lement modifids.

A c e stade, on envisage la suppression de l 'arSte v pour laquclle A(v) est minimal (dtape c). Gdn~ralement , A(v) n 'es t qu 'une approximat ion de la diffdrence de coflt A'(v) qui serait effectivement enre-

gistrde si on 61iminait ~ ce momen t l 'ar~te v de la solution courante. C'est pourquoi, avan t de supprimer l 'ar~te v, on calcule la diffdrence de cofit exacte.

A'(v) = w(Lv) - - (I)v(Ytv) (~tape d).

Par ailleurs, on recherche la deuxi~me ar~te dans

l 'ordre des A croissants, c'est-~-dire l 'ar~te v' telle

que : A ( v ' ) = Min (A(u)}.

u=/=v uEsupp(yt)

Alors, de deux choses l ' u n e :

�9 ou b i e n : A'(v) ~ A(v') et dans ce cas, l 'ar~te v

ANN. TI~LI~COMMUNIC., 31, n ~ 3-4, 1976 10/16

M. MINOUX. MULTIFLOTS DE GOUT MINIMAL AVEG FONGTIONS DE GOUT CONCAVES 8 7

sera effectivement supprim6e fa l ' i tdrat ion t, h condi- tion que A'(v) < 0. Apr6s la suppression de l 'ar~te v,

on pose: A ( v ) - 0. Ev idemment , l 'a lgori thme se ter- mine h ce niveau si 0 ~< A'(v) ,% A(v') ;

�9 ou b i e n : A ' ( v ) > A(v') et d i n s ce cas, il est

possible que la suppression de l 'ar~te v' procure un

gain sup6rieur. On ne supprime done pas l 'ar~te v

ce s t ade ; on se contente de reml)lacer l ' ancienne 6valuation A(v) par la nouvelle valeur plus exacte

A'(v) .

Pour cet algorithme, l 'exp6rience mont re que pour

ehaque ar4te v, A(v) est calcul6 en moyenue deux ou trois lois seulement et par suite la complexit6 du ealcul croit c o m m e : M ' N 2, off M'--= [supp (yo)[ est

le nombre d'ar~tes dans la solution de d6part ; d'ofi un gain tr6s appr6ciable par rappor t h l 'a lgori thme

(A 3). Enfin, on peut d6montrer que pour certaines classes

de probl6mes, l'algorithme (A 4) fournit exactement la m~me solution que (A 3). C'est le cas, en particulier, lorsque les fonctions q)u sont de type 1.

Remarque 1.

Les algorithmes (A 3) et (A 4) peuven t ~tre consi- d6r6s comme des m6thodes de cheminement pro- fondeur d'abord dmls l 'arbre de d6cision du chapitrc VI.

Remarque 2.

Lorsque V u la fonction de cofit (I)u sur l 'ar4te u est constante et 6gale h 3u > 0 (quelle que soit la quant i t6 de riot > 0 sur l 'ar~te u), il est facile de

voir que la solution optimale du probl6me (P) est

l'arbre minimal du graphe G re la t ivement aux longueurs 8u (u ff U). D i n s ce cas, les algorithmes (A 3) et (A 4) rev iennent h construire i t6ra t ivement un graphe partiel connexe de G en excluant , h chaque 6tape, Fare le plus long dont la suppression ne d6connecte pas le graphe : on reconnai t le deuxi6me algorithme de Kruskal [20, 28] qui donne bien la solution du probl6me de l 'arbre minimal .

VI I . 3 . Mise ~ jour des riots c u m u l 6 s ~ c h a q u e i t 6 r a t i o n .

D ins les deux algorithmes pr6c6dents, se pose le probl6me du stockage et de la mise h jour des rou- rages (e'est-h-dire des chaines Q~j) et des riots cumul6s Yt u sur les ar~tes.

Pour cela, nous remarquerons d 'abord qu ' un ensemble de riots (?l;" ayan t tous une origine commune,

peut ~tre consid6r6 comme un rot simple sur le graphe G. Par cons6quent, le mult ir iot sur G que

l 'on consid6re, peut se ddcomposer en N rots simples (au plus) que l 'on n o t e r a : 41, +2 . . . . . + ~N~, Ol~l le r i o t 4 {

regroupe l 'ensemble des riots (pij d 'origine xi et d 'extr6- mit6s xj, avec j > i. Ainsi, par convent ion, le riot q)ij f a r partie du riot ~i si i < j .

Orientons, ma in tenan t , le graphe G en choisissant une orientat ion arbitraire pour chaque ar4te u.

A tout ensemble de routages (ensemble de chaines Qij) pour les riots ~/;', on peut alors associer N vecteurs h M dimensions @, @ . . . . . ~x , Off q;~ ddsigne la valeur (algdbrique) du riot de type i sur l 'arc u.

La composante u du multif lot (riot cumuld sur l 'ar~te u) est a lors :

N

vu= :c G [ i=t

Supposons m a i n t e n a n t qu'fi l '6tape consid6r4e, l 'algo- r i thme d6cide de supprimer l 'ar~te v.

Soit F le cycle Lv U {v} et choisissons le sens de parcours sur ce cycle d6fini par l 'o r ienta t ion de l'are v. Soit y = (yu) le veeteur h M composantes tel q u e :

�9 yu = + 1 s i u ff F et si u est orient6 d in s le sens

du parcours du cycle (remarquer que yv = + 1) ;

�9 y u = - - I si u f f F et s i u est orient6 d i n s le

sens contraire du sens de parcours du cycle ;

�9 y u = 0 si uCP. Pour obtenir les nouveaux riots cumul6s ~ ' u :

(V u = 1 . . . . . M ) ,

on effectuera pour i = 1, ..., N les t r ans fo rmat ions :

On remarque en effet que les N riots simples d~ I

v6r i f ient : @ - - 0 et par suite sur l 'ar~te v: Yv 0.

Pour les autres ar@tes, u =/= v, les riots cumul6s seront donn6s p a r :

N

i=1

Ainsi, la raise h jour des riots ~i n6cessite seulement N]F I addit ions ; et le caicul de la nouvelle solution se fair en recalculant les riots cumul6s un iquemen t

sur les ar~tes du cycle P, ce qui r6clame h nouveau

NIP [ additions. Par ailleurs, le stockage de cette informat ion

n6cessite de g i rder en m6moire N vecteurs de dimen- sion M, soit un tableau N • M.

Pour les probl6mes de taille mod6r6e, ce tab leau peut tr6s bien tenir d in s la m6moire centrale du calculateur. Pour les tr6s gros probl6mes (N > 200,

M > 400), il faut utiliser une m6moire auxiliaire (disque h acc6s al6atoire par exemple), mais ceci n 'est pas g~nant, 6 t i n t donn6 que le nombre d'acc6s (lecture ou 4criture) pour une mise h jour compl6te est toujours tr6s r6duit.

VI I .4 . G6n6ral i sat ion a u x mul t i f l o t s m u l t i - d i m e n s i o n n e l s .

Les algorithmes (A 3) et (A 4) se gdndralisent au

cas (fr6queut en pratique) off le graphe G est parcouru par 1 multiflols simultands. On donne, par chaque

paire de nccuds (xi , xj) les q valeurs d 0. (1), diy (2) . . . . .

d 0. (q) des diff4rents riots ~ij (1) . . . . , ~ij (q) devan t circuler entre xi et x;- sur G. On suppose que tons ces riots e m p r u n t e n t la m~me chaine entre xi et x j .

Un routage permet alors de ddfinir, par chaque

! 1 / 1 6 ANN. TI~LI~COMMUNIC., 31, n ~ 3-4, 1976

88 M. MINOUX. MU1,TIFLOTS DE COUT MINIMAL AVE(: FONCTIONS DE COUT CONCAVES

ar8te u, les flux globaux relatifs aux riots 1, ..., q

passant sur l 'arfite u, soit Yu(1), Yu(2) . . . . . Yu(q).

La fonction de cofit associde est alors :

(I)u(Yu(1), Yu(2) . . . . . Yu(q))

ddpendant des q variables Yu(1) . . . . . Yu(q).

Si l 'on salt calculer rap idement (I)u(Yu(1) . . . . Yu(q))

pour tou t ensemble de q variables Yu(1) . . . . . Yu(q),

alors les algori thmes (A 3) et (A 4) pe rme t t en t de

d6finir de bonnes solutions approch6es. Lh encore, il

n ' es t pas ndcessaire de supposer que les fonctions qPu

sont diffdrentiables. Ceci s 'applique, en part iculier ,

aux probl6mes de mult if lots dynamiques de cofit

(actualis6) minimal lorsque les diffdrents riots ne

suivent pas une loi de croissance simple (exponen-

tielle, lin~aire) en fonction du temps (cf. w IX- l ) .

Le temps dtant discr6tisd, t = 1 ... T, on consid6re

un mult if lot par instant . Chaque composante Yu est

alors un vecteur h T dimensions.

V I I I . B ~ S U L T A T S D E C A L C U L

Afin de contr61er la validitd des a lgori thmes (A 3)

st (A 4), on a construi t une sdrie d 'exemples h par t i r

des quatre graphes de base de la figure 1 (off on a

indiqud les longueurs de rdfdrence lu des diffdrentes

arStes).

Chaque exemple est alors d6fini par les donn6es

suivantes :

a) un coefficient k (coefficient de correct ion des

longueurs) permet de calculer les longueurs lu de

chaque ar~te par la formule l u - part ie enti6re

[100 k + ( 1 - k) lu] off [u est la longueur de r~fd-

rence de l 'ar~te u (cf. Fig. 1) (k peut fitre ndgatif,

mais ne doit pas descendre en dessous d 'une certaine

valeur pour que l 'on ait lu >~ 0).

80 65

+o

135

a b

+/\

8O

C d

FIG. 1. - - Graphes de base utilis6s pour la construction des exemples (avec les lougueurs de r6f6rence des ar6tes).

a) graphe G 1 ; b) graphe G 2 ; c) graphe G 3 ; d) graphe G 4.

ANN. TELECOMMUNIC., 31, n ~ 3-4+ 1976 12/16

M. MINOUX. MUI/I'IFLOTS DE (3OUT MINIMAL AVE(3 FON(3TIONS DE (3OUT CONCAVES 89

b) o n a s s o c i e h c h a q u e s o m m e t xi ~ X n n

n o m b r e n(xi) ( a p p e l 6 poids d u s o m m e t xi) e t o n

d d f i n i t ( p o u r i < j ) les di~ p a r l a f o r m u l e :

d ~ = p a r t i e e n t i 6 r e [ K [ n ( x 0 n(x~)]~l(wi~) ~] ,

off ~ e t ~ s o n t ( t e u x c o e f f i c i e n t s ~ g a l e m e n t d o n n d s ,

wi j e s t l a p l u s c o u r t e c h a i n e e n t r c x i e t x j ( en f o n c -

t i o n d e s l o n g u e u r s lu) e t off K v 6 r i f i e :

K ~] Dz(xi) ~z(xj)]~/(wij) B -- 100 N ~. ij

i<]

Les caract6r is t iques des diff6rents exemples t rai tds s o n t r a s s e m b l 6 e s d a n s le tableau I.

Les fonctions de coflt sont lin6aires avec coflt fixe de l a f o r m e : Ou(Yu) - -1 ,~ (8 + Y.) ( p o u r Yu > O) (off 8 est le eofit fixe).

Les r6sul ta ts de calcul sont consign6s darts le tableau I I , o h o n a i n d i q u 6 , p o u r c i m q u e e x e m p l e :

- - l a v a l e u r d u co f i t f ixe ,

- - l a s o l u t i o n o p t i m a l e o b t e n u e p a r l ' a l g o r i t h m e

(A 2) e t le n o m b r e de n c e u d s de l ' a r b o r e s c e n c e ~3

e x p l o r d s ( c e t t e i n d i c a t i o n p e r m e t d ' a p p r 6 c i e r la diff i -

c u l t 6 d e c h a q u e p r o b l b m e ) .

- - les s o l u t i o n s o b t e n u e s p a r les a l g o r i t h m e s (A 3)

(A 4) ( la s o l u t i o n de d @ a r t u t i l i s 6 e c o r r e s p o n d h u n

u n i r o u t a g e a u x p l u s c o u r t e s c h a i n e s r e l a t i v e s a u x

l o n g u e u r s lu s u r le g r a p h e d e d 6 p a r t ) .

O n r e m a r q u e r a q u e les s o l u t i o n s f o u r n i e s p a r les

algor i thmes ( A 3 ) - ( A 4 ) sout souvent opt imales et qu'elles ne s '6car tent j amais beaucoup de l ' op t imal i t6 (1 h 2 %). Pour l ' exemple 35, les 6carts r e l a t ivement

TABLEAU I

Caractdristiqaes des diffdrents exemples dtudids

Graphe Poids E x e m p l e s de base k des diff6rents n(euds

(dans I 'ordre)

11 0 10, 5, 7, 8, 3

12 0 1, 9, 6, 4. 10 G 1

13 N = 5 _ _ 0 ' 5 2, 5, 10, 8, 1

14 0 , 5 1 , 9 6 , 4 , 1 0

15 1 10, 10, 10, 10, 10

21 0 5, 10, 2, 7, 8, 1

22 0 5, 3, 2, 9, 1, 10 (} 2

23 N = 6 0,4 5, 10, 2, 7, 8, 1

24 - 0,4 1, 5, 8, 2, 6, 4 1

25 1 1, 5, 8, 2, 6, 4 1

31 0 1, 2, 3, 4, 5, 6, 7 1

32 0 7, I, 6, 5, 4, 3, 2 1 G 3

33 N = 7 0 0 , 5 , 4, 8, 7. 6 , 3 1

34 1 1, 2, 2, 2, 2, 2, 2 0,5

35 1 O, 1, 1, 1, 1, 1, 1 1

41 0 5, 4, 8, 7, 3, 10, 1, 2 1

42 0 9, 5, 3, 2, 6, 1, 7, 10 1 G 4

43 N = 8 0,5 5, 4, 8, 7, 3, 10, 1 , 2 1

44 0.5 9, 5, 3, 2, 6, 1, 7, 10 1

45 0 2, 8, 7, 1, 6, 4, 3, 5 1

1 2

1 2

1 2 1 - 2 1 0 1 2

1 2

1 2 - - 2

1 2

2

2

1

0

2

2

2

2

- - 2

TABLEAU II

Comparaison des algorithmes (A 2), (A 3) el (A 4) sur un certain nombre d'exemples

(~ indique que la solution optima]e a 6t~ trouv6e)

Valeur N o m b r e i du Algo- de

Exemple cofit r i t h m e nceuds ( A 3 ) ( A 4 ) fixe (A 2) explords

10 207 505 20 ~ 11 I 50 232 970 79 ~

100 255 265 91 ~

3i) 242 330 35 ~ 12 50 252 655 59 ~

200 315 370 113 ~

50 319 676 61 ~ 13 100 358 610 126 ~

200 420 497 207 422 233 422 238

50 317 957 24 318 247 318 247 14 300 472 280 260 475 857 475 857

500 555 595 295 ~

200 450 000 321 ~ 15 250 500 000 436 ~

300 520 000 548 ~

50 542 120 110 543 350 543 350 21 200 667 190 354 ~

500 859 634 557 ~

50 472 835 77 ~ 22 100 517 743 168 524 385 524 385

200 588 324 261 598 874 598 874

50 531 914 54 ~ 23 200 654 885 256 658 626 658 626

500 828 678 357 ~

50 705 589 116 ~ 24 100 747 993 246 750 194 750 194

200 805 554 281 812 298 812 298

1 - - 1

200 611 200 465 617 400 617 400 25 500 805 900 667 818 000 818 000

000 ~ 055 900 1 003 1 058 300 058 300

50 336 182 39 338 011 338 011 31 500 521 679 181 ~

000 698 810 243 ~

50 334 284 37 334 885 334 885 32 200 412 093 201 413 479 413 479

500 509 764 193 ~

50 368 897 20 371 485 371 485 33 200 449 226 172 463 273 463 273

500 566 826 276 580 151 580 151

318 1 020 600 419 ~ 34 331 1 031000 419 1 036 200:1 036 200

000 ,1 438 200 562 ~ - - i

326 1 075 800 141 1 173 600 1 173 600 35 1 000 1 480 200, 141 1 5 7 8 0 0 0 1 5 7 8 0 0 0

2 608 2 445 0001 147 2 542 800/2 542 800

50 - - 7 6 3 0 8 9 i 7--------7 ~ ' 41 200 : 905 341 375 ~

1 000 1 463 505 1 225 ~

10 612 368 32 ~ 42 5 0 653 322 209 ~

100 696 542 431 701 222 701 222

100 892 905 194 893 616 893 616 43 200 1 001 997 583 1 007 288 1 007 288

500 1 278 525 1 891 1 283 816 1 283 816

50 771 839 136 773 343 773 343 44 100 828 989 362 829 396 829 396

200 923 638 716 931 672 931 672

50 1 173 693 109 ~ 45 200 1 314 413 500 1 323 515 1 323 515

500 1 545 147 1 045 1 558 537 1 558 537

13/16 A~-. T~I.~COMMCNlC., 31, n ~ 3-4, 1976

90 ~I. M I N O U X . M U L T I F L O T S D E C O U T M I N I M A L A V E C F O N C T I O N S D E C O U T C O N C A V E S

impor tan ts s 'expl iquent par le f a r que la matrice D

ne v6rifie pas l 'hypoth~se du paragraphe II-2. Enfin, pour ce qui est du temps de calcul, il est

intdressant de noter que l 'a lgori thme (A 4) autorise

le t r a i t ement de rdseaux de grande laille. Ainsi, dans certains probl6mes que nous avons rencontr6s (dtude de la s t ructure optimale $ long terme du r6seau tdld- phonique de Paris), le nombre de nceuds N dtait de

l 'ordre de 200 et le nombre d'ar~tes M de l 'ordre

de 400. Pour ces probl6mes, le temps de calcul restait

compris entre 3 et 5 minutes sur calculateur (*).

I X . C O N C L U S I O N : A P P L I C A T I O N S

IX.1 . P l a n i f i c a t i o n ~ l o n g t e r m e d ' u n r 6 s e a u t 6 1 6 p h o n i q u e .

Lorsqu 'un rdseau de tdldcommunications, devant

satisfaire une demande en trafic (centre ~ centre) croissante au cours du temps, arrive fi sa turat ion, la

question se pose de savoir off et quand r6aliser les

extensions n6cessaires. G6n6ralement, les services charg6s de l a g e s t i o n

du r6seau ne s ' int6ressent qu ' aux d6cisions fi prendre

dams le fu tur immddiat (court terme). Cependant, le choix de la meilleure polit ique

d 'extension ne peut se faire qu 'en consid6rant l '6vo- lu t ion du r6seau sur une p6riode de temps sufflsam- men t longue, au moins 6gale fi la dur6e moyenne de remplissage des infrastructures de t ransmission (8 h

10 ans). De sorte qu 'une solution satisfaisante du probl6me ~ court terme passe n6cessairement par la recherche d 'une polit ique optimale d ' invest issements

long terme (voir aussi [261). On se ram6ne h u u probl6me de type (P) en p renan t

des fonctions de coflt ~u(Yu) repr6sentant les coflts actualisds de d6veloppement de l 'art6re u sur la pdriode consid6rde (darts ce cas Yu ne repr6sente pas le flux total sur l'arfite u, mais la vitesse de croissance de ce flux). On donne dans [24] le principe de calcul des fonctions (Du et on mont re qu'elles satisfont bieu, les hypoth6ses H 2 et H 1 du paragraphe II.

Les mOthodes expos6es dams eet article, et en part i-

culier l 'a lgor i thme (A4) , pe rmet ten t de r6soudre efficacement ce p rob l~me. Par exemple, elles out

permis de d6finir (dans un certain nombre d 'hypo- th6ses de croissance plausibles) des structures optimales pour le r6seau t616phonique in te rurba in fran-

9ais, sur la p6riode 1975-1985. Dans [26] et [27], on mont re comment les r6sultats

obteuus h long terme peuven t ~tre utilis6s par la plauificatiou ~ court et fi moyen terme d ' un rdseau de t~ldcommunications.

(*) HB 6000.

IX .2 . P r o b l ~ m e s de t616d i s t r ibu t ion g u n e

s o u r c e .

Ce probl6me, que nous noterons (P 2), est un cas part icul ier du probl6me (P) dans lequel les diffdrents

riots devant circuler sur le graphe G ont tous une origine commune xio. Alors tous les 61dments de la matrice D = [dij] sont nuls, saul sur la ligne i o et

sur la colonne i 0. Il s 'agit doric d ' un riot simple et

non plus d ' un multiflot. Darts ce cas, le domaine d 'admissibil i td ~ (ensemble

de vecteurs D-admissibles) est encore un trongon

convexe de R M. On mont re en outre [5, 25] que si

yo est un point extrfime de 3 , alors que le support de yo consti tue un arbre (graphe partiel connexe

sans cycles) de G (c'est donc un vecteur uniroute). Lorsque les fonctions de cofit Ou(Yu) sont liudaires avec cofit fixe (type 1), on d6montre [23, 24] que tou t point extreme de ~ est un op t imum local du probl~me (P 2).

Dans [29], Rothfarb et Goldstein proposent pour rdsoudre (P 2) une mdthode, ddrivde de l 'a lgori thme

du simplex eu programmat ion lin6aire c o n t i n u e ; elle consiste h engendrer une suite de points extremes

adjacents de ~ (arbres adjacents) de cofits d6crois-

sants. On about i t alors h un op t imum local. Une mdthode voisine est exposde par Zadeh darts [38].

Remarquons ici que les algorithmes (A 3)-(A 4)

sont directement applicables h ce cas particulier. Le tableau I I I rassemble un certain nombre de rdsultats comparatifs obtenus sur des probl6mes de taille r6duite. On observe que sur t ous l e s exemples trait~s, la solution optimale est obtenue.

TABLEAU III Comparaison des algorilhmes (A 2), (A 3) el (A 4)

sur le pcoblgme de la tdlddistribution dt une source (~ indique que la solution optimale a dt6 trouv6e)

E x e m p l e no

1 N = 5 M = 10

2 N = 5 M = 10

3

N = 7

M = 14

4 N = 7 M = 14

Valeur du cofit fixe 8

100 200 500

50 100 200

50 100 200 300 500 100 200 300

Solution exacte

algorithme (A 2)

1 5 8 6 4 0 189 215 276 215

45 800 60 300 89 300

238 070 263 713 312 843 353 644 431 444 276 292 324 592 369 272

N o m b r e de noeuds explords

96 81 64 64 64 64

1 057 1 553 1 657 1 351

898 1 098 1 409 1 422

Algo- rithmes

(A 3) et (A 4)

-)(-

Les fonctions de cofit sont de type 1 de la forme: (~u(Y,u) = lu(8 + Yu) (pour Yu > O),

off 8 est le eoflt fixe (le m~me pour toutes les ar~tes u) et off lu est la longueur de l 'ar~te u.

ANN. TI~LECOMMUNIC., 31~ n ~ 3-4, 1976 14/16

M. MINOUX. -- MULTIFLOTS DE COUT MINIMAL AVEC FONCTIONS DE COUT CONCAVES 91

(Les exemples 1 et 2 correspondent aux exemples 11 et 12 du tableau I, le nceud 1 6taut pris comme n(eud

origine des riots.) Signalons que les diffdrentes mdthodes dvoqudes

ici peuvent ~tre utilis~es m~me dans le cas off les fonctions de coot ne sont pas concaves, par exemple

pour des fonctions en escalier. Cependant , dans ce cas, les rdsultats thdoriques qui ont 6td dtablis ne

s 'appl iquent plus (par exemple : le caract~re arbo-

rescent des solutions n 'es t plus garaati).

Le probl~me de la tdlddistr ibutiou fi une source a d ' impor tan tes applications, entre autre dans les domaine des rdseaux de tdld-informatique, de la d is t r ibut ion d'dnergie, etc.

I X . 3 . A u t r e s a p p l i c a t i o n s .

I1 existe enfin de nombreux probl/~mes prat iques

duns lesquels or~ recherche un mult if lot de coot minimal (ou un rdseau de coot minimal) , le coot dtant la somme de deux termes :

- - le premier, consti tu6 par des codts fixes (coOt de crdation d ' un arc ou d 'une ar~te inddpendamment

du riot sur cet arc ou sur cette ar~te) ;

- - l e second, constitu~ par des codls variables (coOt du passage d 'uue unit6 de flot sur l 'arc ou sur l'ar~te).

On t rouvera duns l 'art icle de Billheimer et Gray [4] une liste tr~s compl6te d'exemples de ce type, inc luant n o t a m m e n t :

- - les probl6mes d ' acheminement du courrier ;

- - les probl~mes de dis t r ibut ion de marchandises par camion, t rain, avion, etc. ;

les probl6mes d '@oulement de trafic de vdhicules (planification des extensions des r6seaux urbains) ;

- - planificat ion des rdseaux de t ranspor t (rontiers, ferroviaires, a6riens, etc.).

Manuscril refu le 19 novembre 1975.

BIBLIOGRAPItIE

[1] BALINSKY (M. L.). Fixed cost transportation problems (Probl6mes de transport avec coots fixes). Naval Res. Log. Quarterly, U. S. A. (1961), 8, pp. r

[2] BERGE ((].). Th6orie des graphes et ses applications. Dunod, Paris (1958), 275 p.

[3] BEaGF. (C.). Graphes et hypergraphes. Dunod, Paris (1970), 502 p.

[5~] BILLItEIMER (J. W.) , GRAY (P.). N e t w o r k design w i t h fxed and variable cost elements (Synth~se des rdseaux avec coots fixes et coflts variables). Transportation science, U. S. A. (1973), 7, n ~ l, pp. ~9-7~.

[5] DANTZIG (G. B.). Linear programming and extensions (Programmation lin6aire et prolongements). Princeton Univ. Press, New York (1963), 632 p.

[6] DXNTZIG (G. B.). All shortest routes in a graph (Les plus courts chemins dans un graphe). Technical report n ~ 66-3. Stan]ord Univ., Calif. (1966), 6~ p.

[7] DIJKSTRA (E. W.) . A note on two problems in con- nexion with graphs. Numerische Mathematik, Dtsch. (1959), 1, pp. 269-271.

[8] ELHS (L. W.). La lot des volumes 6conomiques appliqude aux T61dcommunications. Bey. TdIdcom., Fr. (1975), 1, n ~ 50, pp. a-20.

[9] FRANK (H.), FRISCH ([. T.). The design of large scale networks (Synth6se des grands r6seaux). Proc. I.E.E.E., U.S .A . (1972), 60, n ~ 1, pp. 6-11.

I t0 ] FLOYD (R. W.) . Algorithm 97 : Shortest path (Algo- rithme 97 : plus court chemin). Communic. ACM, U.S.A. (1962), 5, n ~ 6, p. 3~5.

[It] FORD (L. R.), FULKERSON (D. R.). Flows in networks (Flots dans les rdseaux). Princeton, New Jersey (1962), 19~ p.

[12] GRASSIN (J.), MINOUX (M.). Variations sur un algorithme de Dantzig. Application ~t la recherche de plus courts chemins duns les grands r6seaux. Rev. #., Automat., In]ormat., Reeh. opdrat. (mars 1973), 7, n ~ V-I, pp. 53-62.

[13] GRAY (P.). Exact solution of the fixed charge transportation problem (Solution exacte du probl6me de transport /~ charge fixe). Oper. Res., U. S. A. (1971), 19, n ~ 6, pp. I 529-1 538.

[t~] tlADLEY (G.). Nonlinear and dynamic programming (Programmation non lin6aire et dynamique). Addison- Wesley, Reading, Mass., U. S. A. (1970), ~8~ p.

[15] HERV~ (P.). Rdsolution des programmes lindaires /~ variables mixtes par la proc6dure S.E.P., Metra, Fr. (1967), 6, n ~ 1, pp. 77-91.

[16] HI: (T. C.). Integer programming and networks flows (Programmation en nombres entiers et flots dans les rdseaux). Addison-Wesley, Reading, Mass., U. S. A. (1969), ~52 p.

[t7] ttUAaD (P.). Tour d'horizon en programmation non lin6aire. Bull. Direct. El. et Bech., Electr. de Fr., (1971), sdrie C, n ~ 1, pp. 35-70.

[t8] KENNINGTON (J. L.), UNGER (V. E.). The group theoretic structure in the fixed charge transportation problem (Structure de groupe du probl6me de transport h charge fixe). Operat. Res., U. S. A. (1973), 21, n ~ 5, pp. I 192-1 153.

[19] KLEINROCK (L.), FRATTA (L.), GERLA (M.). The flow- deviation method : a new approach to the analysis and synthesis of store and forward communication networks design (La m6thode du (( riot ddvi6 )) : une nouvelle mani6re d'aborder l'analyse e t l a synth6se des rdseaux de transmission h enregistrement et retransmission). Networks, U. S. A. (1973), 3, n ~ 2, pp. 97-133.

[20] KRUSKAL (J. B.). On the shortest spanning subtree of a graph (Le sous-arbre maximal de longueur minimale d'un graphe). Proc. Am. Math. Soc., U. S. A. (1956), 71, pp. ~8-50.

[21] LAND (A. H.), Dole (A. G.). An automatic method for solving discrete programming problems (Une mdthode automatique pour rdsoudre les probl6mes de programmation discrete). Eeonometrica, U. S. A. (1960), 28, pp. ~97-520.

[22] LASDON (L.). Optimization theory for large systems (Th6orie de l'optimalisation des grands syst6mes). MacMillan, London (1970), 523 p.

[23] MALEK-ZAVAREI (M.), FR~CSH (I. T.). On the fixed cost flow problem (Sur le probl~me de riot h coot fixe). Intern. J. control., G.B. (1972), 16, n ~ 5, pp. 897-902.

[24] MINoux (M.). Optimisation et planification des r6seaux de Tdl6communications. Proceedings of the 7 th I.F.I.P. con]erence on optimization techniques, Nice (1975). Springer Verlag, Berlin (1976).

[25] MiNowx (M.). Recherche de la configuration optimale d'un rdseau de Tdldcommunications avec fonctions de coflt concaves. Ann. Tdldcommunic., Fr.

15/16 ANN. TI~L]:ICOMMUNIC., 31, n ~ 3-4, 1976

92 M. M I N O U X . -- M U L T I F L O T S D E COUT M I N I M A L A V E C F O N C T I O N S D E COUT C O N C A V E S

(jan.-f6v. i974), 29, n ~ 1-2, pp. 25-42; (mars-avril 1974), 29, n ~ 3-4, pp. 139-i71.

[26] MI•ovx (M.). Multiflots dynamiques de coot actualis6 minimal. Ann. Tdldcommunic., Fr. (1975), 30, n o 1-2, pp. 51-58.

[27] MI~oux (M.). Planification h court et fi moyen terme d'un r6seau de T616communications. Ann. Tdld- communic., Fr. (1974), 29, n o 11-12, pp. 509-536.

[28] ROSENSTIEnL (P.). L'arbre minimum d'un graphe, in Th6orie des graphes, Rome Icc, Dunod, Paris (1967), pp. 357-368.

[29] ROTHFARB (B . ) , CTOLDSTEIN (M.}. The one terminal telepak problem (Le probl~me de la tdlddistribution

une source). Operat. Bes., U . S . A . (1971), 19, pp. 156-169.

[30] SCOTT (A. J.). The optimal network problem : Some computationnal procedures. Transp. Res., U.S.A. (1969), 3, pp. 201-210.

[31] SIMONNAnD (M.). Programmation lin6aire. Dunod, Paris (1962), 420 p.

[32] STEINBEnG (D. I.). The fixed charge problem (Le probl~me avec charges fixes). Nay. Bes. Log. Quart., U . S . A . (1970), 17, pp. 217-236.

[33] TOMLIN (Z. A . ) . Minimum cost multicommodity network flows (Multiflots de coot minimal). Oper. Bes., U . S . A . (1966), 14, pp. 45-51.

[34] YAGED (B.). Long range planning for telecommunication networks (Planification it long terme des r6seaux de t6ldcommunication). Polytechnic Inst. Brooklyn (19?l), 147 p.

[35] YAGED (B . ) . Minimum cost routing for static network models (Routage h coot minimal pour mod61es de rdseaux statiques). Networks, U. S. A. (1971), 1, n ~ 2, pp. 139-171.

[36] YAGED (B.). Traffm flow information for minimum cost routing procedures (Informations sur les flux de trafic pour les procddures de routage ~t coot minimal). Automatica, G.B. (mars t969), 5, n ~ 2, pp. 167-173.

[37] YEN (J. Y.). F ind ing the lengths of all shortest paths in a N-node, non negative distance complete network (Recherche des longueurs de t o u s l e s plus courts chemins dans un r~seau complet a N nceuds). J . Assoc. Comput. Machin., U. S. A., 19, n ~ 3, pp, 423- 424.

[38] ZADEH (N.). On building minimum cost communication networks (Construction des r~seaux de communication de coot minimal). Networks, U. S. A. (1973), 3, n ~ 4, pp. 315-331.

[39] ZADEH (N.). On building minimum cost communication networks over time (Construction de r~seaux de communication de coot minimal au cours du temps). Networks, U. S. A. (1974), 4, n ~ 1, pp. 19-3~.

[40] ZANGWILL (W. I.). Non linear programming an unified approach (Programmation non lin~aire, une approche unifide). Prentice hall, New York (1969), 336 p.

[41] ZANGWILL (W. I.). Minimum concave cost flows in certain networks (Flots concaves de coot minimal dans certains r~seaux). Management Sci. (1968), 14, n ~ 7, pp. 429-~50.

ANN. T~L~eJOM~IUNIC., 31, n ~ 3-4, 1976 16/16

Documents

Multiflots de coût minimal avec fonctions de coût concaves