Problème du stable multi-objectif

 

 

BADJARA Mohamed El-Amine Département de Recherche Opérationnelle Faculté de Mathématiques - USTHB

Alger - Algérie

m-Cette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser.


CHERGUI Mohamed El-Amine

Laboratoire RECITS Département de Recherche Opérationnelle Faculté de Mathématiques - USTHB

Alger - AlgérieCette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser.';document.getElementById('cloakcf404df621af255d14ba8431621743d6').innerHTML += ''+addy_textcf404df621af255d14ba8431621743d6+'<\/a>';

 

 

 

 

Résumé—Une méthode exacte de type séparation-évaluation est mise en œuvre pour la génération de l’ensemble des stables effi- caces dans un graphe dont chaque sommet est valué par un vec- teur poids. La méthode exploite la structure des données du problème du stable et permet de décomposer le problème initial, dans une structure arborescente, en sous problèmes indépen- dants de tailles réduites, chacun   pouvant être résolus par une méthode générale de résolution d’un problème multi-objectif linéaire discret.

 

Mots clés: Stable dans un graphe; programme linéaire en nombres  entiers;  séparation  et  évaluation ;    programme  multi- objectif ; solution efficace.

 

I.     INTRODUCTION

Le problème du stable est un problème classique d’optimisation combinatoire connu pour être de type NP- difficile et il en est de même du même problème dans sa ver- sion multi-objectif, noté MOISP. Ce problème n’a pas reçu suffisamment l’attention  des chercheurs à notre connaissance, et très peu de travaux existent seulement pour le problème général connu sous le nom ‘’Set Packing Problem’’ dans le cas bi-objectif [2], [3]. Nous proposons une méthode exacte par séparation et évaluation pour trouver tous les stables effi- caces de MOISP, qui exploite la structure de la matrice des contraintes du problème du stable avant de faire appel à une méthode générale dédiée à la résolution de problèmes d’optimisation multi-objectif linéaires en variables discrètes (MOILP). Nous montrons que notre méthode est plus perfor- mante que la méthode générale décrite par Chergui et al. dans [1] pour la résolution de MOILP.

 

 

télécharger l'article