Master's Year 2 - Modeling, Optimization, Decision and Organization (MODO)

UE Obligatoires

• Graphes et applications

  Graphes et applications

  Ects : 3

  Lecturer :
  CRISTINA BAZGAN
  

  Total hours : 15

  Overview :

  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

   

  Bibliography-recommended reading

  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

  Lecturer :
  ROLAND GRAPPE
  

  Total hours : 15

  Overview :

  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

  Learning outcomes :

  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.

  Assessment :

  A final exam on paper

  Bibliography-recommended reading

  • 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

  Lecturer :
  BRICE MAYAG
  

  Total hours : 15

  Overview :

  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

  Learning outcomes :

  Maitrise des principes et outils de modélisation des préférences

  Assessment :

  Examen écrit de 2h

  Bibliography-recommended reading

  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

  Lecturer :
  DANIEL VANDERPOOTEN
  

  Total hours : 15

  Overview :

  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).

  Recommended prerequisites :

  Connaissance des algorithmes classiques de graphe (plus court chemin, flots,...) et de Programmation Linéaire.

  Learning outcomes :

  • 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

  Bibliography-recommended reading

  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.

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

  Lecturer :
  HUGO GILBERT
  

  Total hours : 15

  Overview :

  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.

  * Classic decision criteria for decision making under uncertainty (Wald, Hurwicz, Laplace, …), and possibilistic decision making.

  * 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.

  * Critères classiques de la décision dans l'incertain (Wald, Hurwicz, Laplace, …), et décisions possibilistes.

  * Élicitation/Apprentissage des modèles décisionnels.

  Recommended prerequisites :

  An introduction to decision theory.

  Learning outcomes :

  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.

  Assessment :

  A 2-hour written exam.

  Bibliography-recommended reading

  * 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

  Lecturer :
  DANIEL VANDERPOOTEN
  

  Total hours : 15

  Overview :

  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

  Learning outcomes :

  • Maîtriser les concepts et algorithmes principaux en optimisation multiobjectif

  Bibliography-recommended reading

  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

  Lecturer :
  HASSAN AISSI
  

  Total hours : 15

  Overview :

  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.

  Bibliography-recommended reading

  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

  Lecturer :
  STEPHANE AIRIAU
  

  Total hours : 15

  Overview :

  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.

  Bibliography-recommended reading

  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

  Lecturer :
  ALEXANDROS TSOUKIAS
  MELTEM OZTURK ESCOFFIER
  

  Total hours : 15

  Overview :

  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.

  Learning outcomes :

  Savoir formuler un problème de décision. Maîtriser les outils d'aide à la structuration d'un problème de décision.

  Bibliography-recommended reading

  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 : 3

  Lecturer :
  CRISTINA BAZGAN
  

  Total hours : 18

  Overview :

  - 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

   

  Learning outcomes :

  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.

  Bibliography-recommended reading

  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

  Lecturer :
  ANDRE ROSSI
  

  Total hours : 15

  Overview :

  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.

  Learning outcomes :

  Voir ci-dessous

  Assessment :

  Un examen de deux heures

  Bibliography-recommended reading

  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

  Lecturer :
  MICHAIL LAMPIS
  

  Total hours : 15

  Overview :

  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.

  Learning outcomes :

  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.

  Bibliography-recommended reading

  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

  Lecturer :
  DENIS CORNAZ
  

  Total hours : 15

  Overview :

  Le but de ce cours est de présenter plusieurs classes de graphes bien connus et de les étudier d’un point de vue structurel (théorème de caractérisation) et algorithmique. On étudiera entre autres les classes de graphes suivants : Graphes d’intervalles Graphes triangulés Graphes de permutation Graphes de comparabilité Graphes planaires Graphes de largeur d’arbre bornée Graphes parfaits En ce qui concerne l’aspect structurel, on présentera les notions suivantes : sommet simplicial, séparateur, schéma d’élimination, triple astéroïdal, mineur, largeur d’arbre, largeur de clique, graphes d’intersection, orientation transitive, caractérisation par sous-graphes induits interdits, décomposition arborescente, k-arbre partiel, … Pour l’aspect algorithmique, on envisage d’étudier entre autres les problèmes suivants : problème de reconnaissance de ces classes de graphes, problème de coloration, problème de la clique maximum, problème du stable maximum, problème du voyageur de commerce, etc.

  Bibliography-recommended reading

  Bibliographie M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Second edition, Academic Press, New York, 2004, Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004. A. Brandstädt, V. B. Le and J. P. Spinrad Graph Classes: A Survey SIAM Monographs on Discrete Mathematics and Applications, 1999.

• Algorithmique pour l’approximation

  Algorithmique pour l’approximation

  Ects : 3

  Lecturer :
  CRISTINA BAZGAN
  

  Total hours : 15

  Overview :

  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

  Bibliography-recommended reading

  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

  Lecturer :
  ANGELO FANELLI
  LAURENT GOURVES
  

  Total hours : 15

  Overview :

  L’objectif est d’analyser des problèmes d’optimisation mettant en jeu plusieurs agents. Les actions/décisions d’un agent ont un impact sur son utilité propre mais aussi sur celle des autres agents. Le comportement des agents, les solutions atteintes et leur qualité peuvent être analysés à l’aide d’outils issus de la théorie des jeux et de l’optimisation. Le cours concerne principalement les jeux stratégiques. On donne des définitions et principaux concepts de solution (équilibres). On analyse ensuite les jeux de congestion, leur pouvoir de modélisation, existence d’un équilibre de Nash pur, calcul d’équilibres, etc. Ensuite, on discute des principales mesures de la qualité des équilibres que sont le prix d’anarchie et de stabilité.

  Learning outcomes :

  Bases en théorie des jeux algorithmique.

  Bibliography-recommended reading

  E. Tardos, T. Roughgarden, V. Vazirani, Algorithmic Game Theory, Cambridge University Press, 2007 D. Easley, J. Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World , Cambridge University Press (2010)

• Programmation stochastique

  Programmation stochastique

  Ects : 3

  Lecturer :
  CLEMENT ROYER
  

  Total hours : 15

  Overview :

  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.

  Recommended prerequisites :

  Basics of linear programming.

  Require prerequisites :

  Basics of matrix linear algebra and statistics.

  Learning outcomes :

  - Identify the main stochastic programming models

  - Understand the scenario formulation in stochastic programming.

  - Formulate a problem as a multistage stochastic program.

  Assessment :

  Written exam

  Bibliography-recommended reading

  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

  Lecturer :
  CLEMENT ROYER
  

  Total hours : 15

  Overview :

  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.

  Require prerequisites :

  Basics of matrix and vector linear algebra.

  Learning outcomes :

  - 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.

  Assessment :

  Written exam.

  Bibliography-recommended reading

  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 : 15

  Lecturer :
  ANGELO FANELLI
  

  Total hours : 15
• Résolution exacte de problèmes NP-difficiles

  Résolution exacte de problèmes NP-difficiles

  Ects : 3

  Lecturer :
  MICHAIL LAMPIS
  

  Total hours : 15

  Overview :

  Objectifs : Enseigner les techniques de la résolution exacte des problèmes NP-difficiles par des algorithmes à complexité non-triviale (dits algorithmes modérément exponentiels) et par des algorithmes paramétrés. Pour chacune de ces techniques, des exemples de problèmes sur lesquels elles sont appliquées seront présentés et discutés.

  Complexité au pire des cas Techniques de résolution exacte (Programmation dynamique, Arbres de recherche, Enumération, Inclusion – exclusion, Recherche locale) Application à la résolution exacte de problèmes NP-difficiles (Coloration, Voyageur de commerce, Stable, Coupe maximum, Stable maximum, Couverture d'ensembles) Techniques de l’algorithmique paramétrée (Kernelisation, Arbres de recherche, …) Application à la résolution paramétrée de problèmes NP-difficiles (Couverture de sommets minimum, Feedback vertex set, k-Couverture de sommets)

  Recommended prerequisites :

  Familiarity with graph theory and data structure will be useful

  Require prerequisites :

  Undergraduate level acquaintance with algorithms, running time analysis, computational complexity

  Learning outcomes :

  • Algorithms design technique for parameterized and exact algorithms.
  • Technique to prove strong hardness for NP-hard problems.

  Bibliography-recommended reading

  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

• Modèles industriels et de conception

  Modèles industriels et de conception

  Ects : 3

  Lecturer :
  Michel NAKHLA
  

  Total hours : 24

  Overview :

  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.

  Bibliography-recommended reading

  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

• RO, environnement et systèmes de santé (AgroParisTech)

  RO, environnement et systèmes de santé (AgroParisTech)

  Ects : 3

  Lecturer :
  JOHN LEVESQUE
  

  Total hours : 15

  Overview :

  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é

  Bibliography-recommended reading

  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

  Lecturer :
  KEVIN LEVILLAIN
  BLANCHE SEGRESTIN
  

  Total hours : 15
• Conception et dynamique des organisations (Ecole des Mines)

  Conception et dynamique des organisations (Ecole des Mines)

  Ects : 3

  Lecturer :
  Michel NAKHLA
  

  Total hours : 15

  Overview :

  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.

  Bibliography-recommended reading

  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.

Ateliers de l'option DÉCISION

• 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

  Lecturer :
  BRICE MAYAG
  DANIEL VANDERPOOTEN
  HASSAN AISSI
  SONIA TOUBALINE
  

  Total hours : 30

  Overview :

  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

  Lecturer :
  STEFANO MORETTI
  MELTEM OZTURK ESCOFFIER
  ALEXANDROS TSOUKIAS
  STEPHANE AIRIAU
  JEROME LANG
  

  Total hours : 30

  Overview :

  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  

Ateliers de l'option OPTIMISATION COMBINATOIRE

• Atelier Algorithmique à garanties de performance

  Atelier Algorithmique à garanties de performance

  Lecturer :
  MICHAIL LAMPIS
  LAURENT GOURVES
  CRISTINA BAZGAN
  FLORIAN SIKORA
  EUN JUNG KIM
  EVANGELOS PASCHOS
  

  Total hours : 30

  Overview :

  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

  Lecturer :
  DENIS CORNAZ
  

  Total hours : 30

  Overview :

  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.  

Ateliers de l'option ORGANISATION

• Atelier Modèles de gestion et dynamique des organisations (Ecole des Mines)

  Atelier Modèles de gestion et dynamique des organisations (Ecole des Mines)

  Lecturer :
  Michel NAKHLA
  

  Total hours : 30

  Overview :

  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.  

Séminaires de Recherche