 | | |
| MATH0462-1 | Discrete optimization
|
|
| Durée : | 30h Th, 20h Pr, 25h Proj. |
|
| Nombre de crédits : |
| Master en ingénieur civil biomédical, à finalité approfondie, 1re année | | 5 |
|
| Master en ingénieur civil biomédical, à finalité approfondie, 2e année | | 5 |
|
| Master en ingénieur civil électricien, à finalité approfondie, 2e année | | 5 |
|
| Master en ingénieur civil électricien, à finalité approfondie, 2e année | | 5 |
|
| Master en ingénieur civil en informatique, à finalité approfondie, 1re année | | 5 |
|
| Master en sciences informatiques, à finalité approfondie, 1re année | | 5 |
|
| Master en sciences informatiques, à finalité approfondie, 2e année | | 5 |
|
| Master en ingénieur civil physicien, à finalité approfondie, 2e année | | 5 |
|
| Master en ingénieur civil en informatique, à finalité spécialisée en gestion, 1re année | | 5 |
|
| Master en sciences informatiques, à finalité spécialisée en gestion, 1re année | | 5 |
|
| Master en sciences informatiques | | 6 |
|
| Master en sciences mathématiques, à finalité spécialisée en informatique, 2e année | | 6 |
|
|
|
| Nom du professeur : | Quentin Louveaux |
|
Langue(s) du cours :
|
| Langue anglaise |
|
Organisation et évaluation :
|
| Enseignement au premier quadrimestre, examen en janvier |
|
Contenus du cours :
|
| Considérons un représentant commercial d'une entreprise qui doit visiter 20 clients potentiels dans 20 villes différentes. Une question naturelle que peut se poser le représentant est de savoir dans quel ordre il va visiter les clients afin de minimiser la distance parcourue. Ce problème célèbre mieux connu sous le nom du problème de voyageur de commerce est l'exemple typique du problème d'optimisation discrète. On dispose d'un nombre fini de solutions possibles (ici les 20! possibles permutations des villes) et pourtant il est pratiquement impossible de les tester toutes. Si on pouvait en tester un milliard par seconde, dans ce cas-ci il nous faudrait environ 77 ans pour toutes les parcourir.
Le problème de voyageur de commerce n'est qu'un exemple parmi tant d'autres de problèmes d'optimisation discrète. En effet, en particulier les problèmes où des décisions binaires (oui ou non par exemple) doivent se prendre sont légion dans les applications pratiques.
Au niveau du contenu du cours, dans un premier temps nous allons nous concentrer sur la modélisation de problèmes discrets soous forme de programmes linéaires en nombres entiers. Nous discuterons quelques principes pour formuler des problèmes et nous attarderons à ce qui fait une bonne formulation.
Ensuite, la deuxième partie du cours concernera les techniques de résolution des problèmes en nombres entiers: principalement branch-and-bound, branch-and-cut, relaxation lagrangienne, programmation dynamique, et algorithmes d'approximation. Nous discutons également quelques cas particuliers de problèmes discrets très importants et que l'on peut résoudre efficacement: les problèmes de flot, d'affectation. Enfin, la programmation par contraintes et l'optimisation non linéaire discrète sera brièvement abordée. |
|
Acquis d'apprentissage (objectifs d'apprentissage) du cours :
|
| A l'issue de ce cours, l'étudiant
- pourra formuler un problème réel comme un problème d'optimisation en nombres entiers
- pourra comparer deux formulations d'un même problème
- connaîtra les principales méthodes pour résoudre les problèmes d'optimisation en nombres entiers.
|
|
Prérequis et corequis / Modules de cours optionnels recommandés :
|
| Un cours de base en programmation linéaire est préférable. |
|
Activités d'apprentissage prévues et méthodes d'enseignement :
|
| Des séances d'exercices en salle sont organisées chaque semaine.
Un projet consiste en la réalisation d'un programme informatique. |
|
Mode d'enseignement (présentiel ; enseignement à distance) :
|
| Supports du cours et informations générales: http://www.montefiore.ulg.ac.be/%7Esmathieu/milp.html |
|
Lectures recommandées ou obligatoires et notes de cours :
|
| Deux références principales sont utilisées pour ce cours:
Pour la 1e partie (et les algorithmes d'approximation):
D. Bertsimas, R. Weismantel, Optimization over Integers. Dynamic Ideas, 2005.
Pour la 2e partie:
L. Wolsey, Integer Programming. Wiley, 1998. |
|
Modalités d'évaluation et critères :
|
| Le projet compte pour 1/3 de la note finale.
Un examen écrit d'exercices compte pour 2/3 de la note finale.
La note est une moyenne géométrique. |
|
Stage(s) :
|
| |
|
Remarques organisationnelles :
|
| Le cours se donne au premier quadrimestre. |
|
Contacts :
|
| |
|
