Le parcours vise à donner une solide formation orientée vers l'aide à la décision (AD) et la recherche opérationnelle (RO). L'accent est mis non seulement sur la maîtrise des concepts et outils relevant au sens large de la recherche opérationnelle et de l'aide à la décision, sur les techniques informatiques qui leur sont liées, mais aussi sur les aspects méthodologies et les conditions d'insertion des méthodes et outils dans les organisations.
Les objectifs de la formation :
Ce master est une formation par la recherche, qui offre des débouchés professionnels et académiques. En effet, la formation met l'accent sur les capacités à manier l'abstraction, à poser une problématique, à exercer un regard critique, à concevoir ou adapter des solutions. Ces capacités, essentielles pour des carrières académiques, le sont également pour les débouchés professionnels visés.
L'étudiant titulaire de ce Master s'insère naturellement dans :
ECTS : 15
ECTS : 3
Description du contenu de l'enseignement :
L’objectif de ce cours est de présenter les méthodes générales classiques permettant d’établir des algorithmes d'approximation ainsi que des résultats de non-approximation pour des problèmes d'optimisation.
Présenter le lien entre un problème de décision et d'optimisation
Présenter les classes de problèmes d'optimisation sémantiques (en fonction du rapport d'approximation) et syntaxiques (en fonction de la formulation logique) et la liaison entre les deux types de classes
Résultats d’approximation pour des problèmes d'optimisation classiques (Voyageur de commerce, Stable, Couverture de sommets et d’ensembles, Coloration, Satisfiabilité, Sac à dos)
Notions de réduction préservant le rapport d'approximation et son utilisation pour l'obtention de résultats d'approximation et non-approximation
Présenter de nouveaux paradigmes d’approximation, notamment l’approximation modérément exponentielle et l’approximation paramétrée
Bibliographie, lectures recommandées :
Bibliographie
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag, 1999.
D. Hochbaum, Approximation Algorithms for NP-Hard Problems, Course Technology, 1996.
V. Th. Paschos, Complexité et Approximation Polynomiale, Hermès, 2004.
V. Vazirani, Approximation Algorithms, Springer-Verlag, 2001.
ECTS : 3
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.
Compétence à acquérir :
- Apply basic machine learning techniques in the context of optimization problems.
- Understand the use of machine learning in derivative-free optimization.
- Learn the main success stories of machine learning on combinatorial problems.
Mode de contrôle des connaissances :
Written exam.
Bibliographie, lectures recommandées :
Y. Bengio, A. Lodi, A. Prouvost. Machine learning for combinatorial optimization: a methodological tour d'horizon, 2021.
S. Jegelka. Theory of Graph Neural Networks: Representation and Learning, 2022.
J. Larson, M. Menickelly, S. M. Wild. Derivative-free optimization methods, 2019.
ECTS : 3
Description du contenu de l'enseignement :
Le but de ce cours est de présenter plusieurs classes de graphes bien connus et de les étudier d’un point de vue structurel (théorème de caractérisation) et algorithmique.
On étudiera entre autres les classes de graphes suivants :
Graphes d’intervalles
Graphes triangulés
Graphes de permutation
Graphes de comparabilité
Graphes planaires
Graphes de largeur d’arbre bornée
Graphes parfaits
En ce qui concerne l’aspect structurel, on présentera les notions suivantes : sommet simplicial, séparateur, schéma d’élimination, triple astéroïdal, mineur, largeur d’arbre, largeur de clique, graphes d’intersection, orientation transitive, caractérisation par sous-graphes induits interdits, décomposition arborescente, k-arbre partiel, … Pour l’aspect algorithmique, on envisage d’étudier entre autres les problèmes suivants : problème de reconnaissance de ces classes de graphes, problème de coloration, problème de la clique maximum, problème du stable maximum, problème du voyageur de commerce, etc.
Bibliographie, lectures recommandées :
Bibliographie
M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Second edition, Academic Press, New York, 2004, Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
A. Brandstädt, V. B. Le and J. P. Spinrad Graph Classes: A Survey SIAM Monographs on Discrete Mathematics and Applications, 1999.
Description du contenu de l'enseignement :
Cet atelier de recherche est centré sur la théorie de la complexité, la résolution exacte et paramétrée, l’approximation, les modèles dynamiques en optimisation combinatoire et les jeux algorithmique. Fil conducteur de l’atelier est la résolution de problèmes issus des divers modèles discrets par des algorithmes avec garanties de performance (en temps, espace, qualité de solution, etc.).
Les différents thèmes abordés chaque année donnent lieu à un mémoire de Master ou à un mémoire secondaire.
Description du contenu de l'enseignement :
Cet atelier de recherche est centré sur quelques thèmes variables d’année en année mais ayant toujours trait à l’aide à la décision. Ces thèmes peuvent avoir pour point d’appui :
un cas concret faisant l’objet d’un stage de Master ;
des expériences visant à valider certaines hypothèses ;
la comparaison, expérimentale ou théorique, de diverses techniques ou approches susceptibles de traiter un même problème ;
l’étude de procédures ou méthodes nouvelles, en particulier multicritères ;
l’examen de problèmes d’ordre théorique, notamment axiomatique ;
des réflexions et analyses menées sur des thèmes généraux tels que la prise en compte de la mauvaise connaissance, l’insertion des méthodes dans les processus de décision, le mode de validation de certains types de résultats …
Les thèmes sont choisis en relation avec les étudiants et sont centrés sur les mémoires de Master. Les étudiants qui choisissent cet atelier à titre secondaire sont associés à ces thèmes soit par des analyses critiques- d’articles ou de travaux divers, soit par des réalisations d'expériences ou des mises en œuvre de méthodes ou encore, s’ils le souhaitent, par des recherches plus personnelles.
Description du contenu de l'enseignement :
L'objectif de cet atelier est de présenter aux étudiants des problèmes de recherche à la frontière de l'intelligence artificielle et de la théorie de la décision. L'atelier se présente en deux parties: une première durant laquelle les intervenants présentent les différents sujets de recherche (en donnant des éléments pour pouvoir situer la problématique), une deuxième durant laquelle les étudiants présentent leurs travaux sur les sujets choisis. Les sujets peuvent varier chaque année, mais la liste suivante donne une idée des thématiques habituellement abordées:
modélisation des préférences non-classiques
apprentissage de préférences, classification
théorie de la décision algorithmique
fouille de données et extraction de connaissances
décision distribuée automatisée (systèmes multiagents, argumentation, négociation)
décision séquentielle et révisable
Description du contenu de l'enseignement :
intéressons :
aux processus de production de connaissances liés à la construction des instruments de gestion et d’aide à la décision au sein des organisations ;
aux processus de création, de diffusion et d’adoption des outils et modèles considérés comme innovations managériales ;
au double-rôle des outils et des modèles dans les organisations : moyen de pilotage et de coordination, vecteurs d’exploration et d’apprentissage.
Ces questions seront explorées à partir de situations de gestion et d’aide à la décision (gestion de projet, relations contractualisées de type clients-fournisseurs, planification des activités et planification stratégique, relations entre firmes, processus de conception et d’aide à la décision, etc.) et seront éclairées par différentes familles théoriques (théorie de la décision, sociologie cognitive, théories de l’apprentissage, théories des organisations, approches socio-économiques).
Les séances seront structurées autour des sujets de mémoire choisis par les étudiants qui auront par ailleurs, un certain nombre de textes à étudier. Des interventions théoriques seront ponctuellement assurées par les responsables de l’atelier pour apporter les éléments fondamentaux nécessaires.
Description du contenu de l'enseignement :
Cet atelier de recherche est centré sur la programmation mathématique pour la résolution des problèmes d’optimisation combinatoire. En exploitant la structure combinatoire d’un problème, notamment grâce à la théorie des graphes, l’approche polyédrale permet de révéler des liens entre les propriétés algorithmiques et les propriétés géométriques du problème. Parmi les problèmes considérés, par exemple pour leurs applications en conception de réseaux de télécommunication, on retrouve les problèmes classiques tels que la coloration de graphe, les multiflots/multicoupes, ou la connexité.
Différents thèmes sont abordés chaque année donnant lieu à un mémoire de Master ou à un mémoire secondaire.
ECTS : 3
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.
ECTS : 3
Description du contenu de l'enseignement :
Curriculum:
* Introduction : concepts of uncertainty, risk, and preference
* EU and SEU models and attitudes towards risk.
* Descriptive limits of EU and extensions RDU, CEU, WEU, and SSB.
* Sequential decision making, graphical models, Bellman optimality principle, consequentialist and resolute choice approachs.
* Classic decision criteria for decision making under uncertainty (Wald, Hurwicz, Laplace, …), and possibilistic decision making.
* Elicitation/Learning of decision models.
Contenu :
* Introduction : concepts d'incertitude et de risque, préférence
* Modèles EU, SEU et attitudes vis-à-vis du risque.
* Limites descriptives de EU et extensions RDU, CEU, WEU, et SSB.
* Décision séquentielle, modèles graphiques, principe d’optimalité de Bellman, approches conséquentialistes et de choix résolus.
* Critères classiques de la décision dans l'incertain (Wald, Hurwicz, Laplace, …), et décisions possibilistes.
* Élicitation/Apprentissage des modèles décisionnels.
Compétence à acquérir :
Objectives: Most economic decisions are taken in an uncertain environment, in which the consequences of decisions are not known with certainty, such as investment or insurance decisions. This course aims to introduce the fundamental concepts of decision theory in an uncertain environment, as well as classical resolution models.
Objectifs : La plupart des décisions économiques se prennent dans un environnement incertain, dans lequel les conséquences des décisions ne sont pas connues avec certitude, comme par exemple des décisions d'investissement ou d'assurance. Ce cours vise à présenter aux étudiants les concepts fondamentaux de la théorie de la décision en environnement incertain, ainsi que les modèles classiques de résolution.
Mode de contrôle des connaissances :
A 2-hour written exam.
Bibliographie, lectures recommandées :
* von Neumann, John and Oskar Morgenstern,Theory of Games and Economic Behaviour, Princetown University Press, 1947.
* Savage, Leonard J., The Foundations of Statistics, Dover, 1954.
* Puppe, C., Distorted probabilities and choice under risk (Vol. 363). Springer Science & Business Media, 1991.
* Barbera, S., Hammond, P.J., & Seidl, C. Editors, Handbook of Utility Theory: Volume 2: Extensions. Springer Science & Business Media, 1998.
* Barbera, S., Hammond, P.J., & Seidl, C. Editors, Handbook of Utility Theory: Volume 1: Principles. Springer Science & Business Media, 1998.
ECTS : 3
ECTS : 3
Description du contenu de l'enseignement :
Cet enseignement vise à montrer la richesse des concepts et outils issus de la théorie des graphes pour la modélisation et la résolution de nombreux problèmes concrets. Outre l’étude d’algorithmes et de leurs fondements théoriques, on montrera comment les concepts issus des graphes permettent de modéliser, de façon plus ou moins directe, certaines situations concrètes en les ramenant par exemple à un des problèmes classiques ou à un problème voisin.
Concepts de base de théorie des graphes,
Etude de problèmes classiques de couplage, couverture, stable
Différents problèmes de flot
Problèmes de coloration
Applications
Bibliographie, lectures recommandées :
R. Ahuja, T. Magnanti and J. Orlin. Networks Flows, Theory, Algorithms, Applications. Prentice Hall, Englewood Cliffs, New Jersey (1993).
M. Gondran et M. Minoux. Graphes et algorithmes, Eyrolles, 2009, 4e édition.
L. Lovasz, M. D. Plummer, Matching Theory, Elsevier Science Ltd, 1986
ECTS : 3
Description du contenu de l'enseignement :
L’objectif est d’analyser des problèmes d’optimisation mettant en jeu plusieurs agents. Les actions/décisions d’un agent ont un impact sur son utilité propre mais aussi sur celle des autres agents. Le comportement des agents, les solutions atteintes et leur qualité peuvent être analysés à l’aide d’outils issus de la théorie des jeux et de l’optimisation.
Le cours concerne principalement les jeux stratégiques. On donne des définitions et principaux concepts de solution (équilibres). On analyse ensuite les jeux de congestion, leur pouvoir de modélisation, existence d’un équilibre de Nash pur, calcul d’équilibres, etc. Ensuite, on discute des principales mesures de la qualité des équilibres que sont le prix d’anarchie et de stabilité.
Compétence à acquérir :
Bases en théorie des jeux algorithmique.
Bibliographie, lectures recommandées :
E. Tardos, T. Roughgarden, V. Vazirani, Algorithmic Game Theory, Cambridge University Press, 2007
D. Easley, J. Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World , Cambridge University Press (2010)
ECTS : 3
Description du contenu de l'enseignement :
Cet enseignement vise à présenter les modèles industriels de production et de conception. Il est d'abord centré sur les différents problèmes de rationalisation industrielle.
Sont étudiées différentes catégories de modèles et leurs techniques actuelles de résolution ainsi que les situations où ces problèmes se posent. Par ailleurs sont présentés les principaux systèmes de production : gestion des flux, planification, outils assistés par ordinateur,... et leur évolution face à un monde industriel dominé davantage aujourd'hui par des stratégies de conception et d'innovation. L'accent est principalement mis sur les conditions d'applicabilité de ces techniques et l'on distinguera les modèles basés sur le raisonnement et ceux basés sur l'organisation.
Bibliographie, lectures recommandées :
Bibliographie
M. Nakhla : L’essentiel du management industriel, Dunod 2009, 2ème Ed
JC. Moisdon, M. Nakhla : RO : Méthodes d’optimisation en gestion, presses des mines, 2010
A. Hatchuel, P. Lemasson, B. Weil : Processus d’innovation, Hermes 2006
ECTS : 3
Description du contenu de l'enseignement :
Ce cours vise à présenter les principaux concepts et méthodes utiles pour la modélisation des préférences et l'aide multicritère à la décision.
Modélisation des préférences (langage de la modélisation des préférences, principales structures, représentation numérique, extensions)
Introduction à quelques procédures de vote
Théorie de l’utilité multiattribut (résultats de base, procédures directes, procédures indirectes : méthode UTA, Intégrale de Choquet)
Méthodes de surclassement: (ELECTRE TRI)
Méthodes d'élicitation des paramètres
Compétence à acquérir :
Maitrise des principes et outils de modélisation des préférences
Mode de contrôle des connaissances :
Examen écrit de 2h
Bibliographie, lectures recommandées :
Bibliographie
B. Roy et D. Bouyssou, Aide Multicritère à la Décision: Méthodes et Cas. Economica, Paris, 1993.
B. Roy, Méthodologie multicritère d’aide à la décision, Economica, Paris, 1985
Vincke Ph. (1989), L'Aide Multicritère à la Décision, Editions Editions Ellipses, Bruxelles.
Roubens, M. and Ph. Vincke (1985), Preference Modelling, Lecture Notes in Economics and Mathematical Systems n° 250, Springer Verlag, Berlin.
Sen A.K. (1986), Social choice theory, in K.J. Arrow and M.D. Intriligator (eds.), Handbook of Mathematical Economics III, North-Holland, Amsterdam, 1073-1181
French S. (1993) Decision Theory - An Introduction to the Mathematics of Rationality, Ellis Horwood, chapitre 4.
D. Bouyssou, Th. Marchant, M. Pirlot, P. Perny, A. Tsoukiàs, et Ph. Vincke. Evaluation and decision models: a critical perspective, Kluwer 2000.
ECTS : 3
Description du contenu de l'enseignement :
Le cours vise à présenter des modélisations originales de différents problèmes concrets de décision. Il s'agit de développer les aptitudes des étudiants à élaborer et mettre en œuvre des modèles pertinents face à une situation de décision.
Concept de modèle en aide à la décision. Modèle des solutions et modèle des préférences.
Description du processus de modélisation et de ses différentes phases.
Présentation de modélisations non triviales de problèmes de décision utilisant divers cadres de modélisation (graphes, programmation linéaire, multicritère,...).
Utilisation de variables 0-1 en programmation linéaire
Présentation d'outils de modélisation et de résolution (modeleurs et solveurs).
Compétence à acquérir :
Bibliographie, lectures recommandées :
Bibliographie
H.P. Williams. Model building in mathematical programming. J. Wiley, New York, 2013. 5ème edition
Ph. Vallin et D. Vanderpooten. Aide à la décision : une approche par les cas. Ellipses, Paris, 2002., 2ème édition
D. Vanderpooten « Modelling in decision aiding ». In D. Bouyssou, E. Jacquet-Lagrèze, P. Perny, R. Slowinski, D. Vanderpooten, and Ph. Vincke (eds), Aiding Decisions with Multiple Criteria: Essays in Honour of Bernard Roy, pages 195–210. Kluwer, 2001.
ECTS : 3
Description du contenu de l'enseignement :
Le cours a comme objectif de faire connaître aux étudiants les méthodes les plus connues pour structurer et formuler un problème de décision et de développer leur capacité de conduire un processus d'aide à la décision.
Processus de décision et processus d'aide à la décision.
Méthodes de structuration orientées à des méthodes d'aide à la décision et méthodes indépendantes.
Formulation d'un problème de décision et choix d'une méthode de résolution.
Évolution et révision d'un problème de décision. Mise à jour.
Construction d'explications et argumentation.
Compétence à acquérir :
Savoir formuler un problème de décision. Maîtriser les outils d'aide à la structuration d'un problème de décision.
Bibliographie, lectures recommandées :
Bibliographie
Keeney R., Valued Focussed Thinking, Wiley, New York, 1992.
Rosenhead R., Rational Analysis of a Problematic World, Wiley, New York, 1997.
ECTS : 3
Description du contenu de l'enseignement :
Ce cours vise à présenter les principaux concepts, résultats et méthodes en optimisation multiobjectifs en général et en optimisation combinatoire multiobjectifs en particulier. On s’intéresse à déterminer, de façon exacte ou approchée, soit l’ensemble des solutions efficaces, soit une solution de meilleur compromis selon les préférences d’un décideur.
Motivation, Concepts fondamentaux (espace des décisions et espace des critères, solutions efficaces, points non dominés...),
Intérêt et limites des fonctions d'agrégation classiques pour déterminer une solution de meilleur compromis (Somme pondérée, Tchebychev, point de référence,...)
Optimisation combinatoire multiobjectifs – Difficultés spécifiques (intraitabilité..)
Méthodes exactes d'énumération de l'ensemble des solutions efficaces (méthodes génériques, méthodes spécifiques)
Méthodes approchées avec garantie
Approches générales pour la détermination d'une solution de meilleur compromis
Compétence à acquérir :
Bibliographie, lectures recommandées :
Bibliographie
M. Ehrgott, Multicriteria Optimization, Springer, 2005, 2nd edition.
Steuer, R. 1985. Multiple Criteria Optimization: Theory, Computation and Application. New York: John Wiley and Sons.
Vanderpooten, D. Multiobjective Programming: Basic Concepts and Approaches. In R. Slowinski and J. Teghem, editors, Stochastic versus Fuzzy Approaches to Multiobjective Mathematical Programming under Uncertainty, pages 7-22, 1990. Kluwer Academic, Dordrecht.
ECTS : 3
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.
Compétence à 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 :
ECTS : 3
Description du contenu de l'enseignement :
- Modélisation et résolution de problèmes à l'aide de la programmation par contraintes : intérêt de la programmation par contraintes, exemples,
- Types de contraintes, principaux algorithmes et heuristiques de résolution
- Utilisation du logiciel professionnel OPL Studio
Compétence à acquérir :
Introduire les concepts fondamentaux de la programmation par contraintes et à étudier la modélisation et la résolution de problèmes à l'aide de la programmation par contraintes.
Bibliographie, lectures recommandées :
Référence(s) :
K. Apt, Principles of Constraint Programming, Cambridge University Press, 2009.
K. Marriott and P.J. Stuckey, Programming with Constraints: An Introduction, The MIT Press, 1998.
E. Tsang, Foundations of Constraint Satisfaction, Academic Press, 1993.
ECTS : 3
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.
Compétence à acquérir :
- Identify the main stochastic programming models
- Understand the scenario formulation in stochastic programming.
- Formulate a problem as a multistage stochastic program.
Mode de contrôle des connaissances :
Written exam
Bibliographie, lectures recommandées :
J. R. Birge and F. Louveaux, Introduction to Stochastic Programming 2nd Edition, 2011.
G. Cornuéjols, J. Pena and R. Tutuncu, Optimization in Finance 2nd Edition, 2018.
A. Shapiro, D. Dentcheva and A. Ruszczynski, Lectures on Stochastic Programming 3rd edition, 2021.
ECTS : 3
Description du contenu de l'enseignement :
L’objectif de ce cours est de se saisir d’un certain nombre de problèmes liés à l’environnement et au développement durable à travers les outils les outils de la recherche opérationnelle.
Optimisation dans l’environnement et développement durable
Planification des maintenances des arrêts des centrales nucléaires
Energie renouvelable, biomasse
Optimisation d’un réseau de chaleur
Modèles d’optimisation et systèmes de santé
Bibliographie, lectures recommandées :
Bibliographie
Copetti et al, A general battery model for PV simulation Progress in Photovoltaics: Research and applications, vol 1, 4, 283-292,1993
Eynard J. Modélisation, optimisation dynamique et commande d’un méthaniseur, inra, 2006
Sandou G. Optimisation d’un réseau de chaleur, Edf/SupElec, 2004.
Nakhla M. La régulation par les instruments des services d’eau en Europe, Presses des mines, 2013
ECTS : 3
Description du contenu de l'enseignement :
En RO-AD, le qualificatif « robuste » se rapporte à une aptitude à résister à des « à peu près » et à des « zones d’ignorances » afin de se protéger d’impacts jugés regrettables tels des dégradations de propriétés qui devaient être préservées. Les solutions optimales qui découlent des modèles classiques de la RO ne possèdent pas nécessairement cette aptitude. Ce cours vise donc à introduire des modèles permettant de répondre à cette préoccupation.
Introduction des concepts de base et illustration de la préoccupation de robustesse à travers des exemples.
Etude des modèles classiques : critères min-max et min-max regret.
Etude du modèle de Bertsimas et Sim.
Etude du modèle basé sur la programmation multi-niveaux.
Bibliographie, lectures recommandées :
Bibliographie
B. Roy, Robustness in operational research and decision aiding: A multi-faceted issue, European Journal of Operational Research 200(3), 629-638, 2010
H. Aissi, B. Roy, Robustness in Multi-criteria Decision Aiding, in Trends in Multiple Criteria Decision Analysis, M. Ehrgott, J.R. Figueira, S. Greco Ed., Springer, 87-121, 2010
H. Aissi, C. Bazgan, and D. Vanderpooten, "Min–max and min–max regret versions of combinatorial optimization problems: A survey", European Journal of Operational Research, 197(2), 427-438, 2009.
ECTS : 3
Description du contenu de l'enseignement :
Objectifs : Enseigner les techniques de la résolution exacte des problèmes NP-difficiles par des algorithmes à complexité non-triviale (dits algorithmes modérément exponentiels) et par des algorithmes paramétrés. Pour chacune de ces techniques, des exemples de problèmes sur lesquels elles sont appliquées seront présentés et discutés.
Complexité au pire des cas
Techniques de résolution exacte (Programmation dynamique, Arbres de recherche, Enumération, Inclusion – exclusion, Recherche locale)
Application à la résolution exacte de problèmes NP-difficiles (Coloration, Voyageur de commerce, Stable, Coupe maximum, Stable maximum, Couverture d'ensembles)
Techniques de l’algorithmique paramétrée (Kernelisation, Arbres de recherche, …)
Application à la résolution paramétrée de problèmes NP-difficiles (Couverture de sommets minimum, Feedback vertex set, k-Couverture de sommets)
Compétence à acquérir :
Bibliographie, lectures recommandées :
Bibliographie
ECTS : 3
Description du contenu de l'enseignement :
In this course we study the basics of computational complexity theory, focusing on time complexity, space complexity, and non-determinism. We discuss standard complexity classes, including P, NP, coNP, PSPACE, and the relations between them. We will explain how the notion of reductions allows us to understand the relative difficulty of two problems, even when both problems are intractable and see how reductions lead to the notion of problems complete for a class. We also study the fundamental notion of NP-completeness and its relatives (such as PSPACE-completeness) and explain what this notion means for computer science in general. If time allows we will also discuss more advanced complexity classes, such as the polynomial hierarchy, the boolean hierarchy, and randomized complexity classes.
Compétence à acquérir :
In the end of this course students will have learned how one can prove that a problem is intractable, what it means for a problem to be NP-complete or complete for another class, and the most important classes of computational complexity.
Bibliographie, lectures recommandées :
Bibliography
S. Arora, B. Barak, Computational Complexity. A modern approach, Cambridge University Press, 2009.
M.R Garey, D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W. H. Freeman, 1979.
C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
ECTS : 3
Description du contenu de l'enseignement :
De nombreux contextes de décision individuelle ou collective font intervenir des problèmes algorithmiquement difficiles, soit en raison de la combinatoire des choix possibles, soit en raison des problèmes de résistance aux comportements stratégiques. Ce cours a donc pour objectif d'aborder les principales classes de problèmes et de méthodes algorithmiques en théorie de la décision et en choix social, et d'en donner quelques classes d'applications.
représentation de préférences et optimisation sur des domaines combinatoires (CP-nets et extensions, GAI-nets, problèmes de satisfaction de contraintes valués; applications)
algorithmique de la décision séquentielle : planification, processus décisionnels de Markov totalement ou partiellement observables, diagrammes d'influence
aspects algorithmiques du vote : calcul de règles de vote difficiles, vote sur domaines combinatoires; résistance computationnelle aux comportements stratégiques, communication et préférences incomplètes
partage de ressources : enchères combinatoires (langages d'élicitation, calcul de l'allocation optimale), partage équitable.
Bibliographie, lectures recommandées :
Bibliographie
Concepts et méthodes pour l'aide à la décision (D. Bouyssou, D. Dubois, M. Pirlot, H. Prade, editeurs), Hermès - Lavoisier
Handbook of Constraint Programming (T. Walsh, F. Rossi, editeurs), Elsevier
Handbook of Social Choice and Welfare (K. Arrow, A. Sen, K. Suzumura éditeurs), Elsevier
ECTS : 3
Description du contenu de l'enseignement :
Ce cours est une introduction à l'ordonnancement, dont on trouve des applications dans le domaine de la production de biens et de services, mais également en informatique, dans le domaine hospitalier, en télécommunications, etc. Les notions fondamentales et les propriétés des ordonnancements, qui sont indépendantes des domaines d'application, seront d'abord présentées. Elles serviront de base à l'introduction d'algorithmes spécifiques, exacts et approchés, pour résoudre des problèmes mono-critères et multicritères. L'ordonnancement en présence de données incertaines sera également présenté.
Classification des problèmes d'ordonnancement : tâches, ressources, contraintes, critères, représentation d'un ordonnancement, ordonnancement à machines parallèles, problèmes d'atelier.
Algorithmes classiques en ordonnancement : méthodes exactes et approchées avec ou sans garantie de performance.
Introduction à l'ordonnancement multicritère : problèmes à une machine.
Ordonnancement en contexte incertain (si le temps restant le permet) : flexibilité et robustesse en ordonnancement, maximisation d'indicateurs de robustesse.
Compétence à acquérir :
Voir ci-dessous
Mode de contrôle des connaissances :
Un examen de deux heures
Bibliographie, lectures recommandées :
Bibliographie :
P. Brucker, Scheduling algorithms, Springer, 2007
P. Esquirol et P. Lopez, L’ordonnancement, Economica, 1999
Groupe GOThA, Modèles et Algorithmes en Ordonnancement, Ellipses, 2004.
M.L. Pinedo, Planning and Scheduling in Manufaturing and Services, Springer, 2005
J-C. Billaut, A. Moukrim et E. Sanlaville. Flexibilité et robustesse en ordonnancement, Lavoisier, 2005
V. T'Kindt et J-C Billaut. Multicriteria Scheduling, Theory, Models and Algorithms, Springer, 2002.