Vous êtes ici : FIL > Portail > Licence Info > L3S5 Info > ARO

Algorithmique et Recherche Opérationnelle (ARO)

Responsable

François Lemaire. Bâtiment M3. Bureau 330bis.
Site web : http://cristal.univ-lille.fr/~lemaire
Courrier électronique : francois.lemaire à univ-lille1.fr

Volume horaire

Sur 12 semaines :
  • une heure trente de cours magistral (support de cours en ligne)
  • une heure trente de TD en salle banalisée (feuilles de TD en ligne).
  • une heure trente de TP en salles équipées d'ordinateurs (Linux, AMPL, ...)

Crédits

5 ECTS
Modifié le Fri 30 November 2018, à 09:51:15 AM

Objectifs

Savoir reconnaître, modéliser et résoudre les problèmes d'optimisation qui relèvent de la programmation linéaire ou de la théorie des graphes (chemins de valeur minimale, flot maximal, etc.). Savoir utiliser un logiciel de résolution de programmes linéaires. Logiciel AMPL. Connaître et savoir utiliser quelques algorithmes importants de résolution de programmes linéaires (simplexe) et de la théorie des graphes (Bellman, Dijkstra, etc.).

Compétences

A l'issue de ce module les étudiants doivent
  • être sensibilisés à la modélisation, notamment dans les problèmes d'optimisation
    • savoir reconnaître les problèmes d'optimisation qui relèvent de la programmation linéaire ou de la théorie des graphes ;
    • savoir transformer un problème donné en français en un programme linéaire ou un problème de théorie de graphe ;
    • savoir appliquer et adapter les méthodes vues en court dans des situations réelles ;
  • connaître les techniques de base de la programmation linéaire
    • savoir appliquer à la main l'algorithme du simplexe sur des problèmes simples ;
    • savoir intérprêter et résoudre le dual de problèmes simples ;
    • savoir utiliser un logiciel de résolution de programmes linéaires (logiciel AMPL) ;
    • savoir transformer (lorsque c'est possible) un problème sur les graphes en un programme linéaire, lorsque les algorithmes classiques de la théorie des graphes ne s'appliquent pas ;
  • connaître les éléments de base de la théorie de graphe
    • savoir appliquer les algorithmes classiques de théorie des graphes : parcours largeur/profondeur, plus court chemin, chemins de valeur minimale (Bellman, Dijkstra), flot maximal (Ford-Fulkerson), arbre couvrant minimal (Kruskal) ;
    • savoir expliquer les éléments de preuve des algorithmes simples de théorie de graphes, avoir compris l'utilité des invariants dans les démonstrations ;
    • savoir concevoir et programmer en langage C une bibliothèque simplifiée de théorie des graphes (application concrète des cours d'ASD et de PDC)
    • savoir programmer quelques algorithmes sur les graphes (parcours, plus court chemin, etc.).

Compétences du référentiel licence auxquelles contribue cette unité

  • Participer à la conception et à la réalisation d'applications logicielles :
    • comprendre les différentes natures des informations :données, traitements, connaissances, textes ;
    • choisir, sur des critères objectifs, les structures de données et les algorithmes les mieux adaptés à un problème donné ;
  • Évaluer une solution informatique :
    • analyser, interpréter les résultats produits par l'exécution d'un programme ;
  • Savoir raisonner et démontrer.

Bibliographie

  • Le polycopié donné dans l'onglet « documents » suffit.
  • Introduction à l'algorithmique. 2ème édition. Dunod. Cormen, Leiserson, Rivest et Stein. Un livre de référence pour tout informaticien.
  • Précis de recherche opérationnelle. 5ème édition. Dunod. Faure, Lemaire et Picouleau. Un livre davantage tourné vers les exemples et moins vers l'algorithmique que le précédent.
  • AMPL A modelling language for mathematical programming. International Thomson Publishing. Fourer, Gay and Kernighan. Le manuel de référence du logiciel AMPL, avec de nombreux exemples. En Anglais.
  • Model building in mathematical programming. 3rd edition. John Wiley and Sons Ltd. Williams. Un livre dédié principalement à la modélisation par programmes linéaires, riche d'une douzaine de problèmes. En Anglais.
Modifié le Fri 30 November 2018, à 09:51:15 AM
Gpe Nature Horaire Salle Enseignant e-mail
Cours Mardi 8h30-10h M1 - Amphi Archimède François Lemaire
1 TD Lundi 8h30-10h M5 - A6 Marie-Émilie Voge Marie-Emilie.Voge@univ-lille1.fr
TP Lundi 10h20-11h50 M5 - A16
2 TD Lundi 8h30-10h M5 A1 François Lemaire Francois.Lemaire@univ-lille1.fr
TP Vendredi 8h30-10h M5 - A11
3 TD Mardi 15h20-16h50 M5 - A7 Léopold Weinberg Leopold.Weinberg@univ-lille1.fr
TP Vendredi 8h30-10h M5 - A12
4 TD Jeudi 13h30-15h M5 - A6 Arnaud Liefooghe Arnaud.Liefooghe@univ-lille1.fr
TP Mercredi 15h40-17h10 M5 - A15
5 TD Mercredi 15h40-17h10 M5 - A6 Sylvain Salvati
TP Vendredi 13h30-15h M5 - A11
6 TD Vendredi 10h20-11h50 M5 - A2 Omar Abdelkafi
TP Vendredi 13h30-15h M5 - A15
Modifié le Fri 30 November 2018, à 09:51:15 AM
Séance Cours TD TDO Remarque
2 du 10/09 au 15/09 Introduction à la modélisation et à AMPL.

Résolution graphique de programmes linéaires. Vocabulaire. Définitions.
Pas de TD Pas de TP festival MIX CITE jeudi 13 septembre après-midi

2 cours cette semaine
Le physicien britannique Patrick Blackett est considéré comme un des fondateurs de la recherche opérationnelle. Un article sur le personnage.

2 du 17/09 au 22/09 L'algorithme du tableau simplicial dans un cas favorable. Définitions préliminaires et énoncé de l'algorithme. Résolution graphique. Modélisation en AMPL d'une campagne de publicité. TD 2 TP 1. Prise en main d'AMPL :
  • tester les variantes des modèles d'acierie (jusqu'à la gestion du stock)
  • utiliser les commandes model et reset
  • réfléchir à l'exercice 3 de la feuille de TD2
3 du 24/09 au 29/09 Justification de l'algorithme dans un cas favorable. Terminaison et complexité. L'algorithme du tableau simplicial. Quelques exos de modélisation. TD 3 Modélisation en AMPL d'une campagne de publicité (de la feuille TD2).
4 du 01/10 au 06/10 Un problème d'emploi du temps résolu en AMPL emploitemps.pdf

Présentation du DM. dm-2018.pdf

Introduction aux problèmes de démarrage : rapide présentation de la méthode des deux phases.

Suite de la feuille 3. Exécution manuelle de l'algorithme du tableau simplicial dans le cas favorable et exercices de modélisation. Modélisation en AMPL du problème de production de papier. Gestion de stocks.
5 du 08/10 au 13/10 La dualité en programmation linéaire. Exercices de modélisation. Travail sur le DM. Travail sur le DM (1/2)
6 du 15/10 au 20/10 Introduction à la théorie des graphes. La dualité. TD 5 Travail sur le DM (2/2) Pour les curieux, un ancien TD sur les problèmes de démarrage. TD 4
7 du 22/10 au 26/10 Parcours en largeur (+ court chemin). Fin de la dualité. TP d'introduction sur les graphes. TP graphe 1
du 29/10 au 03/11 interruption pédagogique automne
8 du 5/11 au 10/11 Parcours en profondeur (tri topologique). Chemins de valeur minimale entre un sommet distingué et tous les sommets. Problèmes introductifs de théorie des graphes. TD 6 TP de parcours de graphes. TP graphe 2
9 du 12/11 au 17/11 Algorithmes de Bellman et Dijkstra. Calculs de chemins minimaux en AMPL. Méthode MPM. Rappels de notions de complexité. TD 7 Chemins de plus courte distance. TP graphe 3
10 du 19/11 au 24/11 Flots maximaux. Parcours et tri topologique. TD 8 Parcours en profondeur et labyrinthe. TP graphe 4Fichiers de labyrinthe : labyrinthe1.grp, labyrinthe2.grp.
12 du 26/11 au 01/12 Fin des flots maximaux. Algorithmes de Bellman et Dijkstra. TD 9 Fin des TPs précédents. Algorithme de Bellman pour ceux qui n'ont pas pris de retard. Tester sur le fichier graphe-peage-A1.grp, (voir commentaires à l'intérieur).
12 du 03/12 au 10/12 Fin (bis) sur les flots maximaux. Flots maximaux. TD 10 Fin des TPs précédents. Algorithme de Dijkstra pour ceux qui n'ont pas pris de retard.
13 du 11/12 au 15/12 Pas de cours. Dernier TD.

Contrôles TP.

14 du 17/12 au 21/12
Modifié le Fri 30 November 2018, à 09:51:15 AM

L'évaluation s'effectue suivant une procédure de contrôle continu. Trois notes seront attribuées à chaque étudiant durant le semestre :

  • TD : une note sur 20 de Travaux Dirigés obtenue en additionnant les 4 meilleures de 5/6 mini interros notées sur 5 en TD
  • TP : calculée sur un mini-projet d'AMPL (à rendre à mi semestre et qui compte pour un quart) et un contrôle TP en fin de semestre (qui compte pour trois quarts)
  • DS : une note sur 20 pour l'examen de fin de semestre.

La note finale sur 20 (N) est calculée comme une moyenne pondérée de ces notes, avec un SUP :

N = (TP + sup(TD + 2*DS, 3*DS)) /4

Pour la session de rattrapage, la note de TP est conservée. Le calcul se fait par

N=(TP + 3*DS)/4

L'unité acquise apporte 5 ECTS.

Modifié le Fri 30 November 2018, à 09:51:15 AM

Logiciel AMPL

L'URL du logiciel AMPL. Vous pouvez y télécharger des versions récentes (nécessitant peut-être de s'incrire sur le site d'IBM). Toutefois, le plus simple pour installer AMPL est de suivre la méthode ci-dessous pour installer une version étudiante.
  1. Récupérer les fichiers selon le cas:
  2. créer un répertoire et décompressez les archives dedans. Assurez-vous que les fichiers ampl, minos, gurobi et gurobix ont bien les droits d'exécutables.
  3. le répertoire que vous avez créé sera nommé DIR dans la suite, remplacez donc DIR dans ce qui suit par le répertoire que vous avez choisi
  4. modifier le fichier gurobi en remplaçant les deux chemins par DIR
  5. ajouter DIR à la variable PATH
  6. lancer ampl
Remarques:
  • sous Linux, si vous avez une erreur disant que ampl n'est pas trouvé, il vous manque peut-être les librairies de compatibilité 32 bits (sous Debian, le paquetage libc6-i686:i386 devrait être suffisant).
  • les binaires pour Windows sont sur http://www.netlib.org/ampl/student/mswin/ , mais il faut certainement adapter la procédure précédente

Documentation pour installer le mode AMPL pour emacs : ici

Logiciel du simplexe

Le logiciel simplex écrit par François Boulier vous permet de lancer l'algorithme du simplexe et de voir les tableaux simpliciaux. C'est un logiciel de démonstration à but pédagogique. Voici l'archive : simplex-1.8.tgz. Il s'installe sous Unix ou Linux. Il est écrit en langage C. Il utilise les bibliothèques BLAD ainsi que GMP. Note : l'archive contient non seulement les sources mais aussi un exécutable qui devrait fonctionner sur tout Linux récent ainsi qu'un exécutable fonctionnant sous WINDOWS.

Support de cours

Le support de cours au format PDF.

Bibliothèque C pour les graphes

La bibiothèque en C pour les TP sur les graphes est ici.

Archives de sujets d'examen

Les derniers sujets d'Algo :
Modifié le Fri 30 November 2018, à 09:51:15 AM