Optimisation en informatique

Code UE : USRS25

  • Cours + travaux pratiques
  • 5 crédits

Responsable national

Christophe PICOULEAU

Responsable opérationnel

Tristan CROLARD

Contenu

1- Présentation de l'ensemble du cours à partir d'un problème d'optimisation concret (localisation). Le problème est-il difficile (du point de vue de la complexité) ? Si oui, comment écrire un modèle mathématique ? Ce modèle permet-il d'obtenir de façon suffisamment efficace une solution optimale à l'aide d'un logiciel ? Si oui, l'étude est terminée. Sinon, comment obtenir une solution approchée et comment valider la solution trouvée ?
2- Apprendre à écrire un programme mathématique : choisir les variables, déterminer leurs domaines, écrire l'objectif et les contraintes. Particularité des modèles en variables binaires ou entières. Travail sur des "cas d'école" : partition de graphes (clustering), coloration (planification), etc.
Application à divers problèmes réels : dimensionnement/conception de réseaux, routage multicast dans les réseaux, placement de copies de fichiers, etc.
3- Apprendre à transformer un problème d'optimisation non linéaire en un programme linéaire de façon à pouvoir utiliser les logiciels. Techniques de linéarisation, prise en compte de rapports ou de produits de variables, etc.
4- Résolution approchée de problèmes difficiles par des méthodes générales (recuit simulé, méthode tabou, algorithmes génétiques, etc.) ou par des méthodes spécifiques (heuristiques ad-hoc). Validation des résultats obtenus par les heuristiques à l'aide de bornes basées, par exemple, sur la résolution du problème (ou d'une relaxation) par un solveur (ou logiciel de résolution).
5- Utilisation d'un solveur libre d'accès (par exemple, GLPK) par le biais d'un modeleur (GMPL) ou du format de fichier LP. Mise en oeuvre sur ordinateur pendant certaines séances.  Rappel des principes de la programmation linéaire, et introduction aux techniques de résolution de programmes linéaires en nombres entiers.
6- Étude d'un cas réel : réalisation d'un projet informatique.

Cette UE apparaît dans les diplômes et certificats suivants

Chargement du résultat...
Patientez
Type
Intitulé
Equipe pédagogique
Modalité(s) / Lieu(x)
Code
Equipe pédagogique Informatique
Modalité(s) / Lieu(x)
  • Enseignée en formation présentielle et/ou partiellement à distance : Paris
  • Type Intitulé Equipe pédagogique Modalité(s) / Lieu(x) Code

    Contact



    Voir les dates et horaires, les lieux d'enseignement et les modes d'inscription sur les sites internet des centres régionaux qui proposent cette formation

    Enseignement non programmé en 2017/2018