Combinatorial optimization



BROCHURE

année académique

2024-2025

2025-2026

Titulaire(s) du cours

Bernard FORTZ (Coordonnateur)

Crédits ECTS

Langue(s) d'enseignement

anglais

Contenu du cours

Ce cours présente les méthodes de base pour la résolution de problèmes d'optimisation combinatoire et de programmation linéaire en variables booléennes, entières ou mixtes. Il comprend 13 chapitres intitulés (i) formulations, (ii) optimalité, relaxation et bornes, (iii) problèmes bien résolus, (iv) couplages et affectations, (v) programmation dynamique, (vi) complexité et réduction de problèmes, (vii) branch and bound, (viii) algorithmes de plans coupants, (ix) inégalités valides fortes, (x) dualité lagrangienne, (xi) algorithmes de génération de colonnes, (xii) algorithmes heuristiques, (xiii) de la théorie vers les solutions.

Objectifs (et/ou acquis d'apprentissages spécifiques)

Savoir modéliser et résoudre des problèmes d'optimisation combinatoire.

Méthodes d'enseignement et activités d'apprentissages

24 heures de cours magistral, 12h d'exercices, un projet

Références, bibliographie et lectures recommandées

WOLSEY, L. (1998). Integer Programming, Wiley.

Autres renseignements

Contacts

Martine Labbé, Campus de la Plaine Bâtiment NO Local 2.N3.215

Evaluation

Méthode(s) d'évaluation

Autre

Autre

Examen écrit d'exercices (20%), examen oral de théorie (40%) et évaluation du projet (40%)

Construction de la note (en ce compris, la pondération des notes partielles)