Une recherche réactive pour la résolution du problème max-min knapsack avec deux scénarios

Session : SS16-1 / SS16 : Résolution parallèle des problèmes mono ou multi objectifs (continu et/ou combinatoire)
Mercredi 10 février 11:00 - 12:20 Salle : RP9
Thekra Aldouri et Mhand Hifi

Nous nous intéressons à la résolution du MSKP avec deux scénarios (noté 2SKP) par application d'une méthode réactive à base de recherche par voisinage. Le problème du knapsack multi-scénarios en max-min est une variante du problème du knapsack classique. Il est caractérisé par un ensemble d'items I={1,...,n}, où chaque items i est muni d'un profit et d'un poids. De plus, la seule contrainte du MSKP est représentée par la contrainte knapsack de capacité c. De plus, un scenario s est défini comme l'ensemble des profits qu'on associe à chaque élément i de I. Chacun des scénarios s est représenté par un profit p(i,s) associé à l'item i de I, dépendant du scenario s.

Mots clés : Recherche à voisinage, knapsack, optimisation, perturbation