Combinatorial optimization

5.00 crédits

30.0 h + 22.5 h

Enseignants

Hendrickx Julien; Nunes Grapiglia Geovani;

Langue
d'enseignement

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

Préalables

Bases de programmation linéaires (dont dualité et algorithme du simplexe) telles qu'enseignées dans LINMA2471 (Modèles et méthodes d'optimisation).

Thèmes abordés

Dans ce cours nous examinons des méthodes différentes pour résoudre un problème d'optimisation avec des indivisibilités, ou des décisions oui/non concernant le choix d'une arête dans un graphe, l'achat d'une machine, l'utilisation d'un dépot, etc. De tels problèmes sont posés dans la construction d'un horaire de train ou d'avion, d'un tour dans un graphe, d'un plan de génération journalier d'électricité, etc. La théorie concerne les polyèdres, matrices, graphes et certains aspects de la complexité. Les approches algorithmiques étudiées sont l'énumeration implicite et les méthodes de coupes (branch-and-cut), relaxation lagrangienne, programmation dynamique et les algorithmes d'approximation.

Acquis
d'apprentissage

A la fin de cette unité d’enseignement, l’étudiant est capable de :

Eu égard au référentiel AA, ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :

AA 1 : 1,2

Plus précisément, au terme du cours, l'étudiant sera capable de :

formuler différents problèmes combinatoires sous forme de programmes en nombre entiers
explorer différentes formulations pour un même problème, afin d'en faciliter la résolution
borner (inférieurement et supérieurement) la solution d'un programme en nombre entier
reconnaître des programmes en nombres entiers qui sont faciles à résoudre (en temps polynomial)
reconnaître des programmes en nombres entiers qui sont difficiles à résoudre (NP-complet)
appliquer des techniques heuristiques pour résoudre ces derniers de façon approchée

Acquis d'apprentissage transversaux :

usage de Matlab ou autres logiciels pour la résolution de problèmes de taille moyenne

Contenu

Formulation de problèmes d'optimisation combinatoire et de programmation en nombre entiers
Techniques pour trouver des bornes sur la valeur optimale et en déduire l'optimalité le cas échéant
Comment reconnaître et résoudre certains problèmes faciles sur les flots, les arbres, les couplages et les assignations
Introduction à la distinction entre problèmes faciles et difficiles : la NP-complétude
Enumération intelligente: le branch-and-bound
La relaxation lagrangienne
Introduction aux plans de coupe
Méthodes heuristiques pour trouver des solutions approchées rapidement

Méthodes d'enseignement

Cours Ex cathedra, éventuellement complémenté de découvertes personnelles de partie de la matière par les étudiants, et séances d’exercices supervisées. Ces activités ont lieu en salle, ou en co-modal en fonction des contraintes pratiques et du nombre d’étudiants inscrit.
Les étudiants réalisent également un ou plusieurs exercices à la maison avec utilisation d'un logiciel.

Modes d'évaluation
des acquis des étudiants

85% de la note finale est déterminée par un examen écrit, et 15% par des devoirs (entre 1 et 3 ensembles de problèmes à résoudre durant le semestre).

Ressources
en ligne

Page Moodle du cours

Bibliographie

Integer Programming, L.A. Wolsey, Wiley, New York 1998.

Support de cours

Documents sur la page Moodle / Documents on the Moodle page

Faculté ou entité
en charge

MAP

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

Intitulé du programme

Sigle

Crédits

Prérequis

Acquis
d'apprentissage

Master [120] en sciences mathématiques

MATH2M

Master [120] : ingénieur civil en informatique

INFO2M

Master [120] en sciences informatiques

SINF2M

Master [120] : ingénieur civil en mathématiques appliquées

MAP2M

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

DATE2M

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

DATI2M