Utilisation de la Relaxation Lagrangienne pour déterminer des Ensembles Bornants Inférieurs pour le Problème de Voyageur de Commerce Bi-objectif

Session : SS2-4 / SS2 : Application et théorie de l’optimisation multiobjectif
Vendredi 12 février 10:30 - 11:50 Salle : RP8
Quentin Delmée, Kathrin Klamroth et Anthony Przybylski

1 Problématique Des ensembles bornants serrés sont un élément fondamental pour les méthodes énumératives de résolution des problèmes d’optimisation combinatoire multi-objectif. Des méthodes de Branch & Bound bi-objectif ont été récemment appliquées avec succès, en se basant sur la relaxation convexe. Cet ensemble bornant est serré, permet l’obtention de solutions admissibles, et se détermine rapidement en pratique si la version mono-objectif du problème se résout en temps polynomial ou pseudo-polynomial. Dans le cas contraire, la relaxation continue est une alternative possible mais elle est beaucoup moins serrée en général. D’autres relaxations sont utilisées dans le contexte mono-objectif, pour obtenir un bon compromis entre la qualité de la borne obtenue et son coût temporel. Dans ce travail, nous considérons la relaxation lagrangienne. Cette relaxation est un classique dans le contexte monoobjectif. Cependant elle est beaucoup moins présente dans la littérature multi-objectif. Ehrgott et Gandibleux [1] ont fait une proposition d’utilisation de la relaxation lagrangienne, appliquée au problème du voyageur de commerce bi-objectif. Nous revenons sur cette proposition et proposons des améliorations. 2 Relaxation Lagrangienne Multi-Objectif Ehrgott et Gandibleux [1] ont proposé d’effectuer une somme pondérée des fonctions objectifs et d’appliquer ensuite une relaxation lagrangienne du problème mono-objectif obtenu. La méthode décrite dans Beasley [2] est utilisée pour mettre à jour les multiplicateurs comme cela se fait habituellement dans le contexte mono-objectif. Idéalement, une solution admissible, et donc optimale, est obtenue. Cependant en général, on n’obtient pas une solution admissible et la borne obtenue est alors restée inexploitée dans le contexte bi-objectif. La raison vient du terme de pénalité qui est ici défini pour la somme pondérée des fonctions objectifs et non pas pour chacune des fonctions objectifs. Nous proposons de définir la relaxation lagrangienne directement pour un problème multiobjectif. Le principe est le même que dans le contexte mono-objectif, nous relâchons un sousensemble de contraintes et nous les faisons apparaître dans un terme de pénalité non pas dans une mais dans la totalité des fonctions objectifs. Ensuite, rien n’oblige à utiliser les mêmes valeurs pour les multiplicateurs dans chacune des fonctions objectifs. Nous obtenons finalement un problème multi-objectif dont la résolution définit un ensemble bornant inférieur. Toutefois, le problème ainsi obtenu reste un problème d’optimisation combinatoire multiobjectif. Sa résolution exacte est donc naturellement coûteuse. Pour déterminer un ensemble bornant dans un temps raisonnable, nous considérons donc l’utilisation de la somme pondérée. 3 Étude du lien entre la somme pondérée et la relaxation lagrangienne Pour chaque poids considéré, la résolution de la somme pondérée nous permet d’obtenir un hyperplan en temps qu’ensemble bornant. L’ensemble d’hyperplans obtenus définira un ensemble bornant inférieur. Nous cherchons à fixer les multiplicateurs pour chaque fonction objectif de manière à obtenir le meilleur ensemble bornant possible. Il y a bien sûr plus de multiplicateurs à considérer que dans le contexte mono-objectif. Nous montrons qu’en général nous obtenons le même hyperplan pour une infinité de combinaisons de multiplicateurs différents. Nous utilisons cette propriété pour restreindre l’évolution des valeurs des multiplicateurs. Nos expérimentations sur le problème du voyageur de commerce bi-objectif montrent que l’ensemble bornant obtenu est très proche de la relaxation convexe.

Mots clés : Optimisation combinatoire bi-objectif, ensemble bornant, relaxation lagrangienne, somme pondérée, problème du voyageur de commerce