 | |
| MATH0462-1 | Optimisation discrète
 |
|
| Durée : | 30h Th, 30h Pr |
|
| Crédits/ECTS : |
| ingénieur civil électricien, 3e année | | | | 6,5 |
|
| ingénieur civil informaticien, 3e année | | | | 5,5 |
|
| Master en ingénieur civil électricien, à finalité approfondie, 2e année | | Toute l'année | | 5 |
|
| Master en ingénieur civil en informatique, à finalité approfondie, 2e année | | Toute l'année | | 5 |
|
| Master en sciences informatiques, à finalité approfondie, 2e année | | Toute l'année | | 6 |
|
| Master en ingénieur civil physicien, à finalité approfondie, 2e année | | Toute l'année | | 5 |
|
|
|
| Titulaire(s) : | Quentin Louveaux |
|
| Langue : | Langue française |
|
| Aperçu général : | 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. |
|
| Objectif 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.
Dans un second temps, nous nous occuperons de problèmes que l'on peut modéliser dans des graphes. En particulier, nous verrons une série de problèmes combinatoires dans les graphes qui peuvent être résolus efficacement. Nous ferons également une courte présentation des problèmes difficiles dans les graphes.
Finalement, la troisième partie du cours concernera les techniques de résolution des problèmes en nombres entiers: principalement branch-and-bound, branch-and-cut et reformulation par les treillis. |
|
| Pré-requis : | Un cours de base en programmation linéaire est préférable. |
|
| Travaux pratiques : | Cinq séries d'exercices à réaliser individuellement sont à remettre environ toutes les trois semaines.
Un projet consiste en, au choix, la réalisation d'un programme informatique ou la lecture d'un article. Ce projet fait l'objet d'une présentation orale sous forme de séminaire. |
|
| Notes de cours : | Trois références principales sont utilisées pour ce cours:
Pour la 1e partie (et les treillis):
D. Bertsimas, R. Weismantel, Optimization over Integers. Dynamic Ideas, 2005.
Pour la 2e partie:
R. Ahuja, T. Magnanti, J. Orlin, Network flows. Prentice Hall, 1993.
Pour la 3e partie:
L. Wolsey, Integer Programming. Wiley, 1998. |
|
| Evaluation : | La série de cinq exercices compte pour 25% de la note finale.
Le projet compte pour 25% de la note finale.
Un examen oral avec préparation (éventuellement à livre ouvert) compte pour 50% de la note finale. |
|
| Remarques : | Le cours se donne au premier quadrimestre.
L'horaire est à discuter avec l'enseignant. |
|
|
| |
