Philippe Augerat
Les méthodes d'énumération implicite (Branch-and-Bound, Branch-and-Cut) sont très utilisées en recherche opérationnelle pour résoudre des problèmes tel que celui du Voyageur de Commerce.
Ce projet se propose d'entrevoir quelques unes des questions relatives à la parallélisation des méthodes d'énumération dans le cadre d'un algorithme de résolution du problème de sac à dos.
Dans une version simplifiée, le problème de sac à dos s'énnonce ainsi :
sous la contrainte
Dans, l'interprétation classique, on transporte des objets i de poids 
, de valeur 
. b est une limite supérieure du poids total que l'on peut transporter. 
représente le nombre d'objets i transportés. On cherche bien entendu à maximiser la valeur totale des objets transportés.
Une méthode de résolution consiste à énumérer de manière implicite toutes les solutions possibles, c'est-à-dire, les vecteurs x satisfaisant (2) et (3).
L'algorithme présenté maintenant suppose que les objets sont triés de façon à avoir
En effet, sous cette condition, toute solution x satisfait :
c'est-à-dire que l'on peut borner 
en ne connaissant que les valeurs des k premiers éléments de x.
En particulier si M est la valeur associée à une solution et
on sait que x n'est pas solution optimale, quelque soit la valeur de 
,.., 
.
On a donc un moyen d'éliminer des groupes de solutions sans les tester, ce qui justifie le terme implicite dans le nom de notre méthode.
Pour simplifier le travail, on considèrera le cas où les prennent leur valeur dans {0,1} et on génèrera les et les directement de manière à ce qu'ils satisfassent (4).
Un algorithme séquentiel classique est celui de l'énumération récursive sous forme d'un arbre binaire. Chaque n 
ud de l'arbre correspond à une solution x partielle (au sens où seulement une partie des est fixée). Les deux n uds suivants dans l'arbre sont obtenus par la sélection ou la non sélection d'un objet supplémentaire dans la solution. Enfin, les feuilles de l'arbre sont les solutions.
L'arbre d'énumération est en général mal équilibré. On utilisera donc un algorithme maître/esclaves pour équilibrer la charge entre les différents processeurs. Le maître construira toutes les solutions partielles à un niveau de profondeur de l'arbre donné. Chaque esclave traitera une solution partielle en utilisant l'algorithme séquentiel puis se mettra en attente d'une nouvelle solution partielle à traiter.
Dans un premier temps, on implémentera cet algorithme sur une machine parallèle virtuelle en utilisant MPI. Tout en suivant le modèle de rapport de projet, on se concentrera plus particulièrement sur les mesures de performance. En particulier, on fera varier le nombre de processeurs, le choix de la profondeur de départ choisie, c'est-à-dire le nombre de tâches à nombre de processeurs fixe. On recherchera le meilleur comportement de l'algorithme.
On modifiera ensuite l'algorithme de manière à ce que le maître informe les tâches esclaves de la valeur du gain maximal courant. La connaissance de cette valeur peut permettre d'éliminer plus de branches et donc de réduire la durée de la tâche esclave. Mais on engendre alors de nombreuses communications. On comparera les deux algorithmes.
Références : "Linear programming", V. Chvatal
