Travail pratique d'optimisation Combinatoire

Avant tout : n'oubliez pas de dézipper les fichiers datas et methods.

ce travail pratique s'inscrit dans une série de mise en oeuvre des différentes heuristiques étudiées, dans le but de résoudre le problème de sac à dos qui est un problème classique en optimisation combinatoire.

Les méthodes abordées ici sont :

1. Résolution standard du problème de sac à dos

2. Résolution du problème de sac à dos avec greedy

3. Résolution du problème de sac à dos à l'aide de du principe de la récursivité

4. Résolution du problème de sac à dos à l'aide de du principe de la récursivité avec memorisation

5. Résolution du problème de sac à dos avec de la programmation dynamic (Bottum Up)

6. Résolution du problème de sac à dos avec Branch and Bound

7. Résolution du problème de sac à dos avec Récuit Simulé

8. Résolution du problème de sac à dos avec Algorithme Génétique

Pour des raisons de code propre, chaque algorithme est repris dans un fichier à part (même si celui-ci peut paraître plus simple comme greedy).

Par ailleurs, ils sont appelé dans le fichier main.ipynb ou j'ai pris le soin de faire un bref rapport

Les sources :

Source 1 - Cours d'Optimisation Combinatoire Master 1 de Sébastien Adam

Source 2 - Recherche Opérationnelle TOME 1 de Jacques Teghem

Sources 3 - Github : Honnêteté scientifique exige; je dois avoué que je me suis aussi inspiré de certains code trouvés sur Github, afin d'éclaire certaines zone d'ombres rencontrés (En particulier pour les algorithmes : génétiques et récuit simulés).