Séminaires 2017/2018

Jeudi 10h-12h,

Jeudi 12 Octobre : Salle A701

Jeudi 9 Novembre : Salle D102

Jeudi 7 Décembre : Salle A711

Jeudi 18 Janvier : Salle B205

Jeudi 15 Février : Salle B205

Jeudi 15 Mars : Salle B205

Jeudi 12 Avril : Salle B205

Jeudi 24 Mai : Salle B205

Jeudi 21 Juin : Salle B205

 

COURS 1 (Septembre-Octobre-Novembre)

Titre :Structure et dualité en optimisation combinatoire

Intervenants : Denis Cornaz

Volume horaire : 18h, 6 fois 3h, les Jeudi.

Dates :

Octobre 5 (deux séances 9h-12 et 14h à 17h), Salle A711

12 Octobre (14h à 16h) Salle C108

19 Octobre (deux séances 9h - 12 et 14h à 17h), Salle P303

26 Octobre (9h - 12h) Salle B205

Description: Maîtriser le concept de dualité en optimisation combinatoire et ses applications théoriques principales. Caractérisations par structures interdites.

Contenu:  Théorèmes  primitifs  (ou  fondamentaux)  de  la  théories  des  graphes parfaits et leur imbrication avec la géométrie des polyèdres combinatoires.

Théorème  de  Seymour  sur  le  packing  binaire  (Mengerian  hypergraphs), démonstration du cas graphique. Applications aux multiflots.

Référence  principale:  Combinatorial  Optimization:  Polyhedra  and  Efficiency,

Alexander Schrijver, Springer 2003

Référence  secondaire:

Structures  and  duality in Combinatorial Optimization,

Denis Cornaz (HDR, Paris - Dauphine) 2013.

(http://www.lamsade.dauphine.fr/~cornaz/Rech/HDR.pdf)

 

COURS 2 (Novembre - Janvier)

Titre: Parameterized, Fine-Grained, and Multi-Variate Algorithmics

Intervenants: Eunjung Kim and Michael Lampis

Volume horaire: 18h, 6 fois 3h, les Jeudi de 14h à17h en salle P303

Dates: Novembre 16, 23, 30. Janvier 11, 18, 25.

Description: This course covers a number of modern algorithmic techniques whose main aim is to deal with NP-hard problems. The main approach we will study is based on the idea of analyzing an algorithm's performance as a function of  not  only  the  input  size,  but  also  one  or  more  secondary  variables  (the parameters)  which  quantify  the  structure  of  the  input  instance.  This  analysis allows  us  to  design  algorithms  which,  despite  needing  exponential  time  in  the worst case, can be quite efficient if the values of the parameters are moderate,which is often true in practice. The  course  will  be  divided  into  three  parts.  In  the  first  part,  we  will  cover algorithmic techniques from parameterized algorithms (branching, color-coding, iterative compression), as well as a corresponding complexity theory that allows one  to  determine  the  complexity  of  a  problem  in  a  fine-grained  way  (7,5h).  In the  second  part  we  will  study  advanced  techniques  from  this  domain  and  their applications to various topics, such as satisfiability and graph cuts (7,5h). In the third part, students will be required to read and present a recent paper from the area (3h).

Objectif:

At the end of this course the students will be familiar with some of the most recent algorithmic techniques for designing exact algorithms for NP-hard problems.

Références:

Marek Cygan et al., Parameterized Algorithms (2015) Springer.

 

COURS 3 (Mars-Avril)

Titre:

Simulation agents  pour applications en SHS - aide à la décision

Intervenants :

Juliette Rouchier

Volume horaire: 18h, 3 fois 6h, les Jeudi matin 9h-12h et après midi 14h-17h.

Dates : 1er Mars, 8 Mars et 17 Mai. Salle P303

Motivation  :

Agent-based  simulation  is  used  in  many  applications  of  social analysis and decision-aiding for public policy. Three aspects of the practice will be described  and  analyzed - learning, opinion/innovation diffusion, interaction between  society  and  environment.  Some  application  are  purely  theoretical  and lead  to  discussions  in  social  sciences  (or  more  generally  behavioral  sciences); others  combine  several  technics  and  used  for  ground-based  creation  of institutions and public policies.

Objectif : At the completion of this course, students will be able to:

1. Know the main concepts of ABM simulations, the most used models related to questions that can be addressed and how to interpret results

2. Know the main platforms and how to self-teach on internet (not treated)

References : Bommel P., Bécu N., Le Page C., Bousquet F., 2015. Cormas, an Agent- Based simulation platform for coupling human decisions with computerized dynamics.  In,  T.  Kaneda,  H.  Kanegae,  Y.  Toyoda,  &  P.  Rizzi  (Éd.),  Simulation  and Gaming  in  the  Network  Society.  Volume  9  of  the  series  Translational  Systems Sciences pp 387-410. ( pré-publication)Brenner T., 2006, Agent learning representation: advice on modelling economic learning,  In  :  L.  Tesfatsion  and  K.  L.  Judd, Handbook  of  computational economics  vol.  2:  Agent-based  computational  economics,  Elsevier/North-Holland, Handbooks in Economics Series, 18. Deffuant G., Amblard F., Weisbuch G. and Faure T., 2002, How can extremism prevail?  A  study  based  on  the  relative  agreement  interaction,  JASSS,  5  (4), http:jasss.soc.surrey.ac.uk/5/4/1.htmlJanssen  M.,  Ostrom  E.,  2014,  Vulnerability  of  Social  Norms  to  Incomplete Information,  The  Complexity  of  Social  Norms,  Edmonds  B.  (ed),  Series  in Computational Social Sciences pp 161-173.

 

COURS 4(Avril à Mai)

Title: Metaheuristics and real case applications

Intervenants: Jully Jeunet

Volume horaire: 18h, 6 fois 3h, les Jeudi de14h à17h en salle P303.

Dates : Mai 24, 31. Juin 7, 14, 21 et 28.

The objective is to present some of the most popular metaheuristics for solving combinatorial  problems  with  applications  to  deterministic  real  case  problems, especially  in  operations  management.  We  first  study  singlesolution  stochastic search  algorithms  such  as  simulated  annealing,  tabu  search  and  variable neighbourhood  search.  Population-based  metaheuristics  are  then  introduced, starting  from  genetic  algorithms  to  heuristics  simulating  social  behaviour  of some  organisms,  such as  ant  colony  optimization  or  particle  swarm optimization. For each metaheuristic under analysis, students will select a paper implementing the chosen heuristic for a real case problem close to their research area.This course will result in the ability of the students to identify pros and cons of these heuritics for a given problem and to code them. Planning of sessions Three sessions  will  be  dedicated  to  each  metaheuristic  type  (single-solution  versus population based) starting with a course session to present the principles of the metaheuristics.  The  remainder  of  the  sessions  will  be  used  by  the  students  to present scientific contributions they will select.

Références:E.  Rahimian,  K.  Akartunalı  et  J.  Levine,  2017. A  hybrid  Integer  Programming and  Variable  Neighbourhood  Search  algorithm  to  solve  Nurse  Rostering Problems, European Journal of Operational Research, 258(2), 411-423.V.  Van  Peteghem  ,  M.  Vanhoucke,  2014. An  experimental  investigation  of metaheuristics  for  the  multi-mode  resource-constrained project  scheduling problem  on  new  dataset  instances,  European  Journal  of  Operational  Research, 235(1), 62-72.K.  Sourirajan,  L.  Ozsen,  R.  Uzsoy,  2009.  A  genetic  algorithm  for  a  single product  network  design  model  with  lead  time  and  safety  stock  considerations, European Journal of Operational Research, 197(2), 599-608.

 

COURS 5 par des 3 visiteurs (Décembre, Février et Avril) en salle P303

Titre: Algorithmic Decision Theory

Intervenants: Yannis Dimopoulos, Georgios Chalkiadakis, Carmine Ventre.

Part 1:

Yannis Dimopoulos, University of Cyprus <yannis@cs.ucy.ac.cy>

Volume horaire: 6h (2 fois 3h), Jeudi 14h-17h,

Dates: Décembre 7 et 14

1. Abstract Argumentation

2. Constraint Programming

Part  2:

Georgios  Chalkiadakis,

Technical   University  of  Chania <gehalk@intelligence.tuc.gr>

Volume horaire: 6h (2 fois 3h), Jeudi 14h-17h,

Dates: Février 8et15.

1. A Concise Introduction to Algorithmic Game Theory [3 hours]-Non-cooperative GT- Cooperative GT- GT in multiagent systems research

2. Taking decisions to form (overlapping) coalitions [3 hours]- Overlapping coalition formation

- theoretical background- Overlapping coalition formation in the real world: employing  probabilistic (Bayesian) decision making

Part 3:  Carmine Ventre, University of Essex <c.ventre@essex.ac.uk>,

Volume horaire: 6h (2 fois 3h), Jeudi 14h-17h,

Dates: 29 Mars et 5 Avril.

Broad  survey  of topics  at  the  interface  of  theoretical  computer science  and economics  to  study  decision  making  of  rational  agents,including:  games  in strategic  form  and  equilibrium  concepts;  existenceand  computation  of equilibria; inefficiency of equilibria; mechanism design with and without money (i.e., single-item auctions, Vickreyauction and generalizations, characterizations of truthful mechanisms and applications).