Descriptif des cours
UE Obligatoires
- Graphes et applications
Graphes et applications
Ects : 3
Enseignant responsable :
Volume horaire : 15
Description du contenu de l'enseignement :
Cet enseignement vise à montrer la richesse des concepts et outils issus de la théorie des graphes pour la modélisation et la résolution de nombreux problèmes concrets. Outre l’étude d’algorithmes et de leurs fondements théoriques, on montrera comment les concepts issus des graphes permettent de modéliser, de façon plus ou moins directe, certaines situations concrètes en les ramenant par exemple à un des problèmes classiques ou à un problème voisin.
Concepts de base de théorie des graphes, Etude de problèmes classiques de couplage, couverture, stable Différents problèmes de flot Problèmes de coloration Applications
Bibliographie-lectures recommandées
R. Ahuja, T. Magnanti and J. Orlin. Networks Flows, Theory, Algorithms, Applications. Prentice Hall, Englewood Cliffs, New Jersey (1993). M. Gondran et M. Minoux. Graphes et algorithmes, Eyrolles, 2009, 4e édition. L. Lovasz, M. D. Plummer, Matching Theory, Elsevier Science Ltd, 1986
- Programmation Mathématique
Programmation Mathématique
Ects : 3
Enseignant responsable :
Volume horaire : 15
Description du contenu de l'enseignement :
This course delves into the realm of Mathematical Programming, exploring its applications in solving real-world problems across diverse domains. Various concrete problems find formulation through linear and integer linear programming. The primary objective of this module is to scrutinize the modeling and resolution methods for such problems, grounded in linear programming and integer programming. Here is a possible list of contents, which might change according to the current trends or the lecturer's inclinations.
- Ingredients of combinatorial optimization
- Linear programming
- Solution methods: Graphical solution, Simplex algorithm
- Duality
- Integer programming
- Solution methods: Branch-and-Bound, Cutting planes, Branch-and-Cut
- Perfect formulations
Compétences à acquérir :
At the end of this course, students will have developed expertise in modeling and solving real-world and combinatorial optimization problems through mathematical programming. They will be able to formulate and solve concrete challenges using methods such as linear programming and integer programming, as well as advanced optimization techniques.
Mode de contrôle des connaissances :
A final exam on paper
Bibliographie-lectures recommandées
- Integer Programming, Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli. Springer (2014).
- Theory of Linear and Integer Programming, Alexander Schrijver. Wiley (1998).
- Modélisation des préférences – aide multicritère à la décision
Modélisation des préférences – aide multicritère à la décision
Ects : 3
Enseignant responsable :
Volume horaire : 15
Description du contenu de l'enseignement :
Ce cours vise à présenter les principaux concepts et méthodes utiles pour la modélisation des préférences et l'aide multicritère à la décision.
Modélisation des préférences (langage de la modélisation des préférences, principales structures, représentation numérique, extensions) Introduction à quelques procédures de vote Théorie de l’utilité multiattribut (résultats de base, procédures directes, procédures indirectes : méthode UTA, Intégrale de Choquet) Méthodes de surclassement: (ELECTRE TRI) Méthodes d'élicitation des paramètres
Compétences à acquérir :
Maitrise des principes et outils de modélisation des préférences
Mode de contrôle des connaissances :
Examen écrit de 2h
Bibliographie-lectures recommandées
Bibliographie B. Roy et D. Bouyssou, Aide Multicritère à la Décision: Méthodes et Cas. Economica, Paris, 1993. B. Roy, Méthodologie multicritère d ’ aide à la décision, Economica, Paris, 1985 Vincke Ph. (1989), L'Aide Multicritère à la Décision, Editions Editions Ellipses, Bruxelles. Roubens, M. and Ph. Vincke (1985), Preference Modelling, Lecture Notes in Economics and Mathematical Systems n° 250, Springer Verlag, Berlin. Sen A.K. (1986), Social choice theory, in K.J. Arrow and M.D. Intriligator (eds.), Handbook of Mathematical Economics III, North-Holland, Amsterdam, 1073-1181 French S. (1993) Decision Theory - An Introduction to the Mathematics of Rationality, Ellis Horwood, chapitre 4. D. Bouyssou, Th. Marchant, M. Pirlot, P. Perny, A. Tsoukiàs, et Ph. Vincke. Evaluation and decision models: a critical perspective, Kluwer 2000.
- Modélisation en Aide à la décision – Recherche Opérationnelle
Modélisation en Aide à la décision – Recherche Opérationnelle
Ects : 3
Enseignant responsable :
Volume horaire : 15
Description du contenu de l'enseignement :
Le cours vise à présenter des modélisations originales de différents problèmes concrets de décision. Il s'agit de développer les aptitudes des étudiants à élaborer et mettre en œuvre des modèles pertinents face à une situation de décision.
Concept de modèle en aide à la décision. Modèle des solutions et modèle des préférences. Description du processus de modélisation et de ses différentes phases. Présentation de modélisations non triviales de problèmes de décision utilisant divers cadres de modélisation (graphes, programmation linéaire, multicritère,...). Utilisation de variables 0-1 en programmation linéaire Présentation d'outils de modélisation et de résolution (modeleurs et solveurs).
Pré-requis recommandés :
Connaissance des algorithmes classiques de graphe (plus court chemin, flots,...) et de Programmation Linéaire.
Compétences à acquérir :
- Etre capable de modéliser une situation décisionnelle concrète
- Maîtriser différents cadres de modélisation (graphes, PL)
- Mise en œuvre informatique
Bibliographie-lectures recommandées
Bibliographie H.P. Williams. Model building in mathematical programming. J. Wiley, New York, 2013. 5ème edition Ph. Vallin et D. Vanderpooten. Aide à la décision : une approche par les cas. Ellipses, Paris, 2002., 2ème édition D. Vanderpooten « Modelling in decision aiding ». In D. Bouyssou, E. Jacquet-Lagrèze, P. Perny, R. Slowinski, D. Vanderpooten, and Ph. Vincke (eds), Aiding Decisions with Multiple Criteria: Essays in Honour of Bernard Roy, pages 195 – 210. Kluwer, 2001.
- Modèles industriels et de conception
Modèles industriels et de conception
Ects : 3
Enseignant responsable :
- Michel NAKHLA
- Michel NAKHLA
Volume horaire : 24
Description du contenu de l'enseignement :
Cet enseignement vise à présenter les modèles industriels de production et de conception. Il est d'abord centré sur les différents problèmes de rationalisation industrielle. Sont étudiées différentes catégories de modèles et leurs techniques actuelles de résolution ainsi que les situations où ces problèmes se posent. Par ailleurs sont présentés les principaux systèmes de production : gestion des flux, planification, outils assistés par ordinateur,... et leur évolution face à un monde industriel dominé davantage aujourd'hui par des stratégies de conception et d'innovation. L'accent est principalement mis sur les conditions d'applicabilité de ces techniques et l'on distinguera les modèles basés sur le raisonnement et ceux basés sur l'organisation.
Bibliographie-lectures recommandées
Bibliographie M. Nakhla : L ’ essentiel du management industriel, Dunod 2009, 2ème Ed JC. Moisdon, M. Nakhla : RO : Méthodes d ’ optimisation en gestion, presses des mines, 2010 A. Hatchuel, P. Lemasson, B. Weil : Processus d ’ innovation, Hermes 2006
Enseignements de l'option DÉCISION
- Décision dans l'incertain et modèles décisionnels
Décision dans l'incertain et modèles décisionnels
Ects : 3
Enseignant responsable :
Volume horaire : 15
Description du contenu de l'enseignement :
Curriculum:
* Introduction : concepts of uncertainty, risk, and preference
* EU and SEU models and attitudes towards risk.
* Descriptive limits of EU and extensions RDU, CEU, WEU, and SSB.
* Sequential decision making, graphical models, Bellman optimality principle, consequentialist and resolute choice approachs.
* MDPs and an introduction to Reinforcement Learning.
* Classic decision criteria for decision making under uncertainty (Wald, Hurwicz, Laplace, …).
* Elicitation/Learning of decision models.
Contenu :
* Introduction : concepts d'incertitude et de risque, préférence
* Modèles EU, SEU et attitudes vis-à-vis du risque.
* Limites descriptives de EU et extensions RDU, CEU, WEU, et SSB.
* Décision séquentielle, modèles graphiques, principe d’optimalité de Bellman, approches conséquentialistes et de choix résolus.
* PDMs et une introduction à l'apprentissage par renforcement.
* Critères classiques de la décision dans l'incertain (Wald, Hurwicz, Laplace, …).
* Élicitation/Apprentissage des modèles décisionnels.
Pré-requis recommandés :
An introduction to decision theory.
Compétences à acquérir :
Objectives: Most economic decisions are taken in an uncertain environment, in which the consequences of decisions are not known with certainty, such as investment or insurance decisions. This course aims to introduce the fundamental concepts of decision theory in an uncertain environment, as well as classical resolution models.
Objectifs : La plupart des décisions économiques se prennent dans un environnement incertain, dans lequel les conséquences des décisions ne sont pas connues avec certitude, comme par exemple des décisions d'investissement ou d'assurance. Ce cours vise à présenter aux étudiants les concepts fondamentaux de la théorie de la décision en environnement incertain, ainsi que les modèles classiques de résolution.
Mode de contrôle des connaissances :
A 2-hour written exam.
Bibliographie-lectures recommandées
* von Neumann, John and Oskar Morgenstern,Theory of Games and Economic Behaviour, Princetown University Press, 1947. * Savage, Leonard J., The Foundations of Statistics, Dover, 1954. * Puppe, C., Distorted probabilities and choice under risk (Vol. 363). Springer Science & Business Media, 1991. * Barbera, S., Hammond, P.J., & Seidl, C. Editors, Handbook of Utility Theory: Volume 2: Extensions. Springer Science & Business Media, 1998. * Barbera, S., Hammond, P.J., & Seidl, C. Editors, Handbook of Utility Theory: Volume 1: Principles. Springer Science & Business Media, 1998.
- Optimisation multiobjectifs
Optimisation multiobjectifs
Ects : 3
Enseignant responsable :
Volume horaire : 15
Description du contenu de l'enseignement :
Ce cours vise à présenter les principaux concepts, résultats et méthodes en optimisation multiobjectifs en général et en optimisation combinatoire multiobjectifs en particulier. On s’intéresse à déterminer, de façon exacte ou approchée, soit l’ensemble des solutions efficaces, soit une solution de meilleur compromis selon les préférences d’un décideur.
Motivation, Concepts fondamentaux (espace des décisions et espace des critères, solutions efficaces, points non dominés...), Intérêt et limites des fonctions d'agrégation classiques pour déterminer une solution de meilleur compromis (Somme pondérée, Tchebychev, point de référence,...) Optimisation combinatoire multiobjectifs – Difficultés spécifiques (intraitabilité..) Méthodes exactes d'énumération de l'ensemble des solutions efficaces (méthodes génériques, méthodes spécifiques) Méthodes approchées avec garantie Approches générales pour la détermination d'une solution de meilleur compromis
Compétences à acquérir :
- Maîtriser les concepts et algorithmes principaux en optimisation multiobjectif
Bibliographie-lectures recommandées
Bibliographie M. Ehrgott, Multicriteria Optimization, Springer, 2005, 2nd edition. Steuer, R. 1985. Multiple Criteria Optimization: Theory, Computation and Application. New York: John Wiley and Sons. Vanderpooten, D. Multiobjective Programming: Basic Concepts and Approaches. In R. Slowinski and J. Teghem, editors, Stochastic versus Fuzzy Approaches to Multiobjective Mathematical Programming under Uncertainty, pages 7-22, 1990. Kluwer Academic, Dordrecht.
- Robustesse en Recherche Opérationnelle et Aide à la Décision
Robustesse en Recherche Opérationnelle et Aide à la Décision
Ects : 3
Enseignant responsable :
- Hassan AISSI
Volume horaire : 15
Description du contenu de l'enseignement :
En RO-AD, le qualificatif « robuste » se rapporte à une aptitude à résister à des « à peu près » et à des « zones d’ignorances » afin de se protéger d’impacts jugés regrettables tels des dégradations de propriétés qui devaient être préservées. Les solutions optimales qui découlent des modèles classiques de la RO ne possèdent pas nécessairement cette aptitude. Ce cours vise donc à introduire des modèles permettant de répondre à cette préoccupation.
Introduction des concepts de base et illustration de la préoccupation de robustesse à travers des exemples. Etude des modèles classiques : critères min-max et min-max regret. Etude du modèle de Bertsimas et Sim. Etude du modèle basé sur la programmation multi-niveaux.
Bibliographie-lectures recommandées
Bibliographie B. Roy, Robustness in operational research and decision aiding: A multi-faceted issue, European Journal of Operational Research 200(3), 629-638, 2010 H. Aissi, B. Roy, Robustness in Multi-criteria Decision Aiding, in Trends in Multiple Criteria Decision Analysis, M. Ehrgott, J.R. Figueira, S. Greco Ed., Springer, 87-121, 2010 H. Aissi, C. Bazgan, and D. Vanderpooten, "Min – max and min – max regret versions of combinatorial optimization problems: A survey", European Journal of Operational Research, 197(2), 427-438, 2009.
- Théorie de la décision algorithmique et choix social computationnel
Théorie de la décision algorithmique et choix social computationnel
Ects : 3
Enseignant responsable :
- STEPHANE AIRIAU
Volume horaire : 15
Description du contenu de l'enseignement :
De nombreux contextes de décision individuelle ou collective font intervenir des problèmes algorithmiquement difficiles, soit en raison de la combinatoire des choix possibles, soit en raison des problèmes de résistance aux comportements stratégiques. Ce cours a donc pour objectif d'aborder les principales classes de problèmes et de méthodes algorithmiques en théorie de la décision et en choix social, et d'en donner quelques classes d'applications.
représentation de préférences et optimisation sur des domaines combinatoires (CP-nets et extensions, GAI-nets, problèmes de satisfaction de contraintes valués; applications) algorithmique de la décision séquentielle : planification, processus décisionnels de Markov totalement ou partiellement observables, diagrammes d'influence aspects algorithmiques du vote : calcul de règles de vote difficiles, vote sur domaines combinatoires; résistance computationnelle aux comportements stratégiques, communication et préférences incomplètes partage de ressources : enchères combinatoires (langages d'élicitation, calcul de l'allocation optimale), partage équitable.
Bibliographie-lectures recommandées
Bibliographie Concepts et méthodes pour l'aide à la décision (D. Bouyssou, D. Dubois, M. Pirlot, H. Prade, editeurs), Hermès - Lavoisier Handbook of Constraint Programming (T. Walsh, F. Rossi, editeurs), Elsevier Handbook of Social Choice and Welfare (K. Arrow, A. Sen, K. Suzumura éditeurs), Elsevier
- Méthodes de structuration d'un problème de décision
Méthodes de structuration d'un problème de décision
Ects : 3
Enseignant responsable :
- MELTEM OZTURK ESCOFFIER
- ALEXANDROS TSOUKIAS
Volume horaire : 15
Description du contenu de l'enseignement :
Le cours a comme objectif de faire connaître aux étudiants les méthodes les plus connues pour structurer et formuler un problème de décision et de développer leur capacité de conduire un processus d'aide à la décision.
Processus de décision et processus d'aide à la décision. Méthodes de structuration orientées à des méthodes d'aide à la décision et méthodes indépendantes. Formulation d'un problème de décision et choix d'une méthode de résolution. Évolution et révision d'un problème de décision. Mise à jour. Construction d'explications et argumentation.
Compétences à acquérir :
Savoir formuler un problème de décision. Maîtriser les outils d'aide à la structuration d'un problème de décision.
Bibliographie-lectures recommandées
Bibliographie Keeney R., Valued Focussed Thinking, Wiley, New York, 1992. Rosenhead R., Rational Analysis of a Problematic World, Wiley, New York, 1997.
- Programmation par contraintes et ses applications
Programmation par contraintes et ses applications
Ects : 2
Enseignant responsable :
Volume horaire : 18
Description du contenu de l'enseignement :
- Modélisation et résolution de problèmes à l'aide de la programmation par contraintes : intérêt de la programmation par contraintes, exemples, - Types de contraintes, principaux algorithmes et heuristiques de résolution - Utilisation du logiciel professionnel OPL Studio
Compétences à acquérir :
Introduire les concepts fondamentaux de la programmation par contraintes et à étudier la modélisation et la résolution de problèmes à l'aide de la programmation par contraintes.
Bibliographie-lectures recommandées
Référence(s) : K. Apt, Principles of Constraint Programming, Cambridge University Press, 2009. K. Marriott and P.J. Stuckey, Programming with Constraints: An Introduction, The MIT Press, 1998. E. Tsang, Foundations of Constraint Satisfaction, Academic Press, 1993.
- Théorie et pratique de l'ordonnancement
Théorie et pratique de l'ordonnancement
Ects : 3
Enseignant responsable :
Volume horaire : 15
Description du contenu de l'enseignement :
Ce cours est une introduction à l'ordonnancement, dont on trouve des applications dans le domaine de la production de biens et de services, mais également en informatique, dans le domaine hospitalier, en télécommunications, etc. Les notions fondamentales et les propriétés des ordonnancements, qui sont indépendantes des domaines d'application, seront d'abord présentées. Elles serviront de base à l'introduction d'algorithmes spécifiques, exacts et approchés, pour résoudre des problèmes mono-critères et multicritères. L'ordonnancement en présence de données incertaines sera également présenté. Classification des problèmes d'ordonnancement : tâches, ressources, contraintes, critères, représentation d'un ordonnancement, ordonnancement à machines parallèles, problèmes d'atelier. Algorithmes classiques en ordonnancement : méthodes exactes et approchées avec ou sans garantie de performance. Introduction à l'ordonnancement multicritère : problèmes à une machine. Ordonnancement en contexte incertain (si le temps restant le permet) : flexibilité et robustesse en ordonnancement, maximisation d'indicateurs de robustesse.
Compétences à acquérir :
Voir ci-dessous
Mode de contrôle des connaissances :
Un examen de deux heures
Bibliographie-lectures recommandées
Bibliographie : P. Brucker, Scheduling algorithms, Springer, 2007 P. Esquirol et P. Lopez, L ’ ordonnancement, Economica, 1999 Groupe GOThA, Modèles et Algorithmes en Ordonnancement, Ellipses, 2004. M.L. Pinedo, Planning and Scheduling in Manufaturing and Services, Springer, 2005 J-C. Billaut, A. Moukrim et E. Sanlaville. Flexibilité et robustesse en ordonnancement, Lavoisier, 2005 V. T'Kindt et J-C Billaut. Multicriteria Scheduling, Theory, Models and Algorithms, Springer, 2002.
Enseignements de l'option OPTIMISATION COMBINATOIRE
- Théorie de la complexité
Théorie de la complexité
Ects : 3
Enseignant responsable :
- MICHAIL LAMPIS
Volume horaire : 15
Description du contenu de l'enseignement :
In this course we study the basics of computational complexity theory, focusing on time complexity, space complexity, and non-determinism. We discuss standard complexity classes, including P, NP, coNP, PSPACE, and the relations between them. We will explain how the notion of reductions allows us to understand the relative difficulty of two problems, even when both problems are intractable and see how reductions lead to the notion of problems complete for a class. We also study the fundamental notion of NP-completeness and its relatives (such as PSPACE-completeness) and explain what this notion means for computer science in general. If time allows we will also discuss more advanced complexity classes, such as the polynomial hierarchy, the boolean hierarchy, and randomized complexity classes.
Compétences à acquérir :
In the end of this course students will have learned how one can prove that a problem is intractable, what it means for a problem to be NP-complete or complete for another class, and the most important classes of computational complexity.
Bibliographie-lectures recommandées
Bibliography S. Arora, B. Barak, Computational Complexity. A modern approach, Cambridge University Press, 2009. M.R Garey, D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W. H. Freeman, 1979. C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
- Aspects structurels et algorithmiques dans les graphes
Aspects structurels et algorithmiques dans les graphes
Ects : 3
Enseignant responsable :
Volume horaire : 15
Description du contenu de l'enseignement :
We will see how structural, algorithmical and geometrical aspects are deeply intertwined in combinatorial optimization.
We will focus on graph theory and, in particular, on the maximum clique and the mimimum coloring problems in sub-classes of perfect graphs.
We will prove the so called weak perfect graph theorem.
Compétences à acquérir :
Structural, algorithmical and geometrical aspects of in combinatorial optimization .
Bibliographie-lectures recommandées
Bibliographie Combinatorial Optimization : Polyedra and Efficiency. A. Schrijver , Springer (2003)
- Algorithmique pour l’approximation
Algorithmique pour l’approximation
Ects : 3
Enseignant responsable :
Volume horaire : 15
Description du contenu de l'enseignement :
L’objectif de ce cours est de présenter les méthodes générales classiques permettant d’établir des algorithmes d'approximation ainsi que des résultats de non-approximation pour des problèmes d'optimisation. Présenter le lien entre un problème de décision et d'optimisation Présenter les classes de problèmes d'optimisation sémantiques (en fonction du rapport d'approximation) et syntaxiques (en fonction de la formulation logique) et la liaison entre les deux types de classes Résultats d’approximation pour des problèmes d'optimisation classiques (Voyageur de commerce, Stable, Couverture de sommets et d’ensembles, Coloration, Satisfiabilité, Sac à dos) Notions de réduction préservant le rapport d'approximation et son utilisation pour l'obtention de résultats d'approximation et non-approximation Présenter de nouveaux paradigmes d’approximation, notamment l’approximation modérément exponentielle et l’approximation paramétrée
Bibliographie-lectures recommandées
Bibliographie G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag, 1999. D. Hochbaum, Approximation Algorithms for NP-Hard Problems, Course Technology, 1996. V. Th. Paschos, Complexité et Approximation Polynomiale, Hermès, 2004. V. Vazirani, Approximation Algorithms, Springer-Verlag, 2001.
- Jeux algorithmiques
Jeux algorithmiques
Ects : 3
Enseignant responsable :
- ANGELO FANELLI
- LAURENT GOURVES
Volume horaire : 15
Description du contenu de l'enseignement :
The aim of the course is to analyze optimization problems involving multiple agents, where the actions or decisions of one agent affect not only their own utility but also the utility of others. The behavior of agents, the solutions they reach, and the quality of these solutions can be examined using tools from game theory and optimization.
Compétences à acquérir :
Foundations of Algorithmic Game Theory.
Mode de contrôle des connaissances :
- Brief Written Examination
- Project-Based Assignment
Bibliographie-lectures recommandées
- Game Theory: An Introduction. Steven Tadelis
press.princeton.edu/books/hardcover/9780691129082/game-theory
- Game Theory. Michael Maschler, Eilon Solan, Shmuel Zamir
www.cambridge.org/highereducation/books/game-theory/9700752D0339AD14706B5C0FAF34AD9E
- Algorithms for Decision Making. Mykel J. Kochenderfer, Tim A. Wheeler, Kyle H. Wray
mitpress.mit.edu/9780262047012/algorithms-for-decision-making/
- Programmation stochastique
Programmation stochastique
Ects : 3
Enseignant responsable :
Volume horaire : 15
Description du contenu de l'enseignement :
Uncertainties are ubiquitous in modeling real-world problems. Including uncertainty in an optimization model is now standard practice in industry,
thanks to the development of both mathematical models and efficient software.
In this course, we will discuss several classes of optimization problems that account for uncertainty
in the problem data. The concepts of multistage problems, probabilistic constraints and risk measures
will be used to derive the problem formulations of interest. We will also review algorithms that can
be used to tackle stochastic programming problems, from both a theoretical and a practical perspective
using recently developed packages.
Pré-requis recommandés :
Basics of linear programming.
Pré-requis obligatoire :
Basics of matrix linear algebra and statistics.
Compétences à acquérir :
- Identify the main stochastic programming models
- Understand the scenario formulation in stochastic programming.
- Formulate a problem as a multistage stochastic program.
Mode de contrôle des connaissances :
Written exam
Bibliographie-lectures recommandées
J. R. Birge and F. Louveaux, Introduction to Stochastic Programming 2nd Edition, 2011. G. Cornuéjols, J. Pena and R. Tutuncu, Optimization in Finance 2nd Edition, 2018. A. Shapiro, D. Dentcheva and A. Ruszczynski, Lectures on Stochastic Programming 3rd edition, 2021.
- Apprentissage pour l'optimisation
Apprentissage pour l'optimisation
Ects : 3
Enseignant responsable :
Volume horaire : 15
Description du contenu de l'enseignement :
Optimization is a useful paradigm for modeling data science problems and solving them using advanced algorithms. On the other hand, data science has brought new paradigms to various areas of computational science, such as linear algebra and partial differential equations. This course will review recent results on exploiting learning techniques as a tool for solving difficult optimization problems. The first part of the course will discuss how machine learning can be used in the context of combinatorial optimization techniques. We will then shift our focus to continuous relaxations of combinatorial problems, and explain how learning tools can be integrated with solvers in that space. Finally, we will present regression techniques and bandit approaches that are used in derivative-free optimization.
Pré-requis obligatoire :
Basics of matrix and vector linear algebra.
Compétences à acquérir :
- Apply basic machine learning techniques in the context of optimization problems.
- Understand the use of machine learning in derivative-free optimization.
- Learn the main success stories of machine learning on combinatorial problems.
Mode de contrôle des connaissances :
Written exam.
Bibliographie-lectures recommandées
Y. Bengio, A. Lodi, A. Prouvost. Machine learning for combinatorial optimization: a methodological tour d'horizon, 2021. S. Jegelka. Theory of Graph Neural Networks: Representation and Learning, 2022. J. Larson, M. Menickelly, S. M. Wild. Derivative-free optimization methods, 2019.
- Algorithmes pour l'optimisation continue
Algorithmes pour l'optimisation continue
Ects : 3
Enseignant responsable :
Volume horaire : 15
Description du contenu de l'enseignement :
Course Content:
- Derivatives and Gradients
- Bracketing Techniques
- Local Descent Methods
- First-Order Optimization Methods
- Second-Order Optimization Methods
- Direct Optimization Methods
- Stochastic Optimization Techniques
- Introduction to Advanced Topics: Constrained Optimization, Multi-objective Optimization, and more.
Additionally, the course will provide a foundational introduction to Julia programming, integrated throughout the curriculum.
Pré-requis recommandés :
The course is intended for advanced undergraduates and graduate students. The course requires some mathematical maturity and assumes prior exposure to multivariable calculus, linear algebra, probability concepts and programming. Some review material is provided during the course. All algorithms will be implemented in the Julia programming language, but no prior knowledge of the language is assumed.
Compétences à acquérir :
The course provides a broad introduction to optimization with a focus on practical algorithms for the design of engineering systems. The course covers a wide variety of optimization topics, introducing the underlying mathematical problem formulations and the algorithms for solving them.
Mode de contrôle des connaissances :
- Brief Written Examination
- Project-Based Assignment
Bibliographie-lectures recommandées
-Algorithms for Optimization. Mykel J. Kochenderfer and Tim A. Wheeler
https://mitpress.mit.edu/9780262039420/algorithms-for-optimization/
-Julia Documentation
- Résolution exacte de problèmes NP-difficiles
Résolution exacte de problèmes NP-difficiles
Ects : 3
Enseignant responsable :
- MICHAIL LAMPIS
Volume horaire : 15
Description du contenu de l'enseignement :
Most interesting optimization problems are NP-hard and therefore require exponential time to solve. Nevertheless, we often do need to solve them to optimality. The objective of this course is to study algorithms which, though taking exponential time in the worst case, are able to solve NP-hard problems while still offering good performance guarantees.
The main topic we will study is parameterized algorithms and complexity, which is the paradigm that leverages input structure to obtain algorithms with efficient running times. We will introduce the basic techniques of this algorithm design field, including bounded search trees, kernelization, color coding, and dynamic programming and show how these techniques can be applied via concrete examples of standard optimization problems (e.g. Vertex Cover, Coloring, Dominating Set, etc.). We will also discuss the corresponding complexity theory which traces the limits of these techniques.
Pré-requis recommandés :
Familiarity with graph theory and data structure will be useful
Pré-requis obligatoire :
Undergraduate level acquaintance with algorithms, running time analysis, computational complexity
Compétences à acquérir :
- Algorithms design technique for parameterized and exact algorithms.
- Technique to prove strong hardness for NP-hard problems.
Bibliographie-lectures recommandées
Bibliographie
- M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015.
- F. V. Fomin, D. Kratsch, Exact Exponential Algorithms, Springer-Verlag, 2010.
Enseignements de l'option ORGANISATION
- RO, environnement et systèmes de santé (AgroParisTech)
RO, environnement et systèmes de santé (AgroParisTech)
Ects : 3
Enseignant responsable :
- JOHN LEVESQUE
Volume horaire : 15
Description du contenu de l'enseignement :
L’objectif de ce cours est de se saisir d’un certain nombre de problèmes liés à l’environnement et au développement durable à travers les outils les outils de la recherche opérationnelle. Optimisation dans l’environnement et développement durable Planification des maintenances des arrêts des centrales nucléaires Energie renouvelable, biomasse Optimisation d’un réseau de chaleur Modèles d’optimisation et systèmes de santé
Bibliographie-lectures recommandées
Bibliographie Copetti et al, A general battery model for PV simulation Progress in Photovoltaics: Research and applications, vol 1, 4, 283-292,1993 Eynard J. Modélisation, optimisation dynamique et commande d ’ un méthaniseur, inra, 2006 Sandou G. Optimisation d ’ un réseau de chaleur, Edf/SupElec, 2004. Nakhla M. La régulation par les instruments des services d ’ eau en Europe, Presses des mines, 2013
- Gouvernance d'entreprise et innovation responsable
Gouvernance d'entreprise et innovation responsable
Ects : 3
Enseignant responsable :
- MICHAIL LAMPIS
Volume horaire : 15
- Conception et dynamique des organisations (Ecole des Mines)
Conception et dynamique des organisations (Ecole des Mines)
Ects : 3
Enseignant responsable :
- Michel NAKHLA
Volume horaire : 15
Description du contenu de l'enseignement :
Cet enseignement vise à préparer les élèves à comprendre les changements qui affectent l'organisation des activités dans les entreprises et à les aider à conduire ces processus de changement. Le cours vise à préparer les élèves à : L'acquisition de concepts permettant de caractériser les formes actuelles d'organisation et de construire pour une situation donnée divers scénarios alternatifs. On utilise les travaux classiques (théorie des organisations, contingence structurelle, design organisationnel) qui proposent un ensemble de « variables de conception » et de configurations organisationnelles, tout en indiquant leurs limites dans l'appréhension des formes actuellement émergentes. Une initiation à l'analyse des fonctionnements réels et des évolutions observées, afin de mieux anticiper certaines difficultés et donc éviter quelques erreurs lors du choix du scénario qui sera mis en oeuvre. Peuvent être mobilisées à cette fin plusieurs grilles d'analyse (stratégie d'acteurs, mécanismes de gestion, dynamique des connaissances, dynamique des identités professionnelles). Enfin, une initiation à la conduite des processus de transformation, au cours desquels il s'agit de gérer les inévitables surprises et de caractériser les fonctionnements émergents. Pour éclairer et structurer ce processus d'exploration, on peut mobiliser la méthodologie de la recherche-intervention, ainsi que d'autres démarches allant dans le même sens (planification interactive, démarche socio-technique, apprentissage organisationnel). Ainsi, le processus de transformation peut être analysé et piloté comme un processus d'exploration et d'apprentissage.
Bibliographie-lectures recommandées
Bibliographie JC Sardas et Ph Lefebvre « Théories des organisations et interventions dans les processus de changement », in Conception et Dynamique des Organisations : Sait-on piloter le changement ?, JC Sardas, A. Guenette (eds.) L ’ Harmattan, Paris 2004. JC Sardas, J. Erschler, G. de Terssac « Coopération et organisation de l'action collective », in Coopération et connaissance dans les systèmes industriels : une approche interdisciplinaire, René Soënen et Jacques Perrin (dir.), Hermès, 2002.
Atelier de recherche principal (1 au choix)
- Atelier Démarches, modèles et procédures d’aide à la décision
Atelier Démarches, modèles et procédures d’aide à la décision
Ects : 20
Enseignant responsable :
- DANIEL VANDERPOOTEN
- Hassan AISSI
- SONIA TOUBALINE
- BRICE MAYAG
Volume horaire : 30
Description du contenu de l'enseignement :
Cet atelier de recherche est centré sur quelques thèmes variables d ’ année en année mais ayant toujours trait à l ’ aide à la décision. Ces thèmes peuvent avoir pour point d ’ appui : un cas concret faisant l ’ objet d ’ un stage de Master ; des expériences visant à valider certaines hypothèses ; la comparaison, expérimentale ou théorique, de diverses techniques ou approches susceptibles de traiter un même problème ; l ’ étude de procédures ou méthodes nouvelles, en particulier multicritères ; l ’ examen de problèmes d ’ ordre théorique, notamment axiomatique ; des réflexions et analyses menées sur des thèmes généraux tels que la prise en compte de la mauvaise connaissance, l ’ insertion des méthodes dans les processus de décision, le mode de validation de certains types de résultats … Les thèmes sont choisis en relation avec les étudiants et sont centrés sur les mémoires de Master. Les étudiants qui choisissent cet atelier à titre secondaire sont associés à ces thèmes soit par des analyses critiques- d ’ articles ou de travaux divers, soit par des réalisations d'expériences ou des mises en œuvre de méthodes ou encore, s ’ ils le souhaitent, par des recherches plus personnelles.
- Atelier Intelligence Artificielle et décision
Atelier Intelligence Artificielle et décision
Ects : 20
Enseignant responsable :
- JEROME LANG
- STEFANO MORETTI
- STEPHANE AIRIAU
- ALEXANDROS TSOUKIAS
- GABRIELLA PIGOZZI
- MELTEM OZTURK ESCOFFIER
Volume horaire : 30
Description du contenu de l'enseignement :
L'objectif de cet atelier est de présenter aux étudiants des problèmes de recherche à la frontière de l'intelligence artificielle et de la théorie de la décision. L'atelier se présente en deux parties: une première durant laquelle les intervenants présentent les différents sujets de recherche (en donnant des éléments pour pouvoir situer la problématique), une deuxième durant laquelle les étudiants présentent leurs travaux sur les sujets choisis. Les sujets peuvent varier chaque année, mais la liste suivante donne une idée des thématiques habituellement abordées: modélisation des préférences non-classiques apprentissage de préférences, classification théorie de la décision algorithmique fouille de données et extraction de connaissances décision distribuée automatisée (systèmes multiagents, argumentation, négociation) décision séquentielle et révisable
- Atelier Algorithmique à garanties de performance
Atelier Algorithmique à garanties de performance
Ects : 20
Enseignant responsable :
- FLORIAN SIKORA
- EUN JUNG KIM
- EVANGELOS PASCHOS
- MICHAIL LAMPIS
- CRISTINA BAZGAN
- LAURENT GOURVES
Volume horaire : 30
Description du contenu de l'enseignement :
Cet atelier de recherche est centré sur la théorie de la complexité, la résolution exacte et paramétrée, l ’ approximation, les modèles dynamiques en optimisation combinatoire et les jeux algorithmique. Fil conducteur de l ’ atelier est la résolution de problèmes issus des divers modèles discrets par des algorithmes avec garanties de performance (en temps, espace, qualité de solution, etc.). Les différents thèmes abordés chaque année donnent lieu à un mémoire de Master ou à un mémoire secondaire.
- Atelier Programmation Mathématique
Atelier Programmation Mathématique
Ects : 20
Enseignant responsable :
Volume horaire : 30
Description du contenu de l'enseignement :
Cet atelier de recherche est centré sur la programmation mathématique pour la résolution des problèmes d ’ optimisation combinatoire. En exploitant la structure combinatoire d ’ un problème, notamment grâce à la théorie des graphes, l ’ approche polyédrale permet de révéler des liens entre les propriétés algorithmiques et les propriétés géométriques du problème. Parmi les problèmes considérés, par exemple pour leurs applications en conception de réseaux de télécommunication, on retrouve les problèmes classiques tels que la coloration de graphe, les multiflots/multicoupes, ou la connexité. Différents thèmes sont abordés chaque année donnant lieu à un mémoire de Master ou à un mémoire secondaire.
- Atelier Modèles de gestion et dynamique des organisations (Ecole des Mines)
Atelier Modèles de gestion et dynamique des organisations (Ecole des Mines)
Ects : 20
Enseignant responsable :
- Michel NAKHLA
Volume horaire : 30
Description du contenu de l'enseignement :
intéressons : aux processus de production de connaissances liés à la construction des instruments de gestion et d ’ aide à la décision au sein des organisations ; aux processus de création, de diffusion et d ’ adoption des outils et modèles considérés comme innovations managériales ; au double-rôle des outils et des modèles dans les organisations : moyen de pilotage et de coordination, vecteurs d ’ exploration et d ’ apprentissage. Ces questions seront explorées à partir de situations de gestion et d ’ aide à la décision (gestion de projet, relations contractualisées de type clients-fournisseurs, planification des activités et planification stratégique, relations entre firmes, processus de conception et d ’ aide à la décision, etc.) et seront éclairées par différentes familles théoriques (théorie de la décision, sociologie cognitive, théories de l ’ apprentissage, théories des organisations, approches socio-économiques). Les séances seront structurées autour des sujets de mémoire choisis par les étudiants qui auront par ailleurs, un certain nombre de textes à étudier. Des interventions théoriques seront ponctuellement assurées par les responsables de l ’ atelier pour apporter les éléments fondamentaux nécessaires.
Ateliers de recherche secondaires (2 au choix)
- Atelier Démarches, modèles et procédures d’aide à la décision
Atelier Démarches, modèles et procédures d’aide à la décision
Ects : 5
Enseignant responsable :
- DANIEL VANDERPOOTEN
- SONIA TOUBALINE
- Hassan AISSI
- BRICE MAYAG
Volume horaire : 30
- Atelier Intelligence Artificielle et décision
Atelier Intelligence Artificielle et décision
Ects : 5
Enseignant responsable :
- ALEXANDROS TSOUKIAS
- STEPHANE AIRIAU
- JEROME LANG
- STEFANO MORETTI
- GABRIELLA PIGOZZI
- MELTEM OZTURK ESCOFFIER
Volume horaire : 30
- Atelier Algorithmique à garanties de performance
Atelier Algorithmique à garanties de performance
Ects : 5
Enseignant responsable :
- EVANGELOS PASCHOS
- FLORIAN SIKORA
- MICHAIL LAMPIS
- CRISTINA BAZGAN
- LAURENT GOURVES
Volume horaire : 30
- Atelier Programmation Mathématique
Atelier Programmation Mathématique
- Atelier Modèles de gestion et dynamique des organisations (Ecole des Mines)
Atelier Modèles de gestion et dynamique des organisations (Ecole des Mines)
Ects : 5
Enseignant responsable :
- Michel NAKHLA
Volume horaire : 30
Séminaires de Recherche
Formation année universitaire 2025 - 2026 - sous réserve de modification
Modalités pédagogiques
La formation est organisée en 2 semestres, chaque semestre permettant de valider 30 ECTS. Les UE proposées sont soit des cours dispensés au premier semestre, soit des ateliers de recherche suivis au second semestre.
Les cours proposés sont des cours de 15h, à 3 ECTS. Outre les cours de tronc commun, les cours se répartissent en 3 listes pour chacune des 3 options. Dans chaque liste 2 cours sont identifiés comme obligatoires.
Au premier semestre, l’étudiant(e) devra suivre 10 cours répartis comme suit :
- 5 cours de tronc commun,
- 2 cours obligatoires propres à son option
- 2 cours optionnels choisis parmi la liste des cours de l'option
- 1 cours optionnel choisi parmi tous les cours proposés (y compris les cours obligatoires des autres options)
Au second semestre, l’étudiant(e) choisit un atelier de recherche principal parmi les ateliers de son option (20 ECTS). Il réalisera son stage et mémoire de master au sein de cet atelier. Il choisit également 2 ateliers de recherche parmi les autres ateliers, au sein desquels il réalisera un mémoire secondaire (2x5 ECTS).
Stages et projets tutorés
Le stage dure 5 mois, du mois d'avril à septembre. Il est réalisé dans un laboratoire universitaire ou en entreprise, et fait l'objet d'un rapport de stage et d'une soutenance orale.
Des programmes nourris par la recherche
Les formations sont construites au contact des programmes de recherche de niveau international de Dauphine, qui leur assure exigence et innovation.
La recherche est organisée autour de 6 disciplines toutes centrées sur les sciences des organisations et de la décision.
En savoir plus sur la recherche à Dauphine