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

UE Obligatoires

• Graphs and applications

  Graphs and applications

  Ects : 3

  Enseignant responsable :
  

  • CRISTINA BAZGAN

  Volume horaire : 15

  Description du contenu de l'enseignement :

  The goal of this course is to show the variety of concepts and algorithms of graph theory for modeling and solving concrete problems. We also show how to model, more or less directly, some real situations by reducing them to classical problems.

  Compétences à acquérir :

  • Basic concepts in graph theory,
  • Study of classical problems: flows, matching, covering, independent set, coloring
  • 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.
• Mathematical Programming

  Mathematical Programming

  Ects : 3

  Enseignant responsable :
  

  • ROLAND GRAPPE

  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

  Many problems arising from different domains can be formulated as linear and integer programs. The aim of this course is to study the modelisation and resolution techniques for these problems, based on linear and integer programming. We will introduce the main theoretical and algorithmic tools necessary for understanding and applying these techniques. We will also present some real applications to illustrate the algorithms that will be discussed.

  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).
• Preference Modelling and Multiple Criteria Decision Making

  Preference Modelling and Multiple Criteria Decision Making

  Ects : 3

  Enseignant responsable :
  

  • BRICE MAYAG

  Volume horaire : 15

  Description du contenu de l'enseignement :

  This course is an introduction to the main tools and techniques of preference modelling and multiple criteria decision making.

  Compétences à acquérir :

  • Introduction to modelling for decision aiding: decision making process and decision aiding process
  • Preference modelling: main structure for preference modelling, numerical representations and classical problems
  • Social choice: introduction to social theory, voting rules and their properties
  • Multiattribute Value Theory: even swap technique, additive value functions (mains results and elicitation)
  • ELECTRE methods: introduction to the ELECTRE methods.

  Mode de contrôle des connaissances :

  Examen écrit de 2h

  Bibliographie-lectures recommandées

  • 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.
• Modelling in Decision Aiding and Operational Research

  Modelling in Decision Aiding and Operational Research

  Ects : 3

  Enseignant responsable :
  

  • DANIEL VANDERPOOTEN

  Volume horaire : 15

  Description du contenu de l'enseignement :

  The course aims at presenting the modelling process in Decision Aiding/Operational Research as well as original models for various decision problems.

  Pré-requis recommandés :

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

  Compétences à acquérir :

  • Definition and roles of models in Decision Aiding/Operational Research. Solution and preference models.
  • Description of the modelling process and its different phases.
  • Presentation of non trivial models using various modelling frameworks (graphs, linear programming, multiobjective,...).
  • The use of 0-1 variables in linear programming
  • Presentation of modelling and solving tools (modellers and solvers).

  Bibliographie-lectures recommandées

  • H.P. Williams. Model building in mathematical programming. J. Wiley, New York, 2013. 5th 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.
• Industrial and design models

  Industrial and design models

  Ects : 3

  Enseignant responsable :
  

  • Michel NAKHLA

  Volume horaire : 24

  Description du contenu de l'enseignement :

  The aim of this course is to introduce industrial production and design models. It focuses primarily on the various problems of industrial rationalization.

  Compétences à acquérir :

  The different categories of models and their current resolution techniques are studied, as well as the situations in which these problems arise. In addition, the main production systems are presented: flow management, planning, computer-aided tools, etc., and their evolution in the face of an industrial world now dominated more by design and innovation strategies. Emphasis is placed on the applicability of these techniques, and a distinction is made between reasoning-based and organization-based models.

  Bibliographie-lectures recommandées

  • 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

• Decision under uncertainty and decision models

  Decision under uncertainty and decision models

  Ects : 3

  Enseignant responsable :
  

  • HUGO GILBERT

  Volume horaire : 15

  Description du contenu de l'enseignement :

  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.

  Pré-requis recommandés :

  An introduction to decision theory.

  Compétences à acquérir :

  • 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 approaches.
  • Classic decision criteria for decision making under uncertainty (Wald, Hurwicz, Laplace, … ), and possibilistic decision making.

  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 1: Principles. Springer Science & Business Media, 1998.
  • Barbera, S., Hammond, P.J., & Seidl, C. Editors, Handbook of Utility Theory: Volume 2: Extensions. Springer Science & Business Media, 1998.      
  • Gilboa, Itzhak, Theory of decision under Uncertainty, Cambridge University Press, 2009.
• Multiobjective Optimization

  Multiobjective Optimization

  Ects : 3

  Enseignant responsable :
  

  • DANIEL VANDERPOOTEN

  Volume horaire : 15

  Description du contenu de l'enseignement :

  This course introduces the main concepts, results and methods in multiobjective optimization in general, with an emphasis on multiobjective combinatorial optimization.

  Compétences à acquérir :

  • Motivation, main concepts (decision space, criterion space, efficient solutions, non-dominated points,...),
  • Interest and limitations of the main scalarizing functions (Weighted sum, Tchebychev, reference point,...)
  • Multiobjective combinatorial optimization – Specific difficulties (intractability...)
  • Exact methods for enumérating the non-dominated set (generic methods, specific methods)
  • Approximate methods with a priori guarantee
  • General approaches for determining a best compromise solution

  Bibliographie-lectures recommandées

  • 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.
• Robustness in Operations Research and Decision Aiding

  Robustness in Operations Research and Decision Aiding

  Ects : 3

  Enseignant responsable :
  

  • Hassan AISSI

  Volume horaire : 15

  Description du contenu de l'enseignement :

  In OR-DA, the term robust means a capacity for withstanding "vague approximations" and/or "zones of ignorance" in order to prevent undesirable impacts, notably the degradation of the properties that must be maintained. Consequently, robustness stems from a process that responds to a concern: a need for resistance or self-protection. Optimal solutions of classical models in OR may not have this capacity. The aim of this course is to introduce the basic robustness models.

  Compétences à acquérir :

  • Basic concepts and presentation of some examples.
  • Study of classical criteria : min-max and min-max regret.
  • Study of Bertsimas and Sim ’ s model.
  • Study of the multilevel programming approach.

  Bibliographie-lectures recommandées

  • 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.
• Algorithmic Decision Theory and Computational Social Choice

  Algorithmic Decision Theory and Computational Social Choice

  Ects : 3

  Enseignant responsable :
  

  • STEPHANE AIRIAU

  Volume horaire : 15

  Description du contenu de l'enseignement :

  Many individual or collective decision making contexts involve computationally hard problems, either because of the combinatorial structure of the choice space, or because of the 'computational resistance" to strategic behaviour. This course aims at introducing the main classes of problems and algorithmic techniques in decision theory and social choice, and to study a few classes of applications.

  Compétences à acquérir :

  • preference representation and optimization on combinatorial domains (CP-nets and extensions, GAI-nets, valued constraint satisfaction problems; applications)
  • algorithms for sequential decision making: planning, fully or partially observable Markov decision processes, influence diagrams
  • algorithmic aspects of voting: computationally hard voting rrules, voting on combinatorial domains, computational resistance to strategic behaviour, communication and incomplete preferences
  • resource allocation: combinatorial auctions (elicitation lannguages, winner determination algorithms), fair division.

  Bibliographie-lectures recommandées

  • 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.
• Problem structuring methods

  Problem structuring methods

  Ects : 3

  Enseignant responsable :
  

  • MELTEM OZTURK ESCOFFIER
  • ALEXANDROS TSOUKIAS

  Volume horaire : 15

  Description du contenu de l'enseignement :

  The students should get acquainted with the best known methods aimed at structuring and formulating a decision problem and learn how to conduct a decision aiding process.

  Compétences à acquérir :

  • Decision Processes and Decision Aiding Processes.
  • Problem Structuring Methods either oriented to one precise decision support method or independent.
  • Formulating a decision problem and choosing a problem solving method.
  • Revising and updating a decision problem.
  • Constructing explanations and justifications.

  Bibliographie-lectures recommandées

  • Keeney R., Valued Focussed Thinking, Wiley, New York, 1992.
  • Rosenhead R., Rational Analysis of a Problematic World, Wiley, New York, 1997.
• Theory and practice of production scheduling

  Theory and practice of production scheduling

  Ects : 3

  Enseignant responsable :
  

  • ANDRE ROSSI

  Volume horaire : 15

  Description du contenu de l'enseignement :

  The objective is to understand the basics of production scheduling, identify scheduling problems and know and understand specific methods to solve them. We will pay particular attention to exact and approximate solution methods in deterministic and uncertain environments. Students will also have the ability to manipulate an academic scheduling software.

  Compétences à acquérir :

  • Classification of scheduling problems: tasks, resources, production lines, constraints, criteria, representation of a schedule …
  • Scheduling in deterministic environment: exact solution methods (priority rules , dynamic programming … ), approximate methods with or without performance guarantee (list algorithms, local search algorithms)
  • Scheduling in uncertain environment: Flexibility and robustness in scheduling, concept of scenario, exact and approximate solution methods of some robust versions.

  Mode de contrôle des connaissances :

  Un examen de deux heures

  Bibliographie-lectures recommandées

  • P. Brucker, Scheduling algorithms, Springer, 2007 (http://users.utu.fi/yurnik/scheduling_files/Scheduling_Peter_Brucker.pdf)
  • 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

Enseignements de l'option OPTIMISATION COMBINATOIRE

• Complexity Theory

  Complexity Theory

  Ects : 3

  Enseignant responsable :
  

  • MICHAIL LAMPIS

  Volume horaire : 15

  Description du contenu de l'enseignement :

  The course is about complexity of algorithms fundamentals. It mainly handles intractability, reducibility, and notions of completeness/hardness for complexity classes.

  Compétences à acquérir :

  • Problems ’ intractability
  • Reductions and class inclusion preservation
  • Role of the parameters in the evaluation of a problem's complexity
  • Complexity classes wrt parameter “ size of instance ” : P, NP, co-NP, Karp and Turing reductions, NP-completeness
  • Complexity classes wrt parameter “ solution value ” , XP, FPT, W[ ]-hierachy, FPT reductions

  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.

• Structural and algorithmic graph theory

  Structural and algorithmic graph theory

  Ects : 3

  Enseignant responsable :
  

  • ANDRE ROSSI
  • DENIS CORNAZ

  Volume horaire : 15

  Description du contenu de l'enseignement :

  In this course, we introduce several well-known graph classes and we study their structural properties (e.g. characterization theorems) as well as their algorithmic properties (e.g. efficient algorithms for some classical optimization problems).

  Compétences à acquérir :

  We study among others the following graph classes: interval graphs, chordal graphs, permutation graphs, comparability graphs, planar graphs, bounded treewidth graphs, perfect graphs. Concerning the structural properties, we will introduce for instance the following notions: simplicial vertex, separator, elimination scheme, asteroidal triple, minor, treewidth, cliquewidth, intersection graph, transitive orientation, characterization by a family of forbidden induced subgraphs, tree decomposition, partial k-tree, … . Concerning the algorithmic properties, we will focus on the following classical optimization problems: recognition problem for the graph classes mentioned above, coloring problem, maximum clique problem, maximum stable set problem, travelling salesman problem, …

  Bibliographie-lectures recommandées

  Bibliographie Combinatorial Optimization : Polyedra and Efficiency. A. Schrijver , Springer (2003)

• Approximation algorithms

  Approximation algorithms

  Ects : 3

  Enseignant responsable :
  

  • CRISTINA BAZGAN

  Volume horaire : 15

  Description du contenu de l'enseignement :

  The course surveys the fundamental concepts of polynomial approximation theory (design and analysis of approximation algorithms, inapproximability, approximation preserving reductions) as well as new approximation paradigms.

  Compétences à acquérir :

  • Links between decision-optimization problem
  • Approximability classes (semantic – syntactic)
  • Approximability/inapproximability of some paradigmatic combinatorial optimization problems (TSP, Vertex Cover, Set Cover, Independent Set/Clique, Coloring, Min and Max Satisfiability, Knapsack, etc.)
  • Approximation preserving reductions and inapproximability
  • New approximation paradigms: Moderately Exponential, Subexponential and Parameterized Appproximation

  Bibliographie-lectures recommandées

  • 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.
• Algorithmic games

  Algorithmic games

  Ects : 3

  Enseignant responsable :
  

  • ANGELO FANELLI
  • LAURENT GOURVES

  Volume horaire : 15

  Description du contenu de l'enseignement :

  The goal is to analyze some optimisation problems when several agents are involved. The actions/decisions made by an agent have an impact on his own utility and also on the utility of the other agents. The behavior of the agents, the solutions that they reach and the quality of these solutions can be analyzed with tools from both game theory and optimization theory.

  Compétences à acquérir :

  The lecture mainly deals with strategic games. The main solution concepts (equilibria) are defined. Then we study congestion games, the range of concrete problem they can model, the existence of a pure Nash equilibrium, the computation of equilibria, etc. Finally, the main measure of efficiency of equilibria are discussed (price of anarchy, price of stability).

  Mode de contrôle des connaissances :

  • Brief Written Examination
  • Project-Based Assignment

  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)
• Stochastic programming

  Stochastic programming

  Ects : 3

  Enseignant responsable :
  

  • CLEMENT ROYER

  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

  •   M. Biel and M. Johansson, Efficient stochastic programming in Julia, INFORMS Journal of Computing (2022)
  • J. R. Birge and F. Louveaux, Introduction to Stochastic Programming 2nd Edition, Springer (2011)
  • A. Shapiro, D. Dentcheva and A. Ruszczynski, Lectures on Stochastic Programming, 3rd edition, SIAM (2021)
• Machine learning for optimization

  Machine learning for optimization

  Ects : 3

  Enseignant responsable :
  

  • CLEMENT ROYER

  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.

  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, European Journal on Operations Research (2021)
  • S. Jegelka. Theory of Graph Neural Networks: Representation and Learning (2022)
  • J. Larson, M. Menickelly, S. M. Wild. Derivative-free optimization methods, Acta Numerica (2019)
  • P.-W. Wang, P. Donti, B. Wilder, J. Z. Kolter. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver, ICML (2019)
• Algorithms for continuous optimization

  Algorithms for continuous optimization

  Ects : 3

  Enseignant responsable :
  

  • ANGELO FANELLI

  Volume horaire : 15

  Description du contenu de l'enseignement :

  This course provides a broad introduction to continuous optimization with a focus on practical algorithms for the design of engineering systems. We cover a wide variety of continuous optimization topics, introducing the underlying mathematical problem formulations and the algorithms for solving them. All the algorithms will be implemented in the Julia programming language. The course requires some mathematical maturity and assumes prior exposure to multivariable calculus, linear algebra, and probability concepts, although all these concepts will be reviewed during the course.

  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 :

  Derivatives and Gradient, Bracketing, Local Descent, First-Order Methods, Second-Order Methods, Direct Methods, Stochastic Methods

  Mode de contrôle des connaissances :

  • Brief Written Examination
  • Project-Based Assignment

  Bibliographie-lectures recommandées

  Mykel J. Kochenderfer and Tim A. Wheeler. Algorithms for Optimization. MIT Press

  https://mitpress.mit.edu/9780262039420/algorithms-for-optimization/   https://algorithmsbook.com/optimization/files/optimization.pdf

• Exact algorithms for NP-complete and hard problems

  Exact algorithms for NP-complete and hard problems

  Ects : 3

  Enseignant responsable :
  

  • MICHAIL LAMPIS

  Volume horaire : 15

  Description du contenu de l'enseignement :

  The course presents the main techniques and tools for the design and analysis of exact algorithms for NP-complete/hard problems, as well as examples of applications of such algorithms and 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 :

  • Exact solution methods (Dynamic programming, Search trees, Enumeration, Inclusion – exclusion, Local search) and tools for their complexity evaluation
  • Applications (Coloring, TSP, Independent Set, Cut, Set Covering)
  • Techniques for the design of parameterized algorithms (Kernelization, Search trees, Random separation, Color coding, etc.)
  • Applications (Vertex cover, Feedback vertex set, k-Covering, etc.)

  Bibliographie-lectures recommandées

  • Exact solution methods (Dynamic programming, Search trees, Enumeration, Inclusion – exclusion, Local search) and tools for their complexity evaluation
  • Applications (Coloring, TSP, Independent Set, Cut, Set Covering)
  • Techniques for the design of parameterized algorithms (Kernelization, Search trees, Random separation, Color coding, etc.)
  • Applications (Vertex cover, Feedback vertex set, k-Covering, etc.)

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 :
  

  • Michel NAKHLA

  Volume horaire : 15

  Description du contenu de l'enseignement :

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

  Compétences à acquérir :

  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 ainsi qu ’ aux systèmes de santé à travers les outils les outils de la recherche opérationnelle.

  Bibliographie-lectures recommandées

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

  • KEVIN LEVILLAIN
  • BLANCHE SEGRESTIN

  Volume horaire : 15

  Description du contenu de l'enseignement :

  L ’ entreprise est devenue un vecteur puissant de transformation du monde, avec des effets positifs (pour trouver des solutions innovantes aux défis climatiques par exemple) ou négatifs (par les inégalités ou les dommages écologiques qu ’ elle peut créer). Faute d ’ avoir intégré cette capacité de transformation de l ’ entreprise, les théories classiques de l ’ entreprise et les schémas classiques de gouvernance de l ’ entreprise ont pu contribuer à amplifier les déséquilibres plutôt qu ’ à favoriser les effets positifs. Mais les avancées récentes de la recherche permettent aujourd ’ hui de proposer de nouvelles théories de l ’ entreprise, qui inspirent de nouveaux modèles de gouvernance et des réformes inédites en France et dans le monde. L ’ objectif du cours est de présenter une nouvelle approche de l ’ entreprise, fondée sur l ’ innovation. L ’ entreprise n ’ est réductible ni à une organisation commerciale, ni à une combinaison des facteurs de production que seraient le capital et le travail. Elle doit être reconnue comme un dispositif de création collective, qui vise à régénérer régulièrement et de façon coordonnée, les produits, les techniques, les métiers, les méthodes, etc. Cette approche permet 1) d ’ être plus cohérent avec les transformations historiques des organisations capitalistes, 2) de mieux comprendre les formes émergentes de gouvernance d ’ entreprise ; mais aussi 3) de fonder de nouveaux cadres de la responsabilité et par là même de caractériser les conditions d ’ une entreprise responsable, capable de concilier performance, innovation collective et intérêt collectif.

  Le cours suit une progression en 4 parties :

   

  1. Les enjeux contemporains de gouvernance

  Puissance transformationnelle des entreprises dans le monde Explosion des nouvelles formes d ’ entreprise et des schémas de gouvernance

   

  2. L ’ entreprise moderne : sources historiques et cadres théoriques

  Principaux cadres théoriques de l ’ entreprise et leurs points aveugles ; Naissance de l ’ entreprise moderne et du management; dispositif de création collective

   

  3. Relire les mutations de l ’ entreprise

  Évolutions parallèles des doctrines de gouvernance (corporate governance) et de responsabilité de l ’ entreprise (RSE) et leurs limites Transformation de l ’ actionnariat et de l ’ écosystème de l ’ entreprise

   

  4. Innovation responsable : formes alternatives d ’ entreprise et réformes en cours

  Entreprises hybrides ; benefit corporations, entreprise à mission … Nouvelles approches de la responsabilité et nouveaux schémas d ’ entreprise

  Compétences à acquérir :

  • Principales théories de l ’ entreprise et éléments sur le développement historique de l ’ entreprise moderne ;
  • Sensibilisation au droit des sociétés
  • Introduction aux fondements et aux enjeux contemporains de gouvernance d ’ entreprise
  • Repères sur la variété des formes d ’ entreprises et les mutations actuelles : formes classiques des sociétés, alternatives, formes hybrides …
  • Modèle et pratiques de l ’ entreprise à mission

  En savoir plus sur le cours :

  Le cours suit une progression en 4 parties (voir le plan). Pour chacune d ’ elle, il est prévu une alternance de cours, d ’ atelier, de conférence et le cas échéant de discussion par les étudiants d ’ articles de référence. La participation au cours peut impliquer la lecture d ’ articles et la préparation d ’ exposé pour échanger au sein de la classe. Dans ce cas, la participation orale est prise dans compte dans l ’ évaluation. Dans tous les cas, un examen final est prévu. Il comporte deux volets : - un questionnaire sur les principales notions vues au cours de la semaine ; - la discussion d ’ un article portant sur l ’ entreprise, ses transformations et ses modes de gouvernement.

• Conception et dynamique des organisations (Ecole des Mines)

  Conception et dynamique des organisations (Ecole des Mines)

  Ects : 3

  Enseignant responsable :
  

  • Cedric DALMASSO

  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)

• Research workshop Decision aiding: procedures, models and approaches

  Research workshop Decision aiding: procedures, models and approaches

  Ects : 20

  Enseignant responsable :
  

  • DANIEL VANDERPOOTEN
  • Hassan AISSI
  • SONIA TOUBALINE
  • BRICE MAYAG

  Volume horaire : 30

  Description du contenu de l'enseignement :

  This research seminar is centred on themes linked to decision aiding that may vary from year to year. For instances, these themes may include:

  • dealing with a practical decision aiding problem linked to an internship,
  • theoretical or experimental comparison of various techniques or approaches,
  • studying new decision aiding techniques, especially techniques dealing with multiple criteria,
  • axiomatic and theoretical developments motivated by decision aiding problems or techniques,
  • investigating general research questions, e.g., properly taking imprecision or uncertainty into account or the development and validation of elicitation techniques.

  Themes are chosen each year depending on the wishes of students and the availability of internships. Students following this research seminar as a secondary choice are involved through the critical analysis or research articles, performing experiments, implementing techniques. They are also invited to suggest personal research topics. Students following this reasearch seminar are expected to play an active role. The central aim of the research seminar is to help students learn about doing research.
• Research workshop Decision and Artificial Intelligence

  Research workshop Decision and Artificial Intelligence

  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 :

  The aim of this workshop is to give the students an idea of research issues at the boarder of Artificial Intelligence and decision theory. During the first half of the workshop, the teachers present different research topics, by giving some the elements allowing to understand the problematics. During the second half, the students present their work on the subject they chose. Subjects vary from year to year, but the following list gives an idea of the usual topics:

  • preference modelling
  • preference learning
  • preference aggregation
  • computational social choice: voting, fair division
  • algorithmic decision theory
  • data mining and machine learning
  • distributed decision making
  • knowledge representation and reasoning
  • algorithms for heuristic search, planning and game playing
• Research workshop Algorithms with performance guarantees

  Research workshop Algorithms with performance guarantees

  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 :

  This research workshop focuses on complexity theory, exact and parameterized algorithms, approximation theory, dynamic optimization models and algorithmic games. Its connecting thread is the solution of discrete problems coming for several combinatorial optimization models by algorithms that guarantee several types of requirements (time, space, solution ’ s quality, etc.). All these themes lead to several proposals for Master dissertations.
• Research workshop Mathematical Programming

  Research workshop Mathematical Programming

  Ects : 20

  Enseignant responsable :
  

  • ROLAND GRAPPE

  Volume horaire : 30

  Description du contenu de l'enseignement :

  Research workshop centered on Mathematical Programming to solve combinatorial optimisation problems.
• 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 :

  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.

Ateliers de recherche secondaires (2 au choix)

• Research workshop Decision aiding: procedures, models and approaches

  Research workshop Decision aiding: procedures, models and approaches

  Ects : 5

  Enseignant responsable :
  

  • DANIEL VANDERPOOTEN
  • SONIA TOUBALINE
  • Hassan AISSI
  • BRICE MAYAG

  Volume horaire : 30

  Description du contenu de l'enseignement :

  This research seminar is centred on themes linked to decision aiding that may vary from year to year. For instances, these themes may include:

  • dealing with a practical decision aiding problem linked to an internship,
  • theoretical or experimental comparison of various techniques or approaches,
  • studying new decision aiding techniques, especially techniques dealing with multiple criteria,
  • axiomatic and theoretical developments motivated by decision aiding problems or techniques,
  • investigating general research questions, e.g., properly taking imprecision or uncertainty into account or the development and validation of elicitation techniques.

  Themes are chosen each year depending on the wishes of students and the availability of internships. Students following this research seminar as a secondary choice are involved through the critical analysis or research articles, performing experiments, implementing techniques. They are also invited to suggest personal research topics. Students following this reasearch seminar are expected to play an active role. The central aim of the research seminar is to help students learn about doing research.
• Research workshop Decision and Artificial Intelligence

  Research workshop Decision and Artificial Intelligence

  Ects : 5

  Enseignant responsable :
  

  • ALEXANDROS TSOUKIAS
  • STEPHANE AIRIAU
  • JEROME LANG
  • STEFANO MORETTI
  • GABRIELLA PIGOZZI
  • MELTEM OZTURK ESCOFFIER

  Volume horaire : 30

  Description du contenu de l'enseignement :

  The aim of this workshop is to give the students an idea of research issues at the boarder of Artificial Intelligence and decision theory. During the first half of the workshop, the teachers present different research topics, by giving some the elements allowing to understand the problematics. During the second half, the students present their work on the subject they chose. Subjects vary from year to year, but the following list gives an idea of the usual topics:

  • preference modelling
  • preference learning
  • preference aggregation
  • computational social choice: voting, fair division
  • algorithmic decision theory
  • data mining and machine learning
  • distributed decision making
  • knowledge representation and reasoning
  • algorithms for heuristic search, planning and game playing
• Algorithms with performance guarantees

  Algorithms with performance guarantees

  Ects : 5

  Enseignant responsable :
  

  • EVANGELOS PASCHOS
  • FLORIAN SIKORA
  • MICHAIL LAMPIS
  • CRISTINA BAZGAN
  • LAURENT GOURVES

  Volume horaire : 30

  Description du contenu de l'enseignement :

  This research workshop focuses on complexity theory, exact and parameterized algorithms, approximation theory, dynamic optimization models and algorithmic games. Its connecting thread is the solution of discrete problems coming for several combinatorial optimization models by algorithms that guarantee several types of requirements (time, space, solution ’ s quality, etc.). All these themes lead to several proposals for Master dissertations.
• Research workshop Mathematical Programming

  Research workshop Mathematical Programming

  Ects : 5

  Enseignant responsable :
  

  • ROLAND GRAPPE

  Volume horaire : 30

  Description du contenu de l'enseignement :

  The aim of this workshop is to give the students an idea of research issues at the boarder of Artificial Intelligence and decision theory. During the first half of the workshop, the teachers present different research topics, by giving some the elements allowing to understand the problematics. During the second half, the students present their work on the subject they chose. Subjects vary from year to year, but the following list gives an idea of the usual topics:

  • preference modelling
  • preference learning
  • preference aggregation
  • computational social choice: voting, fair division
  • algorithmic decision theory
  • data mining and machine learning
  • distributed decision making
  • knowledge representation and reasoning
  • algorithms for heuristic search, planning and game playing
• 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

  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.

Séminaires de Recherche