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

Ce cours présente une série de techniques pour des solutions exactes et approximatives aux problèmes d'optimisation combinatoire. Parmi les techniques :

• 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
• A* et ses variantes pour l'optimisation
• comparaison d'algoritthmes 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

Janvier:
Pour la première session, la note globale du cours est uniquement basée sur les notes des projets informatiques, soumis et évalués pendant le semestre.
Août:
Pour la deuxième session, les projets précédemment soumis ne seront pas réévalués et ne pourront pas être resoumis. La note des projets comptera sur 10 points en seconde session et un nouveau projet sera proposé sur 10 points pour faire remonter la note. Ce nouveau projet sera un projet de programmation individuel. Ce projet nécessitera un rapport écrit, et, si le professeur le juge nécessaire, un entretien sur le projet pourra également être organisé pour vérifier que tous les concepts théoriques sont bien compris.
Bonus
Un concours d’optimisation sera proposé durant le quadrimestre. Selon le classement de l’étudiant, celui-ci pourra obtenir 0, 1, 2, 3, 4 ou 5 points. Un étudiant qui obtient X points aura donc la note finale suivante : (score_sur_20 / 20 * (20 - X) + X). Une note de zéro au concours n’entraîne donc aucune perte de points sur la note finale, mais une note de 5 peut vous permettre d’améliorer votre score. En effet, en supposant que vous obteniez 12/20 au projet et 5 points au concours, vous atteindrez la note finale de 12/20 * 15 + 5 = 14/20.
Utilisation de l'IA générative dans les devoirs du cours (# Source : Rédigé avec l'aide de ChatGPT et des Prof. Schaus & Dupont pour la formulation)
Les projets sont individuels (aucun échange de code n'est toléré) . Néanmoins, dans ce cours, nous reconnaissons l'évolution de la technologie et les avantages potentiels de l'utilisation des outils d'IA générative dans le processus de programmation. Cependant, l'honnêteté académique et l'originalité restent primordiales. À cet effet :

• Utilisation de l'IA générative : Les étudiants sont autorisés à utiliser les outils d'IA générative pour les aider dans leurs devoirs. Ces outils peuvent fournir de l'inspiration, suggérer des approches de codage ou aider à résoudre des problèmes.
  
• Travail original : Bien que l'IA puisse être un outil, elle ne doit pas être le seul auteur de votre devoir. Votre soumission doit être principalement votre propre travail. Copier et coller directement des solutions issues des résultats de l'IA sans compréhension ni modification est déconseillé. De même, collaborer avec d'autres étudiants est une partie précieuse du processus d'apprentissage, mais copier directement le travail d'un autre étudiant est considéré comme du plagiat.
  
• Indication de la source : Chaque fois que vous utilisez l'IA générative pour aider dans votre devoir, vous devez l'indiquer en fournissant un bref commentaire dans votre code sur la manière dont l'IA a été utilisée. Par exemple:
  # IA utilisée pour suggérer une optimisation pour cette boucle. 
  

     for i in range(10): ...
Le non-respect de ces directives peut entraîner une réduction des notes ou d'autres sanctions académiques.
Les mêmes conséquences s'appliqueront à un étudiant qui partage volontairement son code ou le rend disponible à d'autres étudiants (y compris en partageant votre code sur un dépôt public ou privé). Si le professeur le juge nécessaire, un entretien sur les projets pourra également être organisé.

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://moodle.uclouvain.be/course/view.php?id=1474

Faculté ou entité
en charge

> INFO