% INF889B — Algorithmes d'optimisation combinatoire % UQAM — Département d'informatique % Plan de cours — Automne 2022 * Horaires, locaux et enseignants: Enseignement ============ Avellaneda, Florent PK-4435 Groupes: 020 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 de décision et d'optimisation combinatoire. Résolution exacte: solution naïve, séparation et évaluation progressive, algorithmes paramétrés, solveurs de contraintes. 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 4 chapitres: 1. **Chapitre 1**: Problemes de décision 2. **Chapitre 2**: Optimisation exacte 3. **Chapitre 3**: Optimisation approché 4. **Chapitre 4**: Optimisation par apprentissage 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 ============ Obligatoires : \* Transparents et annexes disponible sur le site web du cours Utiles : \* Francesca Rossi et al., *Handbook of Constraint Programming*., Elsevier, 2006. \* Armin Biere et al., *Handbook of satisfiability*, IOS press, 2009. \* 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)