RCP104 | Optimisation en informatique

Programme

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, sous la forme d'un projet ou d'un (ou plusieurs) TP noté.

Prérequis

É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.

Objectifs

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).

Délais d'accès

Inscription 1er semestre et annuel :

• Modalité présentiel/hybride : de juillet à mi-octobre
• Modalité FOAD (100% à distance) : de juillet à mi-novembre

Inscription 2ème semestre :

• Modalité présentiel/hybride : de juillet à mi-février
• Modalité FOAD (100% à distance) : de juillet à mi-mars

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.

Modalités

Modalités pédagogiques

Pédagogie qui combine apports académiques, études de cas basées sur des pratiques professionnelles et expérience des élèves. Équipe pédagogique constituée pour partie de professionnels. Un espace numérique de formation (ENF) est utilisé tout au long du cursus.

Modalités de validation

Examen noté sur 16.
Projet ou TP noté sur 4.

Planning

Tarif

Si vous êtes demandeur d'emploi et que vous cotisez à AG2R La Mondiale, vous pouvez bénéficier d'un financement : 4 UE gratuites par an (à raison de 2 UE gratuites par semestre).

Si aucun dispositif de financement ne peut être mobilisé, nous proposons à l’élève une prise en charge partielle de la Région Nouvelle-Aquitaine avec un reste à charge. Ce reste à charge correspond au tarif réduit indiqué ci-dessus et est à destination des salariés ou demandeurs d’emploi.

Passerelles

• CYC9101A - Diplôme d'ingénieur Architecture et ingénierie des systèmes et des logiciels (AISL)
• CYC9104A - Diplôme d'ingénieur Informatique, réseaux, systèmes et multimédia (IRSM)
• CYC9105A - Diplôme d'ingénieur Systèmes d'information
• CYC9106A - Diplôme d'ingénieur Cybersécurité
• CPN8401A - Titre RNCP Niveau 6 Concepteur en architecture informatique Réseaux et systèmes
• CPN8402A-1 - Titre RNCP Niveau 6 Architecture Ingénierie des Systèmes et des Logiciels (AISL)
• CPN8402A-2 - Titre RNCP Niveau 6 Systèmes d'information (ISI)

Avis des auditeurs

Fiche synthétique au format PDF