Advanced Algorithms for Optimization

5 crédits

30.0 h + 15.0 h

Enseignants

Schaus Pierre;

Langue
d'enseignement

Anglais

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 :

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.

La contribution de cette UE au développement et à la maîtrise des compétences et acquis du (des) programme(s) est accessible à la fin de cette fiche, dans la partie « Programmes/formations proposant cette unité d’enseignement (UE) ».

Contenu

programmation dynamique
branch and bound
programmation linéaire
relaxation Lagrangienne
génération de colonnes
recherche locale
programmation par contrainte et sat
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 dans le cadre du cours magistral sera accompagnée de travaux pratiques (assignments/micro-projets) demandant l'implémentation d'un algorithme en vue de résoudre un problème d'optimisation concret. L'évaluation des travaux sera partiellement automatisée sur base de la qualité des solutions trouvées par les algorithmes.

Modes d'évaluation
des acquis des étudiants

Une grande partie de l'évaluation est accordée aux travaux (30% des pointsrépartis sur 3 assignments). Les 70% restants seront évalués de manière classique avec un examenécrit ou oral.Les projets ne peuvent être refaits en 2e session.

Autres infos

Préalables:

LSINF1121

Faculté ou entité
en charge

INFO

Programmes / formations proposant cette unité d'enseignement (UE)

Intitulé du programme

Sigle

Crédits

Prérequis

Acquis
d'apprentissage

Master [120] : ingénieur civil en science des données

DATE2M

Master [120] : ingénieur civil en informatique

INFO2M

Master [120] en sciences informatiques

SINF2M

Master [120] en science des données, orientation statistique

DATS2M

Master [120] en science des données, orientation technologies de l'information

DATI2M