RECHERCHE OPRATIONNELLE

MTHODES ARBORESCENTES

ALGORITHMES SEP ET SES BRANCH AND BOUND

I - INTRODUCTION

II MTHODES SEP ET SES

III - DEUX PROBLMES CLASSIQUES

(1) Voyageur de Commerce (2) Sac Dos

1

I INTRODUCTION A la diffrence des problmes danalyse, les problmes de Mathmatiques Discrtes, comme ceux abords dans ce cours, se mettent rarement en quations, il faut alors les rsoudre pas pas. Le plus souvent, sauf si un algorithme rapide de rsolution est connu, la seule manire de les rsoudre consiste construire tous les cas possibles - si on le peut et il en faut un nombre fini - et retenir ceux qui conviennent, jusqu obtenir une solution, si elle existe. La plupart des problmes abords ici sont des Problmes dOptimisation Combinatoire (POC) cest--dire pour lesquels il sagit de rechercher la valeur optimale dune fonction valeurs entires ou relles, dite fonction conomique ou fonction objectif ou objective (objective fonction, cost fonction), sur un ensemble fini de solutions possibles, dites solutions admissibles, et construire une solution optimale.

Ces problmes sexpriment de la faon suivante : Donne : S ensemble fini et f une fonction de S vers les entiers, ou les rels, associant tout lment de S une certaine valeur Question : On cherche

s0 S telle que

f (s0) = opt f (s) s S{ } o opt signifie Min ou Max Autrement dit on cherche dans un ensemble fini S, ensemble des Solutions Ralisables ou Admissibles, un lment s0 optimisant la fonction f.

Souvent il existe un ensemble fini E et une fonction c associant un cot (profit, distance, poids, capacit, ) tout lment e de E tels que : (1)

S P(E) (S = famille de parties de E), S = { s E s vrifie une certaine proprit }

(2)

f (s) = c(e)e s

s S

On parle alors de Problme dOptimisation Combinatoire Fonction Objective Spare. Un tel problme, comme on la dj dit, peut toujours tre rsolu par la Gnration Exhaustive ou Recherche Exhaustive ou algorithme naf (nave algorithm ou brute-force algorithm en anglais) cest--dire par la mthode consistant examiner tous les cas possibles.

Dans ce cas, cette mthode donne videmment toujours une solution optimale car il y a un nombre fini de cas examiner.

Rappelons que si E = {e1, e2, , eN} est un ensemble ayant N lments, on note P(E)

lensemble des parties de E et Pk(E) lensemble des parties de E ayant k lments, 0 k N, alors :

P (E ) = 2 N et Pk (E ) = CNk = Nk

=

N!k!(N k )! (N

k ) (coefficients binomiaux, combinaisons).

2

Le nombre de suites ordonnes de k lments de distincts de E (arrangements) est :

ANk = N.(N 1). ... .(N k + 1) = N!(N k )!

En particulier le nombre de permutations de E cest dire le nombre de bijections de E sur E est N ! Donc si E a N lments tout POC fonction objective spare peut tre rsolu en 2N tapes puisque toute solution admissible s est un sous ensemble de E il suffit en effet de gnrer chaque sous ensemble s de E, de tester si s vrifie la proprit voulue, de calculer son cot et de retenir un s0 qui ralise loptimum.

De faon plus prcise et pour mettre en vidence que toute recherche exhaustive, quelle quelle soit est de nature arborescente, on peut introduire les variables boolennes x1, x2, , xN respectivement associes chacun des lments, xi = 1 signifiant la slection de llment ei et xi = 0 son rejet, en notant E = {e1, e2, , eN} .

Il est alors facile dorganiser la recherche, cest--dire la gnration exhaustive de tous les sous ensembles de E, sous forme dune Arborescence Binaire o la racine (niveau 0) reprsente lensemble de toutes les solutions possibles, son fils gauche tous les sous ensembles contenant e1, donc pour lesquels x1 = 1, et son fils droit tous les sous ensembles ne contenant pas e1, donc o x1 = 0, et ainsi de suite de telle sorte que pour chaque niveau i chaque nud aura un fils gauche correspondant tous les sous ensembles (compatibles avec les choix dj faits) contenant ei, donc pour lesquels xi = 1, et un fils droit correspondant tous les sous ensembles compatibles ne contenant pas ei, donc o xi = 0, et ceci jusqu i = N.

On procde donc chaque tape par Sparation, dun ct xi = 1 et de lautre xi = 0, ce qui partage lensemble des cas en deux sous ensembles disjoints, ainsi chacune des 2N feuilles de cette arborescence correspond exactement un sous ensemble de E. On gnre ainsi 2N + 1 1 nuds, chaque nud, sauf les feuilles, correspondant une solution partielle dfinie par les valeurs des variables xi situes sur le chemin de la racine ce nud. Par exemple si E = {e1, e2, e3}, on a larborescence:

x1 = 1 x1 = 0 x2 = 1 x2 = 0 x2 = 1 x2 = 0

x3 = 1 x3 = 0 x3 = 1 x3 = 0 x3 = 1 x3 = 0 x3 = 1 x3 = 0

Les sous-ensembles correspondant aux feuilles de gauche droite sont respectivement {e1, e2, e3}, {e1, e2}, {e1, e3}, {e1}, {e2, e3}, {e2}, {e3} et .

3

Remarque Cette arborescence reprsente conceptuellement la mthode dcrite ci dessus pour gnrer systmatiquement tous les sous ensembles de E, est il ncessaire de la fabriquer effectivement ? Ici non, pourquoi ? Mais nous verrons dans la suite que pour les algorithmes SEP et SES il est fondamental de la construire mais pas ncessairement compltement, on ne stockera chaque tape que les informations utiles la poursuite de lexploration.

Dans la suite, voir III, nous examinerons en dtail deux problmes classiques dj

mentionns dans lintroduction au cours : le Problme du Voyageur de Commerce, PVC, the Traveling Salesman Problem en anglais, et le Problme du Sac Dos, SAD, the Knapsack Problem en anglais. Ces problmes qui sont des archtypes de problmes combinatoires NP Difficiles, cest--dire de problmes pour lesquels, en particulier et surtout, aucune mthode de rsolution efficace en temps nest connue.

Ils sont dfinis par : PVC Donnes : G = (X, U, d) un graphe orient valu o d attribue chaque arc u une valuation d(u) strictement positive (cot, distance, temps, capacit, ) Question : Dterminer un circuit hamiltonien de valuation minimale, cest--dire un circuit passant par chaque sommet du graphe une fois et une seule et qui est de valuation minimale, la valuation dun circuit tant gale la somme des valuations de ses arcs. SAD Donnes : On dispose de n objets, numrots de 1 n, dutilits et de volumes respectifs u1, u2, , un et v1, v2, , vn et dun sac dos de volume maximum V Questions : Comment remplir au mieux le sac ? Autrement dit quels objets doit-on prendre dans le sac pour en maximiser lutilit sans dpasser le volume V ?

Ces deux problmes sont des problmes doptimisation combinatoire fonction objective spare, pourquoi ? Pour PVC la mthode exhaustive ncessite de gnrer tous les circuits hamiltoniens du graphe, dans le cas o G est complet cest--dire lorsque G contient tous les arcs possibles, il y a (n 1) ! circuits possibles quand G a n sommets. Pour SAD, il faut tester tous les sous-ensembles dobjets, il y a donc ici 2n cas tester.

Nous voyons donc que cette faon de procder, mme si elle donne toujours une solution optimale, et cest le cas pour tous les problmes NP Difficiles, peut tre efficace sur des petits cas, cest--dire quand n est petit, mais savre vite irraliste, car trs coteuse en temps de calcul, lorsque n est de grande taille, elle est en effet exponentielle en la taille des donnes.

4

Par exemple, si nous appliquons la mthode exhaustive sur SAD lorsque n = 100, il y a 2100 cas examiner, supposons que nous ayons un ordinateur capable de traiter chaque cas en 10 - 9 s il faudra alors 2100.10 9 s pour rsoudre le problme soit au moins environ 3.1013 annes Combien faudra til de temps pour rsoudre PVC sur un graphe complet ayant 100 sommets ?

Cest pour cette raison que lon parle dExplosion Combinatoire.

Dautre part il nest pas toujours facile de mettre en uvre une telle mthode, le problme rside bien sr dans lalgorithme utilis pour la gnration. On peut bien sr sinspirer de la formulation prcdente qui utilise des variables boolennes, mais il nest pas vident a priori dobtenir par exemple : - toutes les permutations dun ensemble de N lments - tous les circuits hamiltoniens dun graphe orient ? ou mme tout simplement tester si

un graphe orient est hamiltonien - tous les stables dun graphe - toutes les colorations possibles dun graphe - tous les ordonnancements linaires possibles dun graphe sans circuit - tous les chemins dun sommet tous les autres dans un graphe -

La question fondamentale est donc dviter la recherche exhaustive et donc lexplosion combinatoire pour rsoudre ce type de problme alors que cest souvent la seule stratgie possible avec la Programmation Dynamique pour obtenir une solution optimale. Il ny a que deux rponses possibles cette question : - soit on refreine ses ambitions en se contentant de rechercher des solutions

approximatives en mettant au point des mthodes approximatives ou heuristiques cest--dire des algorithmes donnant rapidement une solution quon espre pas trop mauvaise mais sans aucune garantie doptimalit

- soit il faut mettre au point des mthodes arborescentes de rsolution bases sur la

recherche exhaustive cest--dire examinant lensemble de tous les cas possibles mais cette fois ci de faon implicite (on dit aussi par numration implicite) cest--dire sans les gnrer tous explicitement, le but tant bien sr dobtenir une solution optimale tout en amliorant nettement en moyenne les performances de la simple gnration exhaustive.

Ce sont ces dernires mthodes quon appelle Algorithmes de Rsolution par Sparation et Evaluation Progressive ou Squentielle suivant la stratgie dexploration choisie ou Algorithmes de Banch and Bound en anglais.

5

Insistons encore sur le fait que les POC sont en gnral dune part trs simple comprendre, voir PVC et SAD, et dautre part trs faciles rsoudre mathmatiquement , quoi de plus lmentaire en effet que de passer en revue toutes les solutions possibles, il y en a un nombre fini, et den extraire loptimum. Mais ce qui nous intresse ici et qui pose problme est le calcul effectif de loptimum et la construction dune solution optimale en temps raisonnable car il peut y avoir un trs grand nombre de cas examiner (explosion combinatoire), il faut donc mettre au point des mthodes rellement utilisables en pratique. Cest l un des dfis majeurs de la Recherche Oprationnelle et plus gnralement des Mathmatiques venir, voir en particulier le site www.claymath.org/millenium/ et le problme P vs NP . Quelques prcisions mmes trs informelles, voire simplistes, en tout cas retenir, peuvent clairer cette problmatique. La classe NP contient les problmes de dcision , cest--dire rponse oui ou non, pour lesquels on peut vrifier, en un temps polynomial, quune solution donne ou propose est rponse oui. tout POC on peut associer sa version naturelle de dcision, celle de PVC est : k-PVC Donnes : G = (X, U, d) un graphe orient valu o d attribue chaque arc u une valuation d(u) strictement positive (cot, distance, temps, capacit, ) et un entier k Question : Existe til dans G un circuit hamiltonien de valuation infrieure ou gale k ? k-PVC est dans NP car il est facile (polynomial) de tester si un circuit donn de G est hamiltonien et de valuation infrieure ou gale k crire la version de dcision de SAD. La classe NP contient des milliers de problmes dment rpertoris, mais, pour certains, aucun algorithme de rsolution en temps polynomial nest connu. P tant dfini comme tant la classe des problmes de dcision polynomiaux, on a P NP (pourquoi ?) et la question, toujours ouverte, est de savoir si cette inclusion est stricte ou si lon a P = NP. On dfinit la classe dquivalence des problmes NP Complets, NPC, comme tant les plus difficiles de NP dans le sens o toute mthode efficace de rsolution de lun deux permettrait de rsoudre efficacement tout problme de NP, par exemple k-PVC NPC. Ainsi lexistence dun algorithme polynomial pour k-PVC permettait de conclure que P = NP. Informellement, un problme NP Difficile est un problme au moins aussi difficile quun problme NP Complet. Les problmes de NPC sont donc aussi NP Difficiles. Mais il existe des problmes de dcision qui sont NP Difficiles sans tre dans NP. Retenons aussi que si le problme de dcision associ un POC est dans NPC alors il est lui-mme NP Difficile, cest le cas de PVC et de SAD.

6

II - ALGORITHMES DE RSOLUTION PAR SPARATION ET VALUATION PROGRESSIVE OU SQUENTIELLE On parle donc dAlgorithmes ou de Mthodes SEP ou SES ou encore Branch and Bound, BAB, en anglais. Cette stratgie de rsolution est fondamentalement base sur la recherche exhaustive car elle consiste parcourir implicitement et de faon arborescente lensemble des solutions possibles du problme, par sparation et en gnrant une solution partielle en chaque nud. Loriginalit de lapproche consiste tirer parti :

du calcul dune fonction chaque tape qui reprsentera une borne infrieure, en fait un minorant, pour un problme de minimisation ou un borne suprieure, en fait un majorant, pour un problme de maximisation. Cette valuation va permettre dune part dorienter la recherche et dautre part dliminer des recherches infructueuses

dun ordre de slection des variables, tout ordre convient mais certains peuvent

amliorer le calcul de la borne et la rapidit de la mthode

dune compatibilit des variables, le choix dune variable peut liminer ou au contraire impliquer dautres variables.

Pour un problme de Maximisation, il faut calculer un majorant, quon appellera Borne Suprieure par abus de langage et quon notera BS(x), en chaque sommet x de larborescence de lexploration de telle sorte que toutes les solutions de la sous arborescence correspondante, A(x), aient une valeur au plus gale BS(x), si BS(x) est infrieure un maximum dj trouv alors il est inutile dexplorer A(x). Pour un problme de Minimisation, il faut calculer un minorant, quon appellera Borne Infrieure et quon notera BI(x), en chaque sommet x de larborescence de lexploration de telle sorte que toutes les solutions de la sous arborescence correspondante, A(x), aient une valeur au moins gale BI(x), si BI(x) est suprieure un minimum dj trouv alors il est inutile dexplorer A(x). Si r est la racine de larborescence de recherche on a le schma suivant : r x A(x) s

7

Par construction, pour toute solution s obtenue partir de x, on a f(s) BS(x) dans le cas dun problme de Maximisation ou f(s) BI(x) dans le cas dun problme de Minimisation, donc si on connat dj une solution s0 telle que BS(x) f(s0) ou BI(x) f(s0), alors on peut laguer A(x) cest dire faire lconomie de lexploration de A(x) et ainsi acclrer la recherche. Cette conomie sera dautant plus importante que la borne sera plus pertinente. Suivant la stratgie dexploration de larborescence, soit en Profondeur soit en Largeur, il y a deux mthodes possibles, SES ou SEP. Initialement, pour les deux mthodes, on trie ventuellement les variables et lon calcule la borne du nud initial, la racine de larborescence, qui reprsente potentiellement toutes les solutions possibles car aucun choix na encore t fait. Dans la procdure SES on sloigne de la racine tant que cela est possible en crant des branches de plus en plus longues et en nexaminant quune seule branche la fois, cela correspond exactement un parcours en profondeur de larborescence partir de la racine. Plus prcisment, en chaque nouveau sommet x, il y a quatre cas : - soit x ne peut pas tre prolong en une solution du problme - soit x correspond une solution du problme, x est une feuille terminale de

larborescence, alors, si ncessaire, on mmorise cette solution ainsi que sa valeur - soit lvaluation de x permet de llaguer

- sinon, on continue rcursivement lexploration avec le fils gauche de x en affectant la

valeur 1 la variable suivante (tape de sparation).

Dans les trois premiers cas, on remonte au pre de x la recherche dun autre fils examiner sil existe, sinon on remonte encore dun niveau et ainsi de suite

La mthode se termine lorsquon revient la racine et que ses fils ont t explors.

Au contraire, chaque tape, la mthode SEP considre, parmi toutes les feuilles de larborescence en cours de construction, la feuille x ayant la meilleure valuation, cest--dire o la borne, BS(x) ou BI(x), est la meilleure, soit la plus grande pour un problme de Maximisation soit la plus petite pour un problme de Minimisation. Le schma gnral de la mthode SEP consiste donc gnrer une arborescence partielle de recherche partir de la racine en choisissant chaque tape le nud le plus prometteur : - si la borne correspondante est moins bonne que celle de la meilleure solution trouve,

lalgorithme est termin

8

- sinon, on effectue une phase de sparation : on donne deux fils au nud courant en affectant la valeur 1 puis la valeur 0 la variable suivante, on dtermine les compatibilits et lon calcule les bornes des deux fils ainsi obtenus, cest lvaluation.

Les stratgies sous-jacentes ces deux techniques dexploration de larborescence sont le Parcours en Profondeur, pour SES, et le Parcours en Largeur, pour SEP, celui-ci tant guid par la fonction dvaluation. En effet, la premire va dabord au plus profond dans larborescence, cest--dire verticalement , tandis que lautre lexplore plutt latralement, cest--dire horizontalement . Notons que la mthode SES peut scrire rcursivement, une criture itrative est possible mais ncessite de stocker dans une pile le chemin qui va de la racine au sommet courant, alors que la mthode SEP implique de garder dans une liste toutes les feuilles encore actives de larborescence en construction.

Pour conclure sur ces mthodes, quelques remarques :

simplicit de conception (essai potentiel de tous les cas possibles) mais mise en

uvre parfois difficile en ce qui concerne la gnration effective de tous les cas et surtout le choix de la fonction permettant de calculer un borne

permet toujours dobtenir une solution optimale, car on examine implicitement

lensemble fini de tous les cas possibles, mais au dpend du temps de calcul voire de lespace mmoire

cest une des seules approches connue, avec la Programmation Dynamique, pour

rsoudre exactement les problmes NP-Difficiles pour lesquels aucune autre stratgie est connue pour obtenir, plus efficacement, une solution optimale

en gnral en Temps Exponentiel dans le plus mauvais cas pour le problmes NP-

Difficiles. La difficult essentielle pour ces mthodes consiste donc trouver un bon compromis local-global cest--dire entre le temps global de calcul dune solution optimale et le temps local de calcul de la fonction dvaluation permettant dacclrer la recherche : plus la fonction sera labore plus elle laguera larbre mais plus elle sera longue calculer Remarquons quil est possible damliorer la mthode par dautres techniques, citons par exemple le principe de slection et limination a priori qui utilise la notion de regret.

9

III DEUX PROBLMES CLASSIQUES

(1) Problme du Voyageur de Commerce (PVC)

Rappelons que le trs classique Problme du Voyageur de Commerce, dans toute sa gnralit, est dfini de la faon suivante : Donnes : G = (X, U, d) un graphe simple orient muni dune valuation d strictement positive (cot, distance, temps, ) Question : Dterminer un circuit hamiltonien de valuation minimale

Traditionnellement un voyageur de commerce partant dune ville doit visiter toutes les

autres villes et revenir son point de dpart tout en minimisant la longueur de son parcours.

On montre que ce problme est NP Difficile, notons aussi que le simple

problme de tester lexistence dun circuit (ou dun cycle dans le cas non orient) hamiltonien est NP Complet.

Lorsque G est non orient et si d vrifie lingalit triangulaire on parle de PVC euclidien, - PVC, cest la cas par exemple lorsque les n sommets du graphe sont des points du plan et d la distance usuelle (distance euclidienne), G est le graphe complet induit par ces points, il y a alors 1/2 . (n 1) ! cycles hamiltoniens possibles. Nous nous proposons ici de rsoudre le PVC par la mthode SEP et de la mettre en uvre sur lexemple suivant o G est dfini par la matrice dadjacence :

A B C D E F A 0 16 10 19 21 18 B 16 0 20 22 C 10 20 0 17 27 25 D 19 17 0 14 15 E 21 27 14 0 12 F 18 22 25 15 12 0

Ici le graphe est non orient car la matrice est symtrique, il peut tre reprsent dans le plan par : C B D A F E

10

On cherche un cycle hamiltonien de longueur minimale, la fonction optimiser est donc trivialement la somme des longueurs des artes. A chaque arte ij on associe la variable boolenne xij valant 1 si ij est slectionne et 0 sinon. La borne infrieure choisie sera tout simplement la somme des longueurs des n plus petites artes possibles car tout cycle hamiltonien doit contenir exactement n artes. Il est naturel de considrer les artes par ordre de longueur croissante car cest un problme de minimisation, ici nous avons : AC = 10, EF = 12, DE = 14, DF = 15, AB = 16, CD = 17, AF = 18, AD = 19, BC = 20, AE = 21, BF = 22, CF = 25 et CE = 27. Enfin les contraintes de compatibilit sont les suivantes : tout sommet ne peut apparatre dans plus de deux artes et il ne faut pas gnrer de sous cycles, le test de compatibilit ne se fera que par rapport aux artes dj slectionnes. La mthode SEP choisie donne larborescence suivante o les sommets sont numrots dans lordre de leurs crations : 1 2 3 4 5 6 7 14 15 8 9 10 11 16 17 20 21 18 19 12 13 Examinons chacune des tapes de la construction : - nud 1 : BI(1) = 84 avec les artes AC, EF, DE, DF, AB, CD

- nud 2 : AC est slectionne, BI(2) = 84, avec les mmes artes quau nud 1

- nud 3 : AC est rejete, BI(3) = 92 avec les artes EF, DE, DF, AB, CD, AF ; ltape

suivante explore le nud 2 - nud 4 : EF est slectionne, BI(4) = 84 car mmes artes quau nud 2

- nud 5 : EF est rejete, BI(5) = 90 avec les artes AC, DE, DF, AB, CD, AF ; ltape

suivante explore le nud 4 - nud 6 : DE est slectionne, BI(6) = 87 avec les artes AC, EF, DE, AB, CD, AF

car DF nest pas slectionnable cause du cycle DEF

11

- nud 7 : DE est rejete, BI(7) = 88 avec les artes AC, EF, DF, AB, CD, AF ; ltape suivante explore le nud 6

- nud 8 : AB est slectionne, BI(8) = 91 avec les artes AC, EF, DE, AB, CD, BF en

effet DF est exclue par les choix de EF et DE ; AF, AD et AE sont limines car A apparat dj deux fois et BC est exclue cause du cycle ABC

- nud 9 : AB est rejete, BI(9) = 90 avec les artes AC, EF, DE, CD, AF, AD en effet

DF a t limine au nud 6 ; ltape suivante explore le nud 7 - nud 10 : DF est slectionne, BI(10) = 89 avec les artes AC, EF, DF, AB, CD, AD

car la slection de DF entrane llimination de AF, F apparat en effet dj deux fois - nud 11 :DF est rejete, BI(11) = 92 avec les artes AC, EF, AB, CD, AF, AD ;

ltape suivante explore le nud 10 - nud 12 : AB est slectionne, BI(12) = 97 avec les artes AC, EF, DF, AB, CD, CE,

en effet AF a t limine au nud 10 et la slection de AB entrane llimination supplmentaire de AD et AE (car A apparat dj deux fois) et de BC (car cycle ABC), BF et CF sont exclues car F apparat dj deux fois

- nud 13 : AB est rejete, BI(13) = 93 avec les artes AC, EF, DF, CD, AD, BC car

AF a t exclue au nud 10 ; la recherche reprend au nud 5 (elle aurait pu reprendre au nud 9)

- nud 14 : DE est slectionn, BI(14) = 90 avec les artes AC, DE, DF, AB, CD, AF

- nud 15 : DE est rejete, BI(15) = 95 avec les artes AC, DF, AB, CD, AF, AD ;

ltape suivante explore le nud 14, on aurait pu prendre 9 - nud 16 : DF est slectionne, BI(16) = 93 avec les artes AC, DE, DF, AB, AF, BC

car les artes CD et AD sont exclues, D apparaissant dj deux fois - nud 17 : DF est rejete, BI(17) = 94 avec les artes AC, DE, AB, CD, AF, AD ; la

recherche continue au nud 9 - nud 18 : CD est slectionne partir du nud 9 avec AC, EF, DE et sans AB, les

artes DF, AE et CE sont exclues, la slection de CD limine de plus les artes AF, AD, BC et CF, il reste donc uniquement BF avec AC, EF, DE et CD, il ny a pas de solution, ce nud est donc sans descendance

- nud 19 : CD est rejete, IB(19) = 93 avec les artes AC, EF, DE, AF, AD, BC ;

ltape suivante explore le nud 8 - nud 20 : CD est slectionne, on obtient une solution de valeur 91 car les artes

slectionnes AC, EF, DE, AB, et CD forment une chane hamiltonienne et la seule arte possible est BF qui permet de former un cycle hamiltonien

12

- nud 21 : CD est rejete, BI(21) = 99 avec les artes AC, EF, DE, AB, BF, CF.

A cette tape nous avons une solution de valeur 91 avec le sommet n 20 de larborescence et les autres nuds restant explorer sont 3, 11, 12, 13, 15, 16, 17, 19 et 21 qui ont tous une borne infrieure au moins gale 92, lalgorithme sarrte donc car il est impossible dobtenir un meilleur cycle.

La solution optimale du problme est donc le cycle trouv au sommet n 20. Remarquons pour terminer quavec notre exemple qui a 13 artes la recherche exhaustive effectue stricto sensu nous aurait fait examiner les 213 cas, ce qui correspond gnrer 214 1 = 16 383 nuds, alors que larborescence obtenue par la mthode SEP choisie na que 21 nuds, cest donc une amlioration substantielle. Que donne la mthode SES dans notre cas ? Avec la mme borne infrieure, le mme ordre de slection des variables et les mmes rgles de compatibilit, nous obtenons globalement la mme arborescence dexploration. Cependant les sommets sont explors cette fois ci dans lordre 1, 2, 4, 6, 8, 20, 21, 9, 18, 19, 7, 10, 12, 13, 11, 5, 14, 16, 17, 15 et 3. Une premire solution est plus rapidement trouve, certes et il se trouve que cest la solution optimale, mais pour conclure, il faut ncessairement explorer le reste de larborescence pour se rendre compte que les autres sommets ne donneront pas de meilleure solution.

Nous venons de voir comment appliquer la mthode SEP, puis SES, sur le problme du Voyageur de Commerce en prenant une fonction dvaluation et des rgles de compatibilit extrmement simples (quels sont dailleurs leurs cots algorithmiques ?). On laisse le soin la lectrice ou au lecteur de mettre au point dautres fonctions dvaluation plus fines, donc sans doute plus dlicates calculer, et de les appliquer notre exemple.

Il existe bien sr pour ce problme des algorithmes de type SEP ou SES trs sophistiqus qui permettent de le rsoudre sur des tailles de lordre de quelques milliers de sommets

Voir par exemple le livre : D.L. APPLEGATE, R.E. BIXBY, V. CHVATAL, W.J. COOK, The Traveling Salesman Problem : A Computational Study , Princeton University Press, 2006, plus de 600 pages trs pointues et actuelles sur le sujet en somme un bon voyage sur le thme Exercices En utilisant la notion dArbre Recouvrant Minimal, quelles autres bornes infrieures peut-on envisager pour notre problme ?

Dans le cas du - PVC, partir dun Arbre Recouvrant Minimal A, on peut construire un cycle hamiltonien CA en considrant lordre dans lequel les sommets sont considrs dans un parcours en profondeur quelconque de A.

Montrer qualors d(CA) 2.d(Cmin) o d reprsente la valuation et Cmin est un cycle optimal.

13

(2) Problme du Sac Dos (SAD)

Ce problme est aussi un grand classique de lOptimisation Combinatoire, on peut le ranger dans la catgorie des problmes de rangements, de chargements,

Sous sa forme la plus simple il est dfini de la faon suivante : Donnes : On a n objets dutilits et de volumes respectifs u1, u2, , un et v1, v2, , vn et dun sac dos de volume maximum V Questions : Comment remplir au mieux le sac ? Autrement dit quels objets doit-on mettre dans le sac pour en maximiser lutilit sans dpasser le volume V ?

On suppose bien sr :

0 < ui et 0 < vi V i 1, 2, ..., n{ }

vii =1

n >V

Si chaque objet i on associe une variable xi 0 reprsentant la quantit de lobjet i

prendre alors le problme revient calculer :

xi 0

xii =1

n vi V

Max xii =1

n ui

ainsi quun contenu optimal du sac. Si aucune restriction nest faite sur le nombre dobjets prendre et en supposant les objets numrots de telle sorte que

u1v1u2v2

... unvn nous avons les rsultats suivants :

Thorme Si on suppose uniquement xi 0 alors la solution optimale est x1 = V / v1 et xi = 0 pour tout i 2 Thorme (DANTZIG, 1957)

Si on suppose 0 xi 1 alors la solution optimale est

xi =1, i 1, 2, ..., r{ }

xi = 0, i r + 2, ..., n{ }

xr+1 =1

vr+1(V vi

i =1

r )

14

o

r =max j vii = 1

j V

Exercice : Prouver ces Thormes.

La difficult de rsolution du problme apparat lorsque nous imposons de prendre un

nombre entier dexemplaires de chaque objet, cest--dire lorsque xi doit tre entier, mme si on se restreint au cas o xi = 0 ou 1. Pour ces cas nous navons pas dquivalents des Thormes prcdents et lon dmontre que le problme est NP Difficile.

On reconnat cependant l un problme de Programmation Linaire en Nombres Entiers (ici en variables boolennes ou entires), il existe alors des mthodes spcifiques de rsolution de ce type de problme. Dans la suite, nous nous intressons au problme en variables boolennes, on dit aussi bivalents ou binaires, et nous supposons que les donnes sont des nombres entiers ou rationnels. Il faut donc calculer :

Max xiuii=1

n

xivii=1

n V

xi 0,1{ }

et trouver une solution, cest--dire un vecteur boolen (x1, x2, , xn), correspondant lutilit maximale. La Recherche Exhaustive consiste ici gnrer tous les sous ensembles possibles dobjets, soit 2n sous ensembles, pour chacun tester sil rentre dans le sac, si cest le cas faire la somme des utilits, et en retenir un dutilit maximum. Cet algorithme est en O(n.2n). Nous allons maintenant dtailler un algorithme de type SEP sur lexemple suivant :

1 2 3 4 5 Utilits 30 27 16 9 7

Volumes 15 18 16 12 14 o V = 45. Pour appliquer la mthode SEP il nous faut prciser la fonction dvaluation permettant de calculer une borne, un ordre de slection et des rgles de compatibilit des variables.

15

Concernant lordre de slection des variables, il est naturel de prendre celui correspondant aux rapports utilits sur volumes dcroissants, cest aussi ce que les deux thormes prcdents invitent faire. Dans le tableau, les objets sont donns dans cet ordre. Quant aux compatibilits, elles rsultent de la contrainte du volume V du sac. SAD est un problme de Maximisation, il faut donc dfinir pour chaque nud de larborescence de recherche une Borne Suprieure, celle ci, compte tenu de lordre des variables, nous est suggre par le premier thorme, il montre en effet quen tout nud o les variables x1, , xi sont dtermines lexpression :

BS(x1, ..., xi) = xkk =1

i uk +

ui+1vi+1

(V xkk =1

i vk )

avec

BS() = u1v1V , est un borne suprieure. Il faut bien sr que

xkvkk =1

i V sinon il ne

peut pas y avoir de solution. Avec la mthode SEP, nous obtenons alors larborescence suivante o les nuds sont numrots dans lordre de leur obtention : 1 2 3 4 5 8 9 6 7 10 11 12 13 Nous avons en effet : - nud 1 : BS(1) = BS() = 30/15 . 45 = 90

- nud 2 : x1 = 1, alors BS(2) = 30 + 27/18 . (45 15) = 75

16

- nud 3 : x1 = 0, alors BS(3) = 27/18 . 45 = 67,5 ; la recherche se poursuit donc au nud 2, car cest le plus prometteur

- nud 4 : x2 = 1, donc BS(4) = 30 + 27 + 16/16 . (45 15 18) = 69

- nud 5 : x2 = 0, donc BS(5) = 30 + 16/16 . (45 15) = 60 ; la recherche se poursuit

donc au nud 4 - nud 6 : x3 = 1, cette solution nest pas ralisable puisque 15 + 18 + 16 = 49 > 45 ; en

ce nud, il ny a pas de descendance - nud 7 : x3 = 0 donc BS(7) = 30 + 27 + 9/12 . (45 15 18) = 66, ltape suivante

explore donc le nud 3 - nud 8 : x2 = 1 donc BS(8) = 27 + 16/16 . (45 18) = 54

- nud 9 : x2 = 0 donc BS(9) = 16/16 . 45 = 45 ; la recherche se poursuit donc avec le

nud 7 - nud 10 : x4 = 1 donc BS(10) = 30 + 27 + 9 + 7/14 . (45 15 18 12) = 66

- nud 11 : x4 = 0 donc BS(11) = 30 + 27 + 7/14 . (45 15 - 18) = 63 ; la recherche

continue au nud 10 - nud 12 : x5 = 1, cette solution nest pas ralisable car 15 + 18 + 12 + 14 = 59 > 45 ;

ce nud est donc strile - nud 13 : x5 = 0, on a alors la solution (1, 1, 0, 1, 0) de valeur 66

Arriv cette tape lalgorithme sarrte car on a une solution avec les objets 1, 2 et 4 de valeur 66 alors que les nuds encore actifs 5, 8, 9 et 11 ont tous une borne suprieure qui est infrieure ou gale 64. Remarquons que l aussi la recherche exhaustive aurait examin les 25 = 32 cas, cest--dire 26 1 = 63 nuds, alors que la mthode SEP se termine en 13 tapes. La mthode SES donnera quasiment la mme arborescence : les sommets, sauf 11, sont obtenus maintenant dans lordre 1, 2, 4, 6, 7, 10, 12, 13, 5, 3, 8 et 9. Il est en effet inutile denvisager le sommet 11 car cest le fils droit de 7 o la borne est 66, valeur dune solution dj trouve en 13. Comme pour le PVC il existe pour SAD dautres algorithmes SEP ou SES beaucoup plus labors permettant de rsoudre des problmes de tailles nettement plus grandes. Nous verrons dans le prochain cours que lon peut aussi rsoudre trs lgamment SAD en utilisant la Programmation Dynamique, mthode qui peut tre rapide lorsque les valeurs des donnes ne sont pas trop grandes.