Descriptif des cours
Fundamental courses
- Graphs and applications
Graphs and applications
Ects : 3
Enseignant responsable :
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 :
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).
- Modelling in Decision Aiding - Operational Research
Modelling in Decision Aiding - Operational Research
Ects : 3
Enseignant responsable :
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 :
Knowledge of basic graph algorithms (shortest path, flows,...) and linear programming.
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).
Mode de contrôle des connaissances :
Exam
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.
- Preference Modelling and Multiple Criteria Decision Making
Preference Modelling and Multiple Criteria Decision Making
Ects : 3
Enseignant responsable :
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.
- 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
Optional courses (choose 5)
Courses for the Decision stream
- Decision under uncertainty and decision models
Decision under uncertainty and decision models
Ects : 3
Enseignant responsable :
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 (in particular MDPs), 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 :
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 :
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 :
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 :
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 :
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.
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
- Programmation par contraintes et applications
Programmation par contraintes et applications
Courses for the Combinatorial Optimisation stream
- Complexity Theory
Complexity Theory
Ects : 3
Enseignant responsable :
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 :
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 :
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.
- Geometric Aspects of Discrete Optimization
Geometric Aspects of Discrete Optimization
Ects : 3
Enseignant responsable :
Volume horaire : 15
Description du contenu de l'enseignement :
Depuis son émergence en tant que discipline fondamentale de l'informatique théorique, l'optimisation discrète, ses méthodes et les problèmes qu'elle cherche à résoudre ont souvent été accompagnés de considérations géométriques. Ce cours se penche sur ces aspects géométriques, en particuliers polyédraux, et sur leurs impacts algorithmiques et structurels, depuis les paradigmes fondateurs remontant aux années 1950 jusqu ’ aux plus récents, notamment ceux liés à l ’ émergence des réseaux de neurones. Les questions abordées lors de l'étude de ces différents paradigmes seront les suivantes : d'où proviennent ces aspects géométriques et comment les traduire en propriétés algorithmiques et/ou combinatoires ? Tout au long du cours, des problèmes de recherche ouverts et d'actualité seront mentionnés dans les différents thèmes abordés.
Contenu :
- Polyèdres et relations min-max fortes
- Formulations étendues et protocoles de communication
- Polyèdres dans les réseaux de neurones ReLU
- Géométrie tropicale et réseaux de neurones profonds
Bibliographie-lectures recommandées
- M. Conforti, G. Cornuéjols, and G. Zambelli. Integer Programming. Graduate Texts in Mathematics, 271. Springer International Publishing (2014).
- P. Chervet, R. Grappe, L.-H. Robert. Box-Total Dual Integrality, Box-Integrality, and Equimodular Matrices. Mathematical Programming, 188 (2021).
- J. Huchette, G. Muñoz, T. Serra, C. Tsay. When Deep Learning Meets Polyhedral Theory: A Survey (2023).
- Algorithmic games
Algorithmic games
Ects : 3
Enseignant responsable :
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 :
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 :
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 is concerned with the latest results on exploiting learning techniques as a tool for solving difficult optimization problems. Rather than aiming for a necessarily incomplete review of existing approaches, the course will focus on selected topics where learning techniques (regression/classification, neural networks) can be integrated into an optimization framework. Topics of interest include graph neural networks and differentiable programming, while applications will range between combinatorial and continuous optimization.
Pré-requis obligatoire :
Basics of matrix and vector linear algebra.
Compétences à acquérir :
- Understand the main principles behind the learning tools used in conjunction with optimization solvers.
- Adopt a critical view of results as presented in research papers.
Mode de contrôle des connaissances :
Written exam.
Bibliographie-lectures recommandées
- B. Amos. Tutorial on amortized optimization, Foundations and Trends in Machine Learning (2023)
- S. Jegelka. Theory of Graph Neural Networks: Representation and Learning, ICM (2022)
- L. Scavuzzo, K. Aardal, A. Lodi, N. Yorke-Smith. Machine learning augmented branch and bound for mixed integer linear programming, Mathematical Programming (2024)
- Algorithms for continuous optimization
Algorithms for continuous optimization
Ects : 3
Enseignant responsable :
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 :
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.)
Courses for the Organisation stream
- Operations Research applied to environment and health systems (AgroParisTech)
Operations Research applied to environment and health systems (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 :
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.
Major research workshop - 20 ETCS (choose 1)
- Decision aiding : procedures, models and approaches
Decision aiding : procedures, models and approaches
Ects : 20
Enseignant responsable :
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.
- Artificial Intelligence and Decision
Artificial Intelligence and Decision
Ects : 20
Enseignant responsable :
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 elements making it possible to understand the problematics. Lectures are also given about how to make a research talk or paper. During the second half, students who chose the workshop as a minor 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
Students who follow the workshop as a major will do their internship on a topic related to Artificial Intelligence and Decision Theory. They are expected to attend the same lectures as others and present the work they are doing as interns.
Compétences à acquérir :
- Have a broader knowledge of research issues at the boarder of Artificial Intelligence and Decision Theory.
- Being able to a make a bibliographic review about a research topic.
- Being able to make research presentations and write research papers.
Mode de contrôle des connaissances :
The evaluation is based on a memoir and a defense based on the work the student did during their internship.
- Mathematical Programming
Mathematical Programming
Ects : 20
Enseignant responsable :
Volume horaire : 30
Description du contenu de l'enseignement :
Research workshop centered on Mathematical Programming to solve combinatorial optimisation problems.
- Algorithms with performance guarantee
Algorithms with performance guarantee
Ects : 20
Enseignant responsable :
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.
- Modèles de gestion et dynamique des organisations (Ecole des Mines)
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.
Minor research workshop - 10 ETCS (choose 2)
Research workshops for the Decision stream
- Decision aiding : procedures, models and approaches
Decision aiding : procedures, models and approaches
Ects : 5
Enseignant responsable :
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.
- Artificial Intelligence and Decision
Artificial Intelligence and Decision
Ects : 5
Enseignant responsable :
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 elements making it possible to understand the problematics. Lectures are also given about how to make a research talk or paper. 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
Compétences à acquérir :
- Have a broader knowledge of research issues at the boarder of Artificial Intelligence and Decision Theory.
- Being able to a make a bibliographic review about a research topic.
- Being able to make research presentations and write research papers.
Research workshops for the Combinatorial Optimisation stream
- Mathematical Programming
Mathematical Programming
Ects : 5
Enseignant responsable :
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 guarantee
Algorithms with performance guarantee
Ects : 5
Enseignant responsable :
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 workshops for the Organisation stream
- Modèles de gestion et dynamique des organisations (Ecole des Mines)
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.
Research Seminars
- Optimization Algorithms and Models : theory and applications
Optimization Algorithms and Models : theory and applications
- Preference modelling and multiple criteria decision making
Preference modelling and multiple criteria decision making
Formation année universitaire 2025 - 2026 - sous réserve de modification
Modalités pédagogiques
Les Modalités des Contrôles de Connaissances (MCC) détaillées sont communiquées en début d'année.
La formation est organisée en 2 semestres, chaque semestre permettant de valider 30 ECTS. Les UE proposées sont soit des cours dispensés au premier semestre, soit des ateliers de recherche suivis au second semestre.
Les cours proposés sont des cours de 15h, à 3 ECTS. Outre les cours de tronc commun, les cours se répartissent en 3 listes pour chacune des 3 options. Dans chaque liste 2 cours sont identifiés comme obligatoires.
Au premier semestre, l’étudiant(e) devra suivre 10 cours répartis comme suit :
- 5 cours de tronc commun,
- 2 cours obligatoires propres à son option (les 2 premiers de chaque option)
- 2 cours optionnels choisis parmi la liste des cours de l'option
- 1 cours optionnel choisi parmi tous les cours proposés (y compris les cours obligatoires des autres options)
Au second semestre, l’étudiant(e) choisit un atelier de recherche principal parmi les ateliers de son option (20 ECTS). Il réalisera son stage et mémoire de master au sein de cet atelier. Il choisit également 2 ateliers de recherche secondaires parmi les autres ateliers, au sein desquels il réalisera un mémoire secondaire (2x5 ECTS).
Stages et projets tutorés
Le stage dure 5 mois, du mois de mars au mois d'août. Il est réalisé dans un laboratoire universitaire ou en entreprise, et fait l'objet d'un rapport de stage et d'une soutenance orale.
Des programmes nourris par la recherche
Les formations sont construites au contact des programmes de recherche de niveau international de Dauphine, qui leur assure exigence et innovation.
La recherche est organisée autour de 6 disciplines toutes centrées sur les sciences des organisations et de la décision.
En savoir plus sur la recherche à Dauphine