Durée
30h Th, 20h Pr, 25h Proj.
Nombre de crédits
Enseignant
Langue(s) de l'unité d'enseignement
Langue anglaise
Organisation et évaluation
Enseignement au deuxième quadrimestre
Horaire
Unités d'enseignement prérequises et corequises
Les unités prérequises ou corequises sont présentées au sein de chaque programme
Contenus de l'unité d'enseignement
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 sous 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 et d'affectation.
Acquis d'apprentissage (objectifs d'apprentissage) de l'unité d'enseignement
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.
- pourra reconnaître un problème d'optimisation discrète qui peut être résolu en temps polynomial
Savoirs et compétences prérequis
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)
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
L'examen est un examen oral de théorie et d'exercices.
'examen compte pour 2/3 de la note finale. Le projet compte pour 1/3 de la note finale.
Si le projet n'est pas soumis en première session, celui-ci doit toujours être soumis en deuxième session. L'énoncé reste le même. L'absence de soumission de projet résulte en une note d'absence.
Stage(s)
Remarques organisationnelles
Le cours se donne au second quadrimestre.
Contacts
Adaptation des engagements pédagogiques suite à la pandémie de COVID-19 pour la session de mai-juin
Méthodes d'apprentissage mises en œuvre : enseignement à distance
Des vidéos des cours et des séances d'exercice sont mises à disposition des étudiants de même que les annotations des slides et des exercices.
Matière de l'évaluation
La matière est celle enseignée en présentiel et lors des cours enregistrés.
Méthodes d'évaluation
L'examen est un oral en vidéoconférence sans préparation et à livre ouvert.
L'examen se compose d'une question de théorie tirée au sort dans la liste disponible dans le répertoire dox. Ensuite un exercice est donné à l'étudiant qui dispose d'une dizaine de minutes pour résoudre/démarrer l'exercice, faire une photo de ses notes et l'envoyer par mail à l'enseignant. Si l'exercice n'est pas fini après 10 minutes, l'étudiant explique oralement comment le terminer. Une liste de thématiques d'exercices sera rendue disponible sur le répertoire dox également.
L'examen dure vingt minutes au total (5 minutes pour la théorie, 10 minutes de préparation de l'exercice et 5 minutes de discussion de l'exercice).
Contact
q.louveaux@uliege.be
Adaptation des engagements pédagogiques suite à la pandémie de COVID-19 pour la session août-sept
Matière de l'évaluation
Méthodes d'évaluation (et plateforme utilisée)
Comme en juin.
L'examen est un oral en vidéoconférence sans préparation et à livre ouvert.
L'examen se compose d'une question de théorie tirée au sort dans la liste disponible dans le répertoire dox. Ensuite un exercice est donné à l'étudiant qui dispose d'une dizaine de minutes pour résoudre/démarrer l'exercice, faire une photo de ses notes et l'envoyer par mail à l'enseignant. Si l'exercice n'est pas fini après 10 minutes, l'étudiant explique oralement comment le terminer. Une liste de thématiques d'exercices sera rendue disponible sur le répertoire dox également.
L'examen dure vingt-cinq minutes au total (5-10 minutes pour la théorie, 10 minutes de préparation de l'exercice et 5-10 minutes de discussion de l'exercice).