Mémoire d'Ingénieur en Recherche Opérationnelle - Mathématiques Appliquées
Vincent Pinte Deregnaucourt - Soutenance le 5 juillet 2007, mention très bien.

Sérialisation d'un Schéma de Sous Gradient avec des Métaheuristiques pour la Résolution Approchées de Problèmes de Sacs à Dos Multidimensionnels Difficiles
(SSGMRAPSàDMD pour les intimes...)
versions
* Soutenance : version transparent (pdf, 850 Ko),
* Soutenance : version papier (pdf, 610 Ko)
* Mémoire (Version soutenue, rendue pour la bibliothèque CNAM), (pdf, 3.6 Mo),
* Attestion du Titre (jpg, 350 Ko) .
(Chopin, Nocturne pour Violons et Piano)
(Baba O'Riley est une chanson écrite par Pete Townshend du groupe de rock britannique The Who. Elle apparaît sur leur album Who's Next (1971). Le solo de violon est joué par Dave Arbus du groupe progressif East of Eden. Son enregistrement a eu lieu au studio Olympic en mai 1971. J'étais alors agé de -5 mois. :-)

Résumé :

Ce document est un mémoire d'Ingénieur en recherche opérationnelle (ou mathématiques appliquées) traitant de la résolution approchée du problème du sac à dos multicontraint (MKP) $\cal{NP}$-difficile.

S'appuyant d'une part sur les travaux de la thèse de Babacar Thiongane pour des sacs à dos bi contraints, et sur la pertinence possible de résultats intermédiaires inhérents à la relaxation lagrangienne et à sa résolution par un algorithme de sous gradient projeté, nous proposons d'améliorer cette technique par l'emploi judicieux d'heuristiques dans la phase initiale et de métaheuristiques structurellement différentes, dans les parties interne et finale.

Les métaheuristiques travaillent avec un voisinage et une solution\footnotemark[1] ou une population de solutions\footnotemark[2].

Nous poursuivons notre étude et nous la validons en montrant que cet algorithme, sur des instances plus grandes et plus difficiles, donne également de bons résultats.

\emph{Mots clés }: sac à dos multidimensionnel, relaxation lagrangienne, méthode de sous gradient, métaheuristique, recherche à voisinages variables, recomposition de chemin.


This research work is an M.S. thesis in operational research (applied mathematics field). It deals with finding good approximation solutions for the $\cal{NP}$-hard Multiconstrained Knapsack Problem (also called Multidimensional Knapsack Problem).

On the one hand it uses the results developed in Babacar Thiongane's Ph.D. on bi-constrained knapsacks, and on the other hand it relies on the hypothetical relevancy of intermediate results inherent to the Lagrangian relaxation, and its resolution by a projected subgradient algorithm.

We hereby show how to improve that process through the relevant use of heuristics in the first place, and that of structurally different heuristics in the second place.

Those metaheuristics may work either in neighborhood spaces\footnotemark[1], or from a population of solutions\footnotemark[2].

We take our study even further by showing that this algorithm provides good results in larger and harder proceedings too.

\emph{Keywords}: Multidimensional Knapsack Problem (MKP), Lagrangian relaxation, subgradient, metaheuristics, variable neighborhood search, path relinking.

\footnotetext[1]{VNS - Variable Neighborhood Search - Recherche à Voisinage Variable} \footnotetext[2]{PR - Path relinking - Recomposition de Chemins}