% INF889B — Algorithmes d'optimisation combinatoire % UQAM — Département d'informatique % Plan de cours — Hiver 2020 * Horaires, locaux et enseignants: Responsable(s) du cours ======================= Coordination ------------ Blondin Massé, Alexandre PK-4525 poste 5516 Description du cours ==================== Objectifs --------- Se familiariser avec les méthodes d'optimisation combinatoire exactes, approximatives et adaptatives. Connaître leurs avantages, leurs limites, être en mesure de les implémenter et d'évaluer leur performance. Sommaire du contenu ------------------- Modélisation d'un problème d'optimisation combinatoire. Optimisation exacte: solution naïve, séparation et évaluation progressive, algorithmes paramétrés. Optimisation convexe: programmes linéaires, algorithme du simplexe, théorie de la dualité, programmation linéaire en nombres entiers. Méthodes approximatives et métaheuristiques: recherche locale, recuit simulé, recherche taboue. Méthodes bio-inspirées: algorithmes évolutionnaires, colonies de fourmis, etc. Optimisation par apprentissage: survol des méthodes d'apprentissage automatique, intégration d'apprentissage dans des algorithmes d'optimisation combinatoire. Contenu du cours ================ Le cours comportera 12 à 13 séances magistrales, dont le contenu se divise en 7 chapitres: 1. **Chapitre 1**: Introduction. Présentation du cours, exemples. 2. **Chapitre 2**: Modélisation, algorithmes, espace combinatoire, ordre de grandeur, complexité, expérience. 3. **Chapitre 3**: Optimisation exacte. Solution naïve, séparation et évaluation progressive, algorithmes paramétrés. 4. **Chapitre 4**: Optimisation convexe. Programmation linéaire, algorithme du simplexe, théorie de la dualité, programmation linéaire en nombres entiers. 5. **Chapitre 5**: Approximation et méta-heuristiques. Recherche locale, recuit simulé, recherche taboue. 6. **Chapitre 6**: Méthodes bio-inspirées. Algorithmes évolutionnaires, colonies de fourmis, essaims de particules. 7. **Chapitre 7**: Optimisation avec apprentissage. Survol des méthodes d'apprentissage automatique, intégration d'apprentissage dans des algorithmes d'optimisation combinatoire. Lors des autres séances, les étudiants et les étudiantes devront présenter des articles scientifiques liés à des sujets d'actualité en optimisation combinatoire, ainsi que sur des problèmes d'optimisation qu'ils rencontrent dans leurs travaux de recherche ou qu'ils souhaitent approfondir. Modalités d'évaluation ====================== L'évaluation des apprentissages sera faite à partir des éléments suivants. Revue de littérature (30%) -------------------------- Dans un premier temps, l'étudiant ou l'étudiante devra identifier un article scientifique du domaine et en faire une brève présentation écrite en une page (5%). Ensuite, il ou elle devra faire une présentation orale de cet article devant la classe, pour une durée d'environ 20 minutes (15%). Finalement, après la présentation, un résumé écrit (dans le style « fiche de lecture ») d'environ 2 pages devra être remis (10%). Projet de session (40%) ----------------------- L'étudiante ou l'étudiant devra d'abord choisir son sujet et en faire une courte description écrite (5%). Ensuite, il ou elle devra faire une présentation orale de son projet devant le classe, pour une durée d'environ 25 minutes (20%). Finalement, un rapport final d'environ 10 pages, semblable à un article scientifique, devra être remis après la présentation (15%). Devoirs (30%) ------------- Trois devoirs écrits (10% chacun) devront être complétés pendant la session. Médiagraphie ============ - Marek Cygan et al., *Parameterized Algorithms*, Springer, 2016, [disponible en ligne](https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf) - Teofilo F. Gonzalez, *Handbook of Approximation Algorithms and Metaheuristics*, 2007. - Fred Glover et Gary A. Kochenberger, *Handbook of metaheuristics*, 2003, ISBN 978-1-4020-7263-5. - Vašek Chvátal, *Linear programming*, W. H. Freeman and Company, New York, 1983, 478 pp. - Stephen Boyd et Lieven Vandenberghe, *Convex optimization*, [notes disponibles en ligne](https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf) - Richard S. Sutton et Andrew G. Barto, *Reinforcement Learning: An Introduction*, second edition, MIT Press, Cambridge, MA, 2018, [disponible en ligne](http://incompleteideas.net/book/RLbook2018.pdf)