Optimisation en informatique
RCP104
Objectifs pédagogiques :
A partir de problèmes concrets en informatique (majoritairement issus des réseaux de télécommunication), l'UE vise à apprendre à traiter des problèmes d'optimisation difficiles. En particulier, elle vise à apprendre à écrire un problème d'optimisation sous la forme d'un modèle mathématique, puis à proposer des méthodes, exactes ou non (mais efficaces malgré tout), utilisant des outils pratiques pour résoudre un tel problème (méthodes heuristiques, logiciels de programmation linéaire, programmation dynamique, etc.).
Public et conditions d'accès :
Élèves ingénieurs, étudiants de master M1.
Prérequis : avoir des connaissances de base en algorithmique, réseaux informatiques, programmation, graphes et recherche opérationnelle.
Compétences :
L'élève ayant suivi cet enseignement sait comment traiter des problèmes d'optimisation dans les réseaux de différents types.
Il ou elle sait notamment les modéliser sous la forme de programmes linéaires, en nombres entiers ou non.
Il ou elle sait également identifier certains problèmes simples, et les résoudre ensuite à l'aide d'algorithmes efficaces connus.
Enfin, il ou elle sait résoudre les problèmes difficiles (souvent des problèmes d'optimisation combinatoire) à l'aide d'outils issus de la recherche opérationnelle, comme la programmation dynamique, les méthodes de résolution de PLNE (à travers des solveurs de PLNE, qui implémentent ces méthodes), ou des méthodes de résolution approchée (heuristiques et méta-heuristiques).
Méthodes de validation :
Examen noté (sur 16 points).
Un ou deux TP noté(s) (sur 4 points en tout).
Contenu de la formation :
1) Présentation de problèmes simples d'optimisation dans les réseaux : routage (acheminement de flux de données sous contraintes de bandes passantes), tables de routage (via l'algorithme de Dijkstra), arbres de connexion simples (via l'algorithme de Kruskal).
2) Modélisation de problèmes d'optimisation par la programmation linéaire (PL) : choix des variables, détermination de leurs domaines, écriture de la fonction objectif et des contraintes. Formulation par la PL de problèmes d'acheminement de flux de données (problèmes de flots maximums ou à coût minimum). Méthode de résolution graphique pour la PL.
3) Mise en oeuvre informatique utilisant un solveur (logiciel de résolution) de PL libre d'accès (a priori, GLPK), par le biais d'un modeleur (GMPL) ou du format de fichier LP.
4) Problèmes difficiles en optimisation dans les réseaux : retour sur les arbres de connexion dans le cas général, et leurs liens avec les arbres de Steiner. Notions de complexité des algorithmes et des problèmes, et catégorisation des problèmes simples et difficiles (P versus NP).
5) Modélisation et résolution de problèmes difficiles (essentiellement combinatoires) d'optimisation dans les réseaux à l'aide de la programmation linéaire en nombres entiers (PLNE) : particularités des modèles en variables binaires ou entières, et formulations pour des problèmes classiques (comme les arbres de connexion dans le cas général, l'allocation de fréquences, le routage multicast, etc.). Linéarisation de problèmes d'optimisation non linéaires (contenant, par exemple, des produits de variables) de façon à pouvoir les résoudre via des solveurs de PLNE. Introduction aux techniques de résolution de PLNE, et aux inégalités valides. Mise en oeuvre informatique pendant une ou deux séances, puis étude d'un cas réel, sous la forme d'un TP noté.
6) Résolution de certains problèmes difficiles par des méthodes basées sur la programmation dynamique, lorsque cela est possible : principe d'optimalité de Bellman, et exemples d'algorithmes de programmation dynamique pour des problèmes classiques en optimisation dans les réseaux.
7) Résolution approchée de problèmes d'optimisation 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, gloutonnes, par recherche locale, etc.). Validation des résultats obtenus par ces heuristiques à l'aide de bornes basées, par exemple, sur la résolution du problème (ou d'une relaxation) par un solveur. Etude de la résolution approchée d'un cas réel, sous la forme d'un TP noté.
Il est à noter que le plan de cette UE a notamment vocation à refléter la démarche de résolution de problèmes d'optimisation dans les réseaux suivie dans l'UE. On commencera par identifier le problème à traiter comme simple ou difficile (du point de vue de la complexité). Si ce problème est difficile, on cherchera alors dans un premier temps à le formuler comme un programme mathématique, ou à utiliser la programmation dynamique pour le résoudre. Si, à l'issue de cette première étape, la formulation du problème utilisée ne permet pas d'obtenir de façon suffisamment efficace une solution optimale à l'aide d'un solveur, ou bien si le problème ne peut pas être résolu efficacement par la programmation dynamique, on s'intéressera dans un second temps à l'obtention d'une solution approchée. En particulier, on cherchera à répondre à la question suivante : comment obtenir rapidement une bonne solution approchée, et ensuite évaluer la qualité de cette solution ?
Bibliographie :
- Alain Billionnet: Optimisation discrète (Dunod)
- Philippe Lacomme, Christian Prins, Marc Sevaux: Algorithmes de graphes (Eyrolles)
- Johann Dréo, Alain Pétrowski, Patrick Siarry, Eric Taillard: Métaheuristiques pour l'optimisation difficile (Eyrolles)
- Malek Rahoual et Patrick Siarry: Réseaux informatiques : conception et optimisation
Cette UE apparaît dans les diplômes et certificats suivants :
- MR11603A : Master Sciences, technologies, santé mention Informatique parcours Systèmes d'information et business intelligence
- MR12301A : Master Sciences, technologies, santé, mention mathématiques appliquées, statistique parcours Statistique du risque pour la finance et l'assurance
- MR11607A : Master Sciences, technologies, santé mention Informatique parcours Sécurité informatique, cybersécurité et cybermenaces En bretagne
- CYC9101A : Diplôme d'ingénieur Spécialité informatique parcours Architecture et ingénierie des systèmes et des logiciels (AISL)
- CYC9102A : Diplôme d'ingénieur Spécialité informatique parcours Intelligence Artificielle et Optimisation
- CYC9104A : Diplôme d'ingénieur Spécialité informatique parcours Informatique, réseaux, systèmes et multimédia
- CYC9105A : Diplôme d'ingénieur Spécialité informatique parcours Informatique systèmes d'information
- CYC9106A : Diplôme d'ingénieur Spécialité informatique parcours Cybersécurité
- CRN0801A : Titre RNCP Niveau 6 Concepteur intégrateur d'infrastructures informatiques (systèmes et réseaux, applicatives, ou de sécurité) parcours Systèmes et réseaux
- CRN0802A : Titre RNCP Niveau 6 Concepteur intégrateur d'infrastructures informatiques (systèmes et réseaux, applicatives, ou de sécurité) parcours Systèmes d'information
- CRN0803A : Titre RNCP Niveau 6 Concepteur intégrateur d'infrastructures informatiques (systèmes et réseaux, applicatives, ou de sécurité) parcours Cybersécurité
- MR11602A : Master Sciences, technologies, santé mention Informatique parcours Recherche opérationnelle
- MR11603B : Master Sciences, technologies, santé mention Informatique parcours Systèmes d'information et business intelligence HTT
- MR11604A : Master Sciences, technologies, santé mention Informatique parcours Traitement de l'information et exploitation des données
- MR11605A : Master Sciences, technologies, santé mention Informatique parcours Préparation à l'agrégation en informatique
- MR11606A : Master Sciences, technologies, santé mention Informatique parcours Réseaux et objets connectés
- MR12303A : Master Sciences, technologies, santé, mention mathématiques appliquées, statistique parcours Science des données
Informations, Orientation & Inscription
Prochaines sessions de formation
Filtres :
| Centre de formation |
Semestre
2024/2025 |
Jours de formation |
Modalité | Crédits | ||
|---|---|---|---|---|---|---|
| Paris | Semestre 2 | 6 crédits (1) |
Ouverture des inscriptions le 21/08/2024 |
|||
|
Date de début des cours (*) :
* Les dates fournies sont d'ordre général à toutes les formations. |
||||||
-
-
Paris
Semestre 2
Cours hybride
-
Légende :
| Tarif (1) : |
|---|
|
Vous pouvez consulter nos tarifs ici. |
| Date de début de cours : |
Les dates fournies sont d'ordre général à toutes les formations. Les cours pour cette formation peuvent potentiellement commencer un peu plus tard dans le semestre. |
| Annuel : |
|
Il s'étend de fin septembre / début octobre à début juillet (dates indicatives, renseignez-vous auprès de votre centre). |
| Semestre 1 : |
|
Il s'étend de fin septembre / début octobre à fin janvier / début février (dates indicatives, renseignez-vous auprès de votre centre). |
| Semestre 2 : |
|
Il s'étend de fin février / début mars à début juillet (dates indicatives, renseignez-vous auprès de votre centre). |
| Cours du soir : | |
|---|---|
|
Les cours commencent le plus souvent à 18h30 dans les centres. |
|
| Cours en journée : | |
|
Se renseigner auprès du centre pour connaître les horaires. |
|
| Cours en ligne : | |
|
les cours sont diffusés sous forme de séances numériques via une plateforme d’e-learning animées et tutorées par un enseignant. Des séances de regroupement en visio sont proposées. |
|
| Classe virtuelle (Formation à distance planifiée): | |
|
L'enseignant à distance intervient en direct et en visioconférence sur la plateforme d'e-learning. Il complète son intervention par des activités interactives (exercices échanges…) |
|
| Cours en ligne hybride : | |
|
Cette modalité associe des cours en ligne tutorées et des regroupements en présentiel obligatoires. |
|
| Cours hybrides : | |
|
Cette modalité mixe des cours en présentiel (en cours du soir ou en journée) et des cours en ligne. |
|
| Cours en ligne organisés par un autre centre CNAM Régional : |
|
|
Les cours sont diffusés sous forme de séances numériques via une plateforme d'e-learning animées et tutorées par un enseignant. |
|
| Formation co-modale : | |
|
Formation proposée en présentiel et à distance en simultané. L'auditeur a la possibilité de choisir de venir sur site pour suivre l'enseignement ou bien de suivre à distance. Les cours se déroulent en semaine généralement après 18h ou le samedi. |
