Modélisation, Optimisation, Décision et Organisation - 2ème année de Master

UE Obligatoires

• Graphes et applications

  Graphes et applications

  Ects : 3

  Enseignant responsable :
  CRISTINA BAZGAN
  

  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 :
  ALI RIDHA MAHJOUB
  

  Volume horaire : 15

  Description du contenu de l'enseignement :

  Plusieurs problèmes concrets issus de domaines divers peuvent être formulés comme des programmes linéaires et des programmes linéaires en nombres entiers. Le but de ce module est d'étudier la modélisation et les méthodes de résolution de ces problèmes, basées sur la programmation linéaire et la programmation en nombres entiers. On introduit les principaux outils théoriques et algorithmiques nécessaires à la compréhension de ces méthodes, et on présente certaines applications réelles illustrant les algorithmes étudiés.

  Modèles de programmes en nombres entiers Relation entre problèmes combinatoires et programmation linéaire Séparation et optimisation Méthode de coupe Techniques de décomposition Applications

  Bibliographie-lectures recommandées

  Bibliographie. W. Cook, W. Cunningham, W.R. Pulleyblank, A. Schrijver, "Combinatorial Optimization", Wiley (1997). G. L. Nemhauser and L. A. Wolsey, " Integer and Combinatorial Optimization", Wiley (1988). L. A. Wolsey, Integer Programmation, Wiley (1998). A. Schrijver, "Theory of Linear and Integer Programming", 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 :
  BRICE MAYAG
  

  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 :
  DANIEL VANDERPOOTEN
  

  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
  

  Volume horaire : 15

  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

UE Optionnels

• Théorie de la décision et théorie des jeux

  Théorie de la décision et théorie des jeux

  Ects : 3

  Enseignant responsable :
  STEFANO MORETTI
  LUCIE GALAND
  

  Volume horaire : 15

  Description du contenu de l'enseignement :

  Ce cours vise à présenter aux étudiants les concepts et modèles de base en théorie de la décision dans le risque et dans l'incertain. On donnera également quelques éléments de base de la théorie des jeux.

  Introduction (principaux concepts : incertitude, risque, probabilités ;typologie des problèmes de décision) Décision dans le risque (arbre de décision, résolution d'un arbre de décision, information parfaite et imparfaite, valeur de l'information, espérance mathématique et espérance mathématique d'utilité, axiomes de Von Neumann & Morgenstern, encodage et utilisation d'une fonction d'utilité, goût et aversion pour le risque) Décision dans l'incertain (critères classiques de la décision dans l'incertain, probabilités objectives et subjectives, modèle de Savage) Décision en situation d'interaction (Jeux contre la nature et contre un adversaire, situations compétitives et coopératives, introduction à la théorie des jeux, aperçu sur les problèmes de négociation)
• Optimisation multiobjectifs

  Optimisation multiobjectifs

  Ects : 3

  Enseignant responsable :
  DANIEL VANDERPOOTEN
  

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

• Théorie et pratique de l'ordonnancement

  Théorie et pratique de l'ordonnancement

  Ects : 3

  Enseignant responsable :
  ANDRE ROSSI
  

  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.

• 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 :
  DENIS CORNAZ
  MICHAIL LAMPIS
  

  Volume horaire : 15

  Description du contenu de l'enseignement :

  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.

  Bibliographie-lectures recommandées

  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

  Enseignant responsable :
  EVANGELOS PASCHOS
  CRISTINA BAZGAN
  

  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 :
  LAURENT GOURVES
  

  Volume horaire : 15

  Description du contenu de l'enseignement :

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

  Compétences à acquérir :

  Bases en théorie des jeux algorithmique.

  Bibliographie-lectures recommandées

  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)

• Optimisation Combinatoire et Polyèdres

  Optimisation Combinatoire et Polyèdres

  Ects : 3

  Volume horaire : 15

  Description du contenu de l'enseignement :

  Plusieurs problèmes concrets issus de domaines divers peuvent être formulés comme des problèmes d’optimisation combinatoire. La résolution de ces problèmes se ramène à l’optimisation d’une fonction objectif sur un polyèdre. Ce cours est une introduction à l’analyse polyédrale pour les problèmes d’optimisation combinatoire. On introduit les principaux éléments nécessaires pour une telle analyse et étudie les conséquences algorithmiques pour la résolution des problèmes sous-jacents. Certaines applications seront présentées pour illustrer ces approches.

   

  Optimisation combinatoire et polyèdres Dimension, faces et facettes de polyèdres Description minimale d’un polyèdre par un système d’inégalités linéaires Approche polyédrale Polyèdres combinatoires et relations min-max Applications

  Bibliographie-lectures recommandées

  Bibliographie W. Cook, W. Cunningham, W.R. Pulleyblank, A. Schrijver, "Combinatorial Optimization", Wiley (1998). A. R. Mahjoub, "Approches polyédrales", dans "Optimisation Combinatoire 1: Concepts fondamentaux", V. Paschos (Ed.), Hermes (2005) pp. 263-329. G. L. Nemhauser and L. A. Wolsey, "Integer and Combinatorial Optimization", Wiley (1988)

• Quelques applications industrielles de la Recherche Opérationnelle

  Quelques applications industrielles de la Recherche Opérationnelle

  Ects : 3

  Description du contenu de l'enseignement :

  Recherche Opérationnelle Objectifs : Présenter quelques applications de la Recherche Opérationnelle (planification, dimensionnement de réseaux, composition de services web, ...) la modélisation (sous forme de PLNE, graphes...) et la décomposition (décomposition de Dantzig-Wolfe, Benders...), l'analyse de complexité théorique, les méthodes de résolution (Branch and Bound, Branch and Price avec de la génération de contraintes et/ou de colonnes, ...), l'analyse de sensibilité et de robustesse des solutions obtenues.  

  Bibliographie-lectures recommandées

  Bibliographie G. Fleury, Ph. Lacomme Programmation linéaire avancée (Programmes Java pour Macintosh, Linux et Windows), Ellipses, 2010.

• Optimisation en environnements incertains et dynamiques

  Optimisation en environnements incertains et dynamiques

  Ects : 3

  Enseignant responsable :
  EVANGELOS PASCHOS
  

  Volume horaire : 15

  Description du contenu de l'enseignement :

  L’objectif de ce cours est de présenter les problématiques liées à l’optimisation combinatoire dans le cadre d’instances évolutives. Pour les différents cas envisagés, nous présenterons des résultats en termes de complexité, d’algorithmique et d’approximation.

   

  Les grandes problématiques présentées seront : L’optimisation on-line dans laquelle l’instance se révèle petit à petit L’optimisation probabiliste dans laquelle il existe une incertitude sur la présence des données La réoptimisation dans laquelle il s’agit de tirer profit de la connaissance d’une solution optimale lorsque l’instance est très peu perturbée Nous aborderons les problèmes classiques d’optimisation combinatoire tels que le stable, la coloration, l’arbre couvrant… dans chacun de ces cadres.

  Bibliographie-lectures recommandées

  Bibliographie C. Murat, V. Paschos, Probabilistic Combinatorial Optimization on Graphs, ISTE, United Kingdom, Hermes Science Publishing, 272 pages, mars 2006. S. Albers, Online Algorithms: a survey, Mathematical Programming, 97(1), 3-26, 2003.

• Résolution exacte de problèmes NP-complets et difficiles

  Résolution exacte de problèmes NP-complets et difficiles

  Ects : 3

  Enseignant responsable :
  EUN JUNG KIM
  MICHAIL LAMPIS
  

  Volume horaire : 15

  Description du contenu de l'enseignement :

  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)

  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.
• Théorie des organisations (Ecole des Mines - AgroParisTech)

  Théorie des organisations (Ecole des Mines - AgroParisTech)

  Ects : 3

  Enseignant responsable :
  Michel NAKHLA
  

  Volume horaire : 15

  Description du contenu de l'enseignement :

  Initier les élèves à l’analyse des organisations, à partir de l’examen d’un certain nombre de variables qui en caractérisent le fonctionnement.

  Approches structurelles des organisations, les déterminants de la structure stratégie d’entreprises Corporate governance Théorie de la firme : théorie du marché et du contrôle, théorie de l’agence, théorie managériale, théorie de la propriété

  Bibliographie-lectures recommandées

  Bibliographie De nouvelles théories pour gérer l’entreprise, Economica, 1987. Théorie des organisations, Ed Eska, 2005 Chandler AZ. The visible hand, Belknap Press, Cambridge, 1977 Woodward J. Industrial organizations, theory and Practice, 1965

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

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

  Ects : 3

  Enseignant responsable :
  Michel NAKHLA
  

  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

• Conception et dynamique des organisations (Ecole des Mines)

  Conception et dynamique des organisations (Ecole des Mines)

  Ects : 3

  Enseignant responsable :
  CEDRIC DALMASSO
  Philippe LEFEBVRE
  

  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.

• Théorie de la conception - Processus génératifs (Ecole des Mines)

  Théorie de la conception - Processus génératifs (Ecole des Mines)

  Ects : 3

  Enseignant responsable :
  Pascal LE MASSON
  

  Volume horaire : 15

  Description du contenu de l'enseignement :

  Le paradigme décisionnel a marqué le XXe siècle, faisant du « décideur » une grande figure managériale tirant sa légitimité des sciences de la décision qui apprennent à sélectionner avec rigueur la solution optimale parmi un ensemble d’alternatives. Mais comment cet ensemble d’alternatives est-il généré ? Cette question invite à dépasser le paradigme décisionnel pour étudier le paradigme conceptif sous-jacent. Le paradigme conceptif trouve sa source dans les premières théories architecturales (Vitruve, 1er siècle av J.C.), il se déploie depuis plusieurs siècles avec les ingénieurs et les designers ; il s’appuie sur les sciences de la conception, qui ont bénéficié des avancées majeures effectuées ces dernières décennies en mathématiques, en engineering design et en neurosciences. Le cours porte sur l’étude de ces fondements théoriques de la conception, les modèles associés et certaines des méthodes qui en découlent.

   

  Bases théoriques du raisonnement de conception – Présentation de plusieurs méthodes de conception Contextualisation de ces éléments théoriques et ces méthodes en fonction des ambitions d’innovation (plus ou moins grande rupture), en fonction des professions impliquées (conception pour l’ingénieur / pour le designer), en fonction des risques (endogénéisation des risques, généricité).

  Ce cours est donné en PSL-week de mars (semaine du 7 mars en 2022)

  Pré-requis recommandés :

  Le cours ne nécessite pas de prérequis. Des connaissances en théories de la décision dans l’incertain et en recherche opérationnelle sont un plus.

  Le cours est particulièrement adapté aux ingénieurs généralistes (notamment des Mines). Mais l’expérience montre que des experts de recherche opérationnelle (issus du Master MODO de Dauphine) comme des designers de l’ENSAD en tirent aussi un grand profit.

  Compétences à acquérir :

  le cours vise un triple objectif :

  - Assimiler les bases théoriques du raisonnement génératif

  - Maîtriser plusieurs méthodes de conception associées et savoir les appliquer sur thèmes d’innovation et des ‘grand challenges’ contemporains (réalisation de référentiels C-K)

  - Permettre de comprendre, évaluer voire améliorer les processus génératifs dans des domaines variées, aussi bien les algorithmes génératifs de la data science que les méthodes génératives des designers du Bauhaus.

  Mode de contrôle des connaissances :

  Un examen final permet l’évaluation. Il comporte trois parties :

  - un questionnaire sur les principales notions vues au cours de la semaine ;

  - le développement d’un raisonnement de conception, sur la base des théories et méthodes vues en cours.

  - la discussion d’un article scientifique en rapport avec les théories et méthodes de la conception. La discussion est guidée par des questions précises et repose sur les notions vues en cours.

  Bibliographie-lectures recommandées

  Le Masson, P., Weil, B., and Hatchuel, A. (2017). Design Theory - Methods and Organization for Innovation, Springer Nature.

   

  Le Masson, P., Weil, B., and Hatchuel, A. (2014). Théorie, méthodes et organisations de la conception, Sciences de la Conception, M. Nakhla, Presses des Mines, Paris. 464p. (version française de l’ouvrage ci-dessus)

• Programmation par contraintes et ses applications

  Programmation par contraintes et ses applications

  Ects : 2

  Enseignant responsable :
  CRISTINA BAZGAN
  

  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.

UE Optionnels

• Démarches, modèles et procédures d’aide à la décision - Atelier principal

  Démarches, modèles et procédures d’aide à la décision - Atelier principal

  Ects : 20

  Enseignant responsable :
  HASSAN AISSI
  SONIA TOUBALINE
  BRICE MAYAG
  DANIEL VANDERPOOTEN
  

  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.
• Démarches, modèles et procédures d’aide à la décision - Atelier secondaire

  Démarches, modèles et procédures d’aide à la décision - Atelier secondaire

  Ects : 5

  Enseignant responsable :
  HASSAN AISSI
  SONIA TOUBALINE
  BRICE MAYAG
  DANIEL VANDERPOOTEN
  

  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.  
• Intelligence Artificielle et décision - Atelier principal

  Intelligence Artificielle et décision - Atelier principal

  Ects : 20

  Enseignant responsable :
  STEPHANE AIRIAU
  JEROME LANG
  STEFANO MORETTI
  

  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
• Intelligence Artificielle et décision - Atelier secondaire

  Intelligence Artificielle et décision - Atelier secondaire

  Ects : 5

  Enseignant responsable :
  STEPHANE AIRIAU
  STEFANO MORETTI
  JEROME LANG
  

  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  
• Algorithmique à garanties de performance - Atelier principal

  Algorithmique à garanties de performance - Atelier principal

  Ects : 20

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

  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.
• Algorithmique à garanties de performance - Atelier secondaire

  Algorithmique à garanties de performance - Atelier secondaire

  Ects : 5

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

  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.  
• Programmation Mathématique - Atelier principal

  Programmation Mathématique - Atelier principal

  Ects : 20

  Enseignant responsable :
  DENIS CORNAZ
  ALI RIDHA MAHJOUB
  

  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.
• Programmation Mathématique - Atelier secondaire

  Programmation Mathématique - Atelier secondaire

  Ects : 5

  Enseignant responsable :
  ALI RIDHA MAHJOUB
  DENIS CORNAZ
  

  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.  
• Modèles de gestion et dynamique des organisations (Ecole des Mines) - Atelier principal

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

  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.
• Modèles de gestion et dynamique des organisations (Ecole des Mines) - Atelier secondaire

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

  Ects : 5

  Enseignant responsable :
  Michel NAKHLA
  

  Volume horaire : 30

  Description du contenu de l'enseignement :

  Dans cet atelier sont étudiés les liens étroits qui existent entre modèles de gestion et dynamique des organisations. Considérant les outils et modèles de gestion comme le fruit de processus de construction et comme partie constitutive de la définition et de la dynamique des organisations, nous nous 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.