Optimisation en informatique
Code UE : USRS25
- Cours + travaux pratiques
- 5 crédits
Responsable(s)
Christophe PICOULEAU
Tristan CROLARD
Objectifs pédagogiques
A partir de problèmes concrets en informatique (majoritairement, mais pas exclusivement, issus des réseaux de télécommunication), apprendre à traiter des problèmes difficiles de la recherche opérationnelle : savoir écrire un modèle mathématique et proposer des méthodes, optimales ou non (mais efficaces malgré tout), utilisant des outils pratiques pour résoudre ces problèmes (méthodes heuristiques, programmation linéaire et logiciels).
Compétences visées
L'étudiant ayant suivi cet enseignement sait reconnaître et modéliser un problème de recherche opérationnelle. Il sait le résoudre avec des outils simples. Il sait en particulier aborder certains problèmes d'optimisation combinatoire dans les réseaux informatiques.
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.
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
Rechercher une formation
RECHERCHE MULTI-CRITERES
-
Vous pouvez sélectionner des formations grâce à un mot ou à une expression présent dans l’intitulé ou dans les index (discipline ou métier visé).
Des index vous sont suggérés à partir du 3e caractère saisi, mais vous pouvez aussi saisir librement tout autre mot . - Les différents items sélectionnés sont croisés.
ex: "Comptabilité" et "Région Grand Est" - Validez par le bouton « Rechercher » ou par la touche Entrée.
- Cette recherche affiche aussi les fiches UE et certificats régionales. Leurs codes les distinguent des fiches nationales par le suffixe de la région (ex : « -IDF » ).
Par défaut, les fiches régionales reprennent le contenu de la fiche nationale correspondante. Mais dans certains cas, des informations régionales ont pu être ajoutées. - Certains diplômes se déclinent selon plusieurs parcours. Pour afficher tous les parcours, tapez la racine du code (ex : « LG035 »).
- Certains stages ont un double code : leur code propre et le code de l’UE ou du certificat équivalent.
- Dans tous les cas, veillez à ne pas insérer d'espace ni de ponctuation supplémentaire.
- Validez par le bouton « OK » (et non pas par la touche Entrée).
Chargement du résultat...
Intitulé de la formation |
Type |
Modalité(s) |
Lieu(x) |
|
---|---|---|---|---|
Intitulé de la formation | Type | Modalité(s) | Lieu(x) |
Contact
Voir le calendrier, le tarif, les conditions d'accessibilité et les modalités d'inscription dans le(s) centre(s) d'enseignement qui propose(nt) cette formation.
Enseignement non encore programmé
Code UE : USRS25
- Cours + travaux pratiques
- 5 crédits
Responsable(s)
Christophe PICOULEAU
Tristan CROLARD