Advanced Algorithms for Optimization

Enseignants

Schaus Pierre;

Langue
d'enseignement

Anglais
> Facilités pour suivre le cours en français

Thèmes abordés

• exploration d'arbres de recherche
• branch and bound
• relaxation (lagrangienne) et calcul de bornes
• la recherche locale
• la programmation mathématique
• la programmation par contrainte
• algorithmes de graphes,
• les recherches à voisinage large
• la programmation dynamique
• les algorithmes gloutons et algorithmes approchés
• l'optimisation multicritères
• l'optimisation sans dérivée
• comparaison d'algorithmes

Ces méthodes seront appliquées sur des problèmes réels de type routing de véhicules, rostering et confection d' horaires, design de réseau, ordonnancement et scheduling, etc.

Acquis
d'apprentissage

A la fin de cette unité d’enseignement, l’étudiant est capable de :
1	Eu égard au référentiel AA du programme « Master ingénieur civil en informatique », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants : INFO1.1-3 INFO2.3-5 INFO5.3-5 INFO6.1, INFO6.4 Eu égard au référentiel AA du programme « Master [120] en sciences informatiques », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants : SINF1.M4 SINF2.3-5 SINF5.3-5 SINF6.1, SINF6.4 Les étudiants ayant suivi avec fruit ce cours seront capables de expliquer les algorithmes de résolution des problèmes d'optimisation discrets en les décrivant précisément, en précisant les problèmes qu'ils permettent de résoudre, en indiquant leurs avantages, inconvénients et limites (temps de calcul, exactitude, problèmes de passage à l'échelle, etc), identifier les algorithmes qui s'appliquent à un problème d'optimisation discret auquel on est confronté et faire un choix argumenté parmi ceux-ci, implémenter les algorithmes permettant de résoudre des problèmes d'optimisation discrets.

Contenu

• programmation dynamique
• branch and bound
• programmation linéaire
• relaxation Lagrangienne
• génération de colonnes
• recherche locale
• programmation par contrainte
• algo de graphes: problème de max flow
• comparaison d'algorihtmes d'optimisation

Utilisation de ces méthodes sur des problèmes réels: tournées de véhicules, ordonnancement, confection d'horaire, design de réseau, etc.

Méthodes d'enseignement

La présentation des algorithmes sera soit proposée sous forme de cours magistraux, de vidéos ou de lecture et sera accompagnée de travaux pratiques (devoirs/micro-projets) sollicitant la mise en œuvre d'algorithmes pour résoudre un problème pratique d'optimisation et la rédaction de rapports.

Modes d'évaluation
des acquis des étudiants

Pour la première session, la note globale du cours est uniquement basée sur les notes des projets informatiques, soumis et évalués au cours du semestre.
Les projets ne sont pas réévalués pour la deuxième session et ne peuvent pas être soumis à nouveau.
Les notes des projets sont conservées telles quelles représentant 50% et les 50% restants sont évalués par un examen écrit ou, le cas échéant, sur ordinateur.
Les projets sont individuels. Cela signifie que tout code source d'un projet
- copié ou inspiré par celui d'un autre étudiant, ou
- copié ou inspiré d'un code source trouvé sur internet ou une autre source,
se traduira par une note nulle pour l'étudiant aux projets et à l'examen
Les mêmes conséquences s'appliqueront à un étudiant qui partage volontairement son code ou le met à la disposition d'autres étudiants.

Autres infos

Préalables: un background solide en algorithmique et structure de données (par exemple acquis via le cours LINFO1121) et un bonne maitrise du langage Java

Ressources
en ligne

https://moodleucl.uclouvain.be/course/view.php?id=8280

Faculté ou entité
en charge

INFO