LES PROCEDURES ARBORESCENTES D'OPTIMISATION

Philippe Herv~ (1)

Traba]o presentado al H Coloquio Fran- co.EspaRol de [nvestigaci6n Operativa y IV Reuni6n National de In vestigaci6n Operativa

R6sum6.- Diverses procddures, telles que les mdthodes "branch and bound", SEP, programmation dynamique, etc. ont dtd proposdes dans les derni~res anndes. Ce sont des illustrations particuli~res d'une mdthode gdndrale pour trouver des solutions op timales ou sous-op timales clans des situations dont l'aspect discret ou combinatoire implique l'absence des propridtds usuelles de convexitd. Dans ces situations, les algorithmes classiques (o~ l'on construit une suite convergeant vers la solution cherchde) ne sont plus applicables. Une approche gdn~rale h ce

probldme est proposde dans cet article.

1. INTRODUCTION.

Dans beaucoup de probl~mes de Recherche Op6rationnelle dont

on a clairement d6fini l 'ensemble des contraintes, et, en cons6quence

l 'ensemble des solutions admissibles, on est amen6 fi d6terminer, en

utilisant au mieux les moyens de calcul dont on dispose, une solution qui poss+de certaines qualit6s qui la rendent pr6f6rable aux autres.

En g6n6ral, on recherche une solution ~ laquelle est associbe une

bonne valeur d 'une certaine fonct ion 6conomique, et qu 'on peut

n6anmoins obtenir en un temps de calcul acceptable. A d6faut de

connaftre une relation pr6cise entre les deux crit~res antagonistes: valeur

(1) Compagnie de Raffinage Shell-Berre, Paris.

69

de la fonction 6conomique et temps de calcul ndcessaire pour l 'obtention de cette solution, on est amend, dar,~ la plupart des m~thodes dites

"heuristiques", fi rechercher une solution dont on conna~'t une borne

supdrieure, fixde au ddpart, de la diffdrence entre sa valeur 6conomique

et celle d 'une solution optimale du probl+me.

Le probldme ~ rdsoudre s 'dnonce ainsi:

"Ayan t associ6 fi tout dldment x de l 'ensemble E des solutions une

valeur 6conomique scalaire f ( x ) , ddterminer une solution x0 e-minimale,

c'est-~-dire telle que:

V x ~ E : f ( x o ) <~ f ( x ) + e

e 6tan.t un seuil de prdcision positif ou nul donnd".

Les procddures arborescentes d 'opt imisat ion s 'appliquent fi une classe tr+s gdndrale de probldmes dans lesquels l 'aspect combinatoire

6carte toute possibilit6 d'utiliser un algorithme sdquentiel classique,

comme en programmation lindaire ou non lindaire continue par exemple,

c'est-fi-dire de construire une suite de solutions convergeant versla solution ddsirOe selon une certaine mdtrique. Les procddures arbores- centes consistent,grosso-modo,fi examiner tour/ l tour des sous-exemples deE de plus en plus restreints,jusqu'fi la mise en 6vidence d'une solution e-minimale dans l'un d'eux. Cela revient, en d'autres termes,/l accumuler pas fi pas une information globale mais partielle sur E, et /l s'arrfiter

quand on juge cette information suffisante.

Nous prdsentons ici une formalisation de l 'ensemble de ces procd- dures dont certaines sont connues sous des appellations vari~es: mdtho- des "branch and bound", procedures SEP, backtracking, programmation

dynamique, etc...

Aprds un expos6 axiomatique, nous illustrerons les principaux

concepts introduits par des exemples pris parmi des mdthodes connues.

70

2. CADRE FORMEL DE LA PROCEDURE

2.1. Graphe dans l 'ensemble des parties de E

On se donne un ensemble D, dit "espace des solutions", contenant

E, et une application mult ivoque F de l 'ensemble P ( D ) des parties de D

dans lui-m6me, satisfaisant aux condit ions suivantes: A A

1) FD, fermeture transitive (1) de D, est finie; posons PD = O.

2) Pour tout ~16ment X de B, on a l e s conditions:

F X r 1 6 2 I V Y ~ PX, V Z ~ I ' X . Y : # Z =~ Y C Z [1]

U Y = X [21 Y e F x

Appelons ~ la famille:

x ot et 3" l 'application multivoquc dans ~ d6finie par:

3"~ = { ~ r x }

Le graphe 7" = (&, 3') est un graphe orient6 sans circuits qui admet

E comme sommet source et les Sommets a x tels que Fig = r comme

sommets terminaux.

Dans la suite nous appellerons sommets (sous-entendu de T) les

61~ments de g.

REMARQUES: I1 peut arriver que certains sommets o x soient vides

alors que X ne l'est pas; de m6me on peut avoir a x = a t , alors que que X g : Y .

2.2. Informat ion en un sommet de T

A toute 6tape de la proc6dure, l ' information sur l 'ensemble des solutions contenues dans un sommet a se divise en deux types:

(1) Rappelons que la fermeture transitive I" d'une application muttivoque I" de D dans lui-m& me est: A

I ' D = D U I ' D U I ' 2 D U . . . U F n D U . . .

71

- l ' i n fo rma t ion certaine,

- l ' i n fo rma t ion suppl6mentaire .

C'est la premi6re que nous d6crirons dans ce paragraphe, la seconde

n '6 tan t pas formalis6e et d6pendan t la rgement du t y p e de probl6me

trait6.

2.2.1. Evalua t ion en un s o m m e t

A chaque dtape, fi chaque s o m m e t a est a t tach6 un scalaire v (a)

qui cons t i tue une 6valuation par ddfaut des valeurs 6conomiques des

solut ions minimales de o. Au d 6 b u t , q u a n d on ne sait r ien sur o, on pose:

v ( a ) = -

Si au contra i re , on apprend fi une cer ta ine 6tape que a est vide, on

pose:

v ( a ) = + oo

2.2.2. E x a m e n d 'un s o m m e t

L ' e x a m e n d 'un sommet est une p roc6dure qui p e rm e t d 'en am61io-

rer sa connaissance, c'est-~-dire, en t re autres , d ' au g m en te r l '6valuat ion

v (a ) de ce sommet . Cet examen dol t satisfaire la cond i t ion suivante [3]:

L ' e x a m e n d 'un sommet terminal de T fourn i t une solut ion mini-

male de ce sommet [et en consequence , une ~valuation v (a) sans dE;.faut

de ce sommet ] .

2.2.3. Eta ts d 'un s o m m e t

Out re l '6valuation v(a), l ' i n tb rma t ion cer ta ine en un so m m et est

cons t i tu6e par les valeurs des trois 6tats ~ deux valeurs possibles chacun,

d6finis c o m m e il suit:

Par conven t ion , on 6crira a ( L ) po u r indiquer que le so m m et a est

dans l '6tat L; on emploiera de plus, pour ddfinir un 6tat L l e s signes de

la logique des propos i t ions (0.

(1) , 4 = n~gat ion de A ; A A B = A e t B : A V B = A o u B.

72

a) ff~tat "marque'" (M)

Par d6f ini t ion on a o (M) si le s o m m e t o a ~t~ examin& A u t r e m e n t

dit, marquage et examen sont synonymes .

La t ransi t ion: o(M)-~ o(M) est irr6versible.

b) if.tat "suffisamment connu" (S)

A une cer ta ine ~tape, on a o (S) si, Xo ~tant la plus pe t i te so lu t ion

de E connue ~ cet te 6tape, on a:

f (xo) <<- v(o) + e

La valeur de f (Xo) ne p o u v a n t aller q u ' en d6croissant au cours de

la proc6dure , il en r6sulte que la t rans i t ion o (S) -* o (S) est irr6versible.

c) ~tat "fermi" (F)

Un s o m m e t o est ferm6 si t o u s l e s so m m et s de 3'0 sont marqu6s o u

suf f i samment connus

o(F) ~* V r ~ 3 " a r ( M V S )

On voit que la t rans i t ion �9 a ( F ) -~ o(F) est irr6versible.

2.3. Descr ip t ion et jus t i f i ca t ion de la p roc6dure

La proc6dure consiste ~ m a r q u e r t o u r ~ tour cer ta ins s o m m e t s de

T choisis c o m m e il suit.

A. A la premiere 6tape, m a r q u e r le s o m m e t E.

B. A une 6tape que l conque :

1. Choisir un s o m m e t o tel que o(M A F).

2. Dans l 'ensemble 3,o, choisir un s o m m e t r tel que r (34 A S).

3. Marquer r.

4. D~duire de ce marquage les modi f i ca t ions 6ventuel les sur

l ' i n fo rmat ion en chacun des s o m m e t s de T

C. Arr~ter la p rocedure quand on ne peut plus le cont inuer .

73

Montrons que cette proc6dure conduit bien ~ la d6termination d 'une solution e-minimale. Pour cela, 6nonqons d 'abord trois propri6t6s des 6tats des sommets:

1 ~ 0 ( S ) o v r e "ro " r (S)

Cette propri6t6 est 6vidente.

2 o

[4]

o ( S ) ~* o ( F ) [51

En effet, d'apr~s [4]

a ( S ) ~ , V r e "ya : r ( S ) ~ ' V re ' , l "o : r ( M V S ) ~ a ( F )

3 ~ Si o x est un sommet terminal de T, c'est-~-dire, si I 'X = r alors

a ( M ) ~ o (S ) [6]

Ceci est une cons6quence de la condition [3] (cf. w 2.2.2.).

D6montrons maintenant la validit6 de la proc6dure:

a) La proc6dure est finie puisque l 'ensemble des sommets de Tes t

fini.

b) Quand la proc6dure est achev6e, tou t sommet marqu6 est ferm6. Supposons en effet qu'il existe encore un sommet ao(M V S-). Si on ne peut plus continuer la proc6dure c'est que t ous l e s sommets marqu6s

sont ferm6s. Donc on a ao(F), or:

oo(F) ~ V a l e T a o : a l ( M V S)

Oo(S) ~ 3 o l e ' ~ , a o " o~(S-)

et en vertu de [4]:

En conclusi6n:

o o ( M A - S ) ~ 3 o l e ~rao " o l ( M V SO

De proche en proche il existe dans T e n chemin orient6 partant de ao et dont tous les sommets sont dans l '6tat MA S, c~ qui est impossible puisque l'extr~mit~ de ce chemin, qui est un sommet terminal de T ne

74

peut ~tre M A S, en vertu de la propri6t6 [6].

Donc, quand la proc6dure est achev6e, tous les sommets marqu6s

de T sont dans l'6tat S, et en particulier le sommet initial E. Si xo est la

plus petite solution rencontr6e au cours de la proc6dure, il vient:

f ( x o ) <~ v ( E ) + e =* v x e E " f ( x o ) < f ( x ) + e

et xo est bien une solution e-minimale de E.

Si on n'a rencontr~ aucune solution au cours de la proc6dure, c'est

que E est vide.

MSF

. I / I MSF I i , / I I

', , / I I

' Z I I i ! I , ~F~S~"

MSF MSF

REMARQUE 1 : Cette

proc6dure est dire arbo-

rescente parce que, si

chaque 6tape on marque

l'arc de T reliant le som- met o (M A F ) au sommet

r (M A S) choisi, le sous- graphe partiel de Y ainsi

marqu6 est, h chaque 6ta-

pe, une arborescence de

racine E.

Fi~,~r~ 1 REMARQUE 2 �9 Si on repr6sente par les som-

mets d 'un cube les diff6rentes valeurs possibles de l'ensemble des trois

6tats d 'un sommet, on peut figurer par des fl~ches les transitions que

peuvent subir ces 6tats au cours de la proc6dure.

Sur la figure:

- - sont marquis d 'un point les seuls sommets du cube repr6sentant

des 6tats possibles, - les arcs en tiret repr6sentent les transitions qui ne peuvent exis

ter si le graphe Y est une arborescence.

75

3. DOMAINE D'APPLICATION ET ADAPTATION DE LA PROCEDURE.

Il est difficile de cerner de fa~on exhaustive l'ensemble des pro-

blames concern6s par cette proc6dure. Citons cependant:

- les probl~mes de recouvrement minimum sur un graphe, - les recherches d'ensembles int6rieurement stables maximaux et

ext6rieurement stables minimaux,

- les probl~mes du type "voyageur de commerce", et plus g6n~ra-

lement les probi~mes de tourn~es.

- les probl6mes d 'ordonnancement ~ contraintes disjonctives,

- les programmes lin6aires en variables enti6res ou mixtes,

- les probl6mes de programmation dynamique.

Dans le cadre de la proc6dure d6crite plus haut, il existe une grande

marge de libert6 pour d6finir avec pr6cision une m6thode de r6solution,

selon le probl6me h r6soudre et les moyens de calcul dont on dispose.

Cette libert6 porte sur:

- le choix de l'ensemble D et de l 'application F,

- le mode d'examen des sommets de T,

- le choix, ~ chaque 6tape, d 'un sommet a (M A if'), - le choix, ~ chaque 6tape, d 'un sommet r (34 A S)

Examinons tour ~ tour quelques-uns de ces points.

3.1. E n s e m b l e D et a p p l i c a t i o n F

Dans la plupart des m6thodes, D est un espace dans lequel on peut

ais6ment rep6rer les 61dments, sans r6p6tition ni omission, fi l'aide de

param~tres ind6pendants.

EXEMPLE : Dans le probl6me du voyageur de commerce, on cherche,

sur un graphe non orient6 fi ar~tes valu6es dans R u n circuit de longueur

minimale dans l'ensemble E des circuits, passant une lois et une seule

par tout sommet. Si le graphe poss~de n sommet, on peut plonger E

dans l'espace D des ensembles de n ar6tes distinctes du graphe.

EXEMPLE :Dans le programme lin6aire ~ variables enti~res bivalentes:

min { C x / x ~ E I

76

E = { x / . 4 x > ~ b . x j = O o u l V i e J}

on peu t plonger E dans l ' e n s e m b l e D des s o m m e t s de l ' h y p e r c u b e unit6

de d imens ion t J I.

D={x/x/= Oou 1, V/E J}

Darts le p lupar t des mEthodes , un c l emen t X de O est une par t ie

de D dEfinie en f ixant les va leurs de cer ta ins pa ram~t res repErant les

Elements de D. ou bien en res t re ignan t le d o m a i n e de var ia t ion de cer-

tains de ces parambtres .

EXl-:MI'H : l ) an s la mOthode de Dakin 15] pour rEsoudre les pro-

g r a m m e s linEaires a var iables mix tes :

E = ', ( x . . v ) /Ax + B.v = c: x >1 O: 0 <~ y < L, y a des c o m p o s a n t e s entieres}

Dans ce cas:

D = (x. y ) / x >1 O: 0 <~ 3" <~ L: v a des c o m p o s a n t e s enti~res}

Un Eldment X de O est ddfini par la donn~e de deux v e c t e u r s a et

b. ~i c o m p o s a n t e s entiEres et indicEes sur le m e m e ensemble que y. et

tels que a ~< b.

Par def in i t ion on a:

X ( a . b ) = { ( x , y ) / x > l O : a<~ y < ~ b ; v a d e s c o m p o s a n t e s e n t i ~ r e s }

L ' app l i ca t ion I 'X ta . b) est une d i c h o t o m i e de X(a . b ) o b t e n u e de

la fas suivante:

-- On choisit selon un cer ta in procEdE lie au rEsultat de l ' e x a m e n

de X(a . b) un indi te j* d 'une c o m p o s a n t e de v e t deux ent iers consecu-

tifs a et /3 tels que:

- Soit alors a ' le vec teu r o b t e n u en subs t i t uan t ~ a ~ , d a n s a et b '

le vec t eu r o b t e n u en subs t i t uan t c~ & bi,, dans b.

Par def ini t ion:

77

['X(a, b)= {X(a' , b), X(a , b')}

3.2. Examen des sommets de T

A chaque sommet a de T est associ4 le probl6me: trouver un 416-

ment minimal de o, au sens de la fonction 6conomique f A dTfaut de rTsoudre ce probl6me, on le remplace par un probl6me moins contraint.

Plus prTcis4ment, on plonge a dans un ensemble a ' plus g4n4ral dans

lequel on sait dTterminer directement par un algorithme efficace, un 416ment minimal dont la valeur va donc constituer une 6valuation par

dbfaut des solution de a.

Parfois, fi d~faut de savoir d4terminer une solution minimale de o'

on sait prouver si a' est vide ou non.

EXEMPLE: Recherche d'une 4valuation par d4faut. Dans les m4tho-

des "branch and bound" pour r4soudre les programmes lin4aires en

variables bivalentes, on plonge les ensembles a qui sont du type:

o = { x / A x < b;

dans l 'ensemble plus g4n4ral:

a = { x / A x < b;

;,'/= 0 ou 1 V j E J }

O < x/ K l V I E J}

La d4termination d'un 414ment minimal de a' revient alors fi r4sou-

dre un programme lin4aire classique.

EXEMPLE: Crit6re de vacuite d 'un sommet o. Dans la m4thode de

Balas [ 1 ] pour r4soudre les m6mes probl6mes que dans l 'exemple pr4c4-

dent, une s6rie de tests logiques sur les coefficients du tableau des

donn4es fournissent des conditions suffisantes de vacuit4 de chaque

sommet.

3.3. Choix, fi chaque 6tape, d 'un sommet a (34 A F')

Parmi toutes les r6gles possibles de choix du sommet a(MAT') on

peut en dTgager deux principales:

1) Rbgle LIFO (Last in first out).

Elle consiste fi prendre pour sommet a (M A F) le sommet non

78

ferm6 le plus r6cemment marqu6.

L 'appl ica t ion de ce t te r~gle rev ient ~ marque r des chemins de T

jusqu 'a r e ncon t r e r un arr6t, c 'est-h-dire jusqu '~ ce que .le dernier s o m m e t

a t te in t devienne ferm6 apr~s son marquage . On r e m o n t e alors le chemin

en sens inverses jusqu'~ r e n c o n t r e r de nouveau un sommet non ferm6.

On repar t de ce dernier s o m m e t pou r d6crire un nouveau chemin (ce t t e

p roc6dure s 'appelle aussi " b a c k t r a c k i n g " )

Cet te r+gle se justifie quand il est pa r t i cu l i6 rement facile d ' enchafner

l ' examen d 'un sommet a avec celui de l 'un de ses suivants r ~ 3' a.

EXEMPLE: Voir la md thode de Balas [1 ].

2) Rkgle du sommet d'~valuation minimale.

Elle consiste a choisir s y s t 6 m a t i q u e m e n t parmi les so m m et s

o (M A F) l 'un de ceux qui poss6de l '4valuat ion la plus faible.

Quand l '6valuation en cbaque s o m m e t est de bonne qualit4, on

peut en effe t penser que la r6gle ci-dessus est celle qui condu i t proba-

b l emen t au plus vite vers la so lu t ion cherchOe.

Des exp6riences effectuOes par l ' au t eu r sur des programmes lindai-

res mix tes ont montr6 cependan t que ce t te idOe a priori est souvent

erronOe.

3.4. Choix du sommet r(~l A S) ~ m a r q u e r

Ici on peut dist inguer aussi deux faqons de proc6der . La premiere

faqon consiste, une fois choisi le s o m m e t o (M A F), a examiner t o u r

tou r t o u s l e s sommets r ~ 7o. Dans le cas oth 7 est une a rborescence ,

ce t te p rocddure poss~de un avantage consid6rable p o u r la mise en oeuvre

sur calculateur , car les seuls s o m m e t s marqu6s non fermdes sont alors

un sous-ensemble de l ' ensemble des po in ts pendan t s de la sous-arbo-

rescence marquee. En cons6quence , pour re teni r en m6moire ce t te

sous-arborescence, il suffit de conse rve r s implement la liste de ses

sommet s pendants .

La deuxi~me faqon de p rocdder cons is te ,au contra i re , "a ne m arq u e r

la fois q u ' u n seul sommet r E " / o (nous en verrons plus loin un exemple

avec la m 6 t h o d e de Land et Doig).

79

Procddure SEP [3].

Cette proc6dure, formalis6e par MM. Roy, Bertier et Nghiem, peut se d6finir ainsi:

C'est l 'utilisation simultan6e de la r6gle du sommet d'6valuation minimale et de la premiere faqon de proc6der d6crite dans ce paragraphe.

4. UN EXEMPLE D'APPLICATION DE LA PROCEDURE: LA METHODE DE

LAND ET DOIG [8]

Nous avons choisi cet exemple parce qu'il i11ustre tous les concepts

introduits dans ce papier. C'est une m6thode pour r6soudre les pro-

grammes lin6aires mixtes.

min Iax + by/(x , y) ~ E}

avec:

E = { ( x , y ) / O < x < < . L ; y ~ O ;

1) Ensemble D �9

D = {(x, y)/O <~ x <<. L " y >>. O,

A x + B y = c xj entier V j E J}

x a des composantes enti~res}

2) Ensemble O: l~tant donn6:

- un sous-ensemble K c J, - un vecteur 2K indic6 sur K et ~ composantes enti6res, telles que:

0 <~ 2j <~ Lj , V j ~ K .

On leur associe le sous-ensemble de D:

O (~X) = { (x, y) /x , y) E D ; XK = XK }

I1 lui correspond, dans g , l 'ensemble:

E (2 K) = D (~K) n E

3) Examen d'un sommet E (~K)

A c e sommet on associe une premi6re 6valuation, par d6faut V(Y K) obtenue en plongeant E (2g) dans:

80

E ' ( ~ K ) = { ( X , Y ) / Y > ~ O O<~x<.L A x + B y = c ; XK=YK}

La d6termination d'un 616ment minimal (~, ~?)XK de EI(YK ) s 'obtient

par simple r6solution d'un programme lin6aire.

4) Application ~[

En un sommet E(Y K) de /" deux cas peuvent se pr6senter:

- ou bien (~, ~?)XK a toutes les composantes de ~ enti+res, darts ce cas E(XK), apr~s examen, est dans l '6tat S e t on pose:

~[EC~K) = q~

-- ou bien il existe au moins une composante ~r de (~, rl)xK qui

n'est pas enti6re, et on pose alors:

7E(~ K) = { E(Y K , ~a) /Ya = O, 1, 2 ..... Lu}

Propri~t& fondamentale des &valuations V(Y K)

Pour des raisons de convexit6 6videntes, on voit que:

V(XK)<" V(XK'[~a] + 1)<. V(Y K,[~a] + 2 ) < " - <. V(~ K,La)

et

V(YK) < V(Y K, [~a] < V(~ x , [~a] - 1) <.... <. V(Y K, O)

De cette propri6t6, il r6sulte que V(Y K, ~a)constitue une 6valuation

par d6faut des sommets E(~ K, Y'~) tels que:

et

5~ ~< 5a si x a < ~

~valuation que l'on peut donc connaftre, m6me si l 'on n'a pas marqu6 t

le sommet E (~ K, xa).

Cette remarque permet de modifier h chaque 6tape, apr~s un mar- quage,l '6valuation v(e) de tout sommet de T ~ l'aide de la r~gle suivante:

(1) [a ] signifie: partie enti~re par d~faut du norabre r#el a.

81

v ( o ) = min v(~-) r eTo

Choix d'un sommet a (M ^ F) fi chaque ktape

Parmi les sommets d '6valuat ion min imale on choisi t le s o m m e t le

plus r 6 c e m m e n t marqu6 (ceci cons t i tue une appl ica t ion en cascade de la

r~gle de l '6valuat ion minirnale et de la r~gle LIFO).

Choix d'un sommet r (M ^ S) fi chaque ktape

Soit o = E(YK) le s o m m e t que l 'on vient de choisir ; p o u r choisir 7-

on proc~de ainsi:

- si aucun sommet 7-~ 3,a n 'a enco re 6t6 marqu6, on choisi t p o u r 7-

l 'un des deux sommets :

E(~K, [~a ] ) ou E(Y K, [ ~ 1 + 1)

- si cer ta ins 616ments de 3,or on t d6j~ 6t6 marqu6, on choisi t pour 7-

celui des 616ments de 3'a non marqu6 et n o n su f f i samment connu d o n t

l ' examen va pe rme t t r e d ' a u g m e n t e r l '6valuat ion de u.

BIBLIOGRAPHIE

Nous citons ici quelques-uns parmi les nombreux articles en relation avec les

m6thodes arborescentes:

1. E. BALAS, 'rAn additive algorithm for solving linear programs, with zero one variables", Operations Research, vol. 13, n ~ 4, July-August 1965, pp. 517-546.

2. M.L . BALINSKI, "Integer Programming: Methods, Uses and computation", Management Sciences, vol. 12, 1965, pp. 253-313.

3. P. BERTIER et B. ROY, "Une procedure de r~solution pour une classe de probl~mes pouvant avoir un caract~re combinatoire", ICC Bulletin, vol. 4, 1965.

4. P. BERTIER, "Procedures pour ~laborer des tourn6es de distribution" (th~se), METRA, s6rie speciale n ~ 8, 1966.

5. R . J . DAKIN, "A tree search algorithm for mixed integer programming pro- .blems", Computer Journal, vol. 8, n ~ 3, October 1965, pp. 250-255.

6. F. GLOVER, "Truncared Enumeration Methods for solving pure and mixed integer linear programs". Working paper for limited distribution, operations Research Center, University of California, Berkeley.

82

7. P. HERVI~, "R6solution des programmes lin6aires ~t variables mixtes par la proc6dure SEP", METRA, vol. V1, n ~ 1, 1967, pp. 77-91.

8. A .H. LAND and A. G. DOIG, "An automatic method for solving discrete pro- gramming problems", Econometrica, vol. 28, 1960, pp. 497-520.

9. E . L . LAWLER and D. E. WOOD, "Branch and Bound Methods, A. Survey", Operations Research, vol. 14, n ~ 4, pp. 699-719.

10. B. ROY, P. BERTIER et P. T. NGHIEM, "Programmes lin6aires en hombres entiers et proc6dure SEP", METRA, vol. IV, n ~ 3, 1965.

83