Contribution à la résolution de problèmes d'optimisation combinatoire: méthodes heuristiques et parallèles

Ce mémoire s'inscrit dans le domaine de l'optimisation combinatoire, plus précisément dans la résolution de problèmes du sac à dos et de ses variantes complexes. Il intéressera particulièrement les étudiants et chercheurs en informatique, mathématiques appliquées et génie industriel, qui souhaitent comprendre les méthodes heuristiques et parallèles pour traiter ces problèmes difficiles.

La question

Le travail aborde la résolution du problème du sac à dos multiple (MKP), une extension du problème classique du sac à dos, qui consiste à remplir plusieurs sacs à dos de capacités différentes avec un ensemble d'objets, afin de maximiser le profit total sans dépasser les capacités. Ce problème est NP-complet, ce qui signifie qu'il est difficile à résoudre de manière exacte pour de grandes instances. La question centrale est donc de développer des méthodes efficaces, notamment heuristiques et parallèles, capables de fournir de bonnes solutions en un temps raisonnable. Par ailleurs, le mémoire s'intéresse aussi à l'accélération des méthodes classiques d'optimisation combinatoire, telles que Branch and Bound et le Simplexe, en exploitant les architectures GPU modernes.

Concepts de base

Un problème d’optimisation combinatoire cherche à maximiser ou minimiser une fonction objectif sous contraintes. Le problème du sac à dos classique (KP) est formulé ainsi :

max ∑(i=1 à n) p_i x_i
s.c. ∑(i=1 à n) w_i x_i ≤ c
x_i ∈ {0,1}

où chaque objet i a un poids w_i et un profit p_i, c est la capacité du sac, et x_i indique si l'objet est choisi (1) ou non (0).

Le problème du sac à dos multiple (MKP) généralise ce cadre à m sacs à dos, chacun avec une capacité c_i :

max ∑(i=1 à m) ∑(j=1 à n) p_j x_ij
s.c. ∑(j=1 à n) w_j x_ij ≤ c_i, ∀ i=1..m
∑(i=1 à m) x_ij ≤ 1, ∀ j=1..n
x_ij ∈ {0,1}

La contrainte supplémentaire garantit qu’un objet ne peut être affecté qu’à un seul sac.

Une notion importante est celle du noyau du sac à dos, qui correspond à un sous-ensemble réduit d’objets déterminants pour la solution optimale. Les objets sont triés par efficacité décroissante (ratio profit/poids), et le noyau est centré autour de l’objet de rupture s, défini par :

∑(j=1 à s-1) w_j ≤ c < ∑(j=1 à s) w_j

Le noyau permet de réduire la taille du problème en fixant certains objets à 0 ou 1 en dehors du noyau, et en ne résolvant exactement que le problème restreint au noyau.

Les méthodes exactes classiques pour résoudre ces problèmes sont :

• Branch and Bound : une méthode d’énumération intelligente qui explore un arbre de solutions possibles, en élaguant les branches non prometteuses grâce à des bornes.
• Programmation Dynamique : une approche récursive qui construit la solution optimale par étapes en mémorisant les sous-solutions.

Le calcul de bornes supérieures et inférieures est essentiel pour ces méthodes, ainsi que la réduction de variables qui permet de simplifier le problème avant résolution.

Enfin, l’émergence des architectures GPU (Graphics Processing Units) offre de nouvelles possibilités pour paralléliser ces algorithmes et accélérer leur exécution.

Approche

Le mémoire propose une contribution sur deux axes :

• Une nouvelle heuristique appelée RCH (Recursive Core Heuristic) pour le problème du sac à dos multiple. Cette méthode considère le MKP comme une succession de problèmes KP à résoudre, chacun défini sur un noyau. Pour chaque noyau sauf le dernier, un problème de subset sum est résolu par programmation dynamique, tandis que le dernier noyau est traité par programmation dynamique classique.
• La mise en œuvre parallèle sur GPU des méthodes classiques de Branch and Bound et du Simplexe. L’architecture CUDA de NVIDIA est exploitée pour décomposer les calculs en tâches parallèles, optimiser les accès mémoire et synchroniser les threads, afin de réduire les temps de calcul.

Pour Branch and Bound, l’algorithme est adapté pour fonctionner en mode hybride CPU-GPU, où la génération et l’évaluation des nœuds sont parallélisées sur GPU, tandis que le CPU gère la gestion globale de l’arbre et les opérations séquentielles. Des techniques spécifiques sont utilisées pour minimiser les latences mémoire et optimiser la gestion des données.

Pour le Simplexe, l’algorithme est décomposé en opérations matricielles parallélisables, avec une gestion fine des mémoires partagées et globales sur GPU. Une extension multi-GPU est également proposée, permettant de répartir le tableau du Simplexe entre plusieurs cartes graphiques et de réduire les échanges CPU-GPU.

Résultats

Les expérimentations montrent que :

• L’heuristique RCH fournit des solutions de bonne qualité pour le problème MKP, en exploitant efficacement la notion de noyau et la programmation dynamique sur sous-problèmes.
• La mise en œuvre parallèle de Branch and Bound sur GPU permet une accélération significative par rapport à la version séquentielle, notamment dans le calcul des bornes et la génération des nœuds.
• L’implémentation du Simplexe sur GPU, ainsi que sa version multi-GPU, obtiennent des gains de performance notables par rapport à l’exécution sur CPU seul, grâce à la parallélisation des calculs et à l’optimisation des transferts mémoire.

Ces résultats confirment l’intérêt des architectures GPU pour l’optimisation combinatoire, en particulier pour des problèmes NP-complets comme le MKP.

Limitations et questions ouvertes

Le mémoire souligne que :

• La taille optimale du noyau pour garantir l’optimalité reste difficile à déterminer a priori, et dépend du type d’instances. Les heuristiques doivent donc être adaptées selon les cas.
• La parallélisation sur GPU nécessite une gestion fine des accès mémoire et des synchronisations, ce qui limite parfois la scalabilité et la généralisation des méthodes à d’autres types de problèmes.
• Les méthodes proposées restent heuristiques ou approximatives pour les grandes instances, et la recherche de solutions exactes rapides demeure un défi.

Glossaire

• Problème du sac à dos (KP) : problème d’optimisation combinatoire visant à maximiser le profit d’objets choisis sous contrainte de poids.
• Problème du sac à dos multiple (MKP) : extension du KP avec plusieurs sacs à dos à remplir simultanément.
• Noyau (core) : sous-ensemble réduit d’objets autour de l’objet de rupture, crucial pour la solution optimale.
• Branch and Bound : méthode d’énumération avec élagage basée sur des bornes.
• Programmation Dynamique : méthode récursive mémorisant les sous-problèmes pour construire la solution optimale.
• Heuristique RCH (Recursive Core Heuristic) : méthode proposée pour résoudre le MKP en décomposant en sous-problèmes KP sur noyaux.
• GPU (Graphics Processing Unit) : processeur spécialisé dans le calcul parallèle massif.
• CUDA : architecture de programmation parallèle développée par NVIDIA pour exploiter les GPU.
• Simplexe : algorithme classique de programmation linéaire pour résoudre des problèmes d’optimisation linéaire.