Aperçu des sections

  • Généralités

  • Présentation de la matière

    Un problème d'optimisation combinatoire consiste à trouver la solution optimale (la meilleure solution) à partir d'un ensemble fini E de solutions possibles. Le défi majeur est que l'ensemble E contient un nombre énorme de solutions et parcourir toutes les solutions pour trouver la meilleure nécessite des siècles de temps de calcul.

    En mathématiques appliquées et en informatique, les problèmes d'optimisation combinatoire sont problèmes difficiles. En effet, on trouve les problèmes d'optimisation non seulement en informatique et en mathématiques appliquées mais aussi en logistique, en santé, en engineering etc…

    Pour faire face à ces problèmes, il existe plusieurs méthodes dont le but est de trouver une solution de bonne qualité (pas nécessairement optimale) dans un temps de calcul très réduit.

    Dans cette matière intitulée "Résolution de problèmes et optimisation combinatoire", nous allons présenter ces méthodes afin de vous permettre de résoudre les problèmes d'optimisation combinatoire d'une manière efficace.




    • Informations générales & Fiche-contact

      info-img

      Institut : des mathématiques et de l'informatique

      Département: de l'informatique

      Public cible : 1ère année Master, Spécialité : Intelligence Artificielle et ses Applications (I2A)

      Intitulé du cours : Résolution de problèmes et optimisation combinatoire

      Unité d’Enseignement : UE Fondamentales 3

      Crédit:05

      Coefficient:03

      Mode d'évaluation : Continu : 40% & Examen : 60%

      Durée : 14-16 semaines, avec un VHS = 67.5 heures.

      Enseignant : Cours, TD et TP: Dr. Oualid GUEMRI

      Contact : par email o.guemri@centre-univ-mila.dz.


      • Section 3


        • Objectifs du cours

          Obj-img


          A la fin de ce cours, vous serez capables de :

          1. Identifier et connaître les problèmes d’optimisation.

          2. Modéliser une solution pour un problème d’optimisation en proposant la structure de données la plus adéquate.

          3. Appliquer une méthode d’optimisation pour la résolution d’un problème d’optimisation.

          4. Concevoir de nouvelles méthodes pour l’optimisation combinatoire.

          5. Analyser le comportement d’un algorithme utilisé pour résoudre un problème.

          6. Évaluer l’efficacité d’un algorithme pour un problème d’optimisation


          • Prérequis

            Avant de commencer ce cours :

            • Il faut avoir de bonnes connaissances en algorithmique et en programmation.

            • Il est recommandé aux étudiants d’avoir des connaissances de base en mathématiques discrètes.


            • Contenu

               - Chapitre 1 :  Introduction à l'optimisation  combinatoire 

                   . La complexité algorithmique 

                   . Classes de problèmes

                   . Optimisation combinatoire : Concepts de base

               - Chapitre 2 :  Les heuristiques 9

                   . Définition générale d'une heuristique  

                   . Codage et représentation de la solution  

                   . Les heuristiques gloutonnes de construction  

                   . Les recherches locales 

              - Chapitre 3 : Les Métaheuristiques

                  . Partie 1 : Concepts de base et définitions

                  . Partie 2 : Métaheuristiques à base de solution unique 

                    => Recherche tabou

                    => Recuit simulé

                  . Partie 3 : Métaheuristiques à base de population de solutions

                    => Algorithme  génétique.

              - Chapitre 4 : 

                  . Introduction.

                  . La méthode de "branch and bound" (B&B) : Définition.

                  . Borne inférieure et Borne supérieure.

                  . La méthode de B&B : Eléments de base de la méthode B&B,  Algorithme et illustration de la méthode B&B sur le problème de TSP



              • Chapitre 1 : Introduction à l'optimisation combinatoire

                La première partie de ce chapitre présente la complexité algorithmique ainsi les différentes classes des problèmes (classification des problèmes à base de la complexité). Ensuite, La deuxième partie présente les problèmes d’optimisation combinatoire.

              • Chapitre 2 : Les heuristiques

                Dans le deuxième chapitre, il s’agit d’étudier comment représenter une solution d’un problème et ensuite de présenter les heuristiques gloutonnes de construction et les recherches locales.


              • Chapitre 3 : Les métaheuristiques

                Dans ce troisième chapitre, des différentes métaheuristiques sont présentées, y compris les métaheuristiques à base de solution unique (La méthode de recherche tabou et la méthode de recuit simulé) et les métaheuristiques à base de population de solutions (l’algorithme génétique).


              • Chapitre 4 : Les méthodes exactes

                Dans le quatrième chapitre, les méthodes exactes sont présentées.


              • TP

              • Bibliographie


                [1] E. A Feigenbaum and J. Feldman. Computers and thought. McGraw-Hill, Inc. New York, NY, USA, 1963.

                [2] I.H. Osman and G. Laporte, Metaheuristics : a bibliography. Annals of Operations Research 63, 513-623, 1996.

                [3] S. Voß, S. Martello, I.H. Osman and C. Roucairol (Eds), Meta-Heuristics - Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands, (1999).

                [4] Kirkpatrick, S., Gelatt, C., et Vecchi, M. Optimisation by simulated annealing. Science, tome 220, n o 4598, pages 671-680, 1983.

                [5] Glover F., 1986. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 13, p. 533-549.

                [6] Guemri, O. (2017). Proposition de solutions pour l'optimisation des chaînes logistiques (Doctoral dissertation, Université d’Oran 1).


                • Section 13

                  • Section 14

                    • Section 15

                      • Section 16

                        • Section 17

                          • Section 18

                            • Section 19

                              • Section 20

                                • Section 21