Photo du professeur

Roland Grappe

Professeur des Universités

roland.grappe(at)lamsade.dauphine.fr

Bureau P625

À propos

Depuis janvier 2025, je suis responsable du pôle Optimisation, Structure & Algorithmes du LAMSADE à l'Université Paris Dauphine-PSL, où je suis Professeur des Universités depuis septembre 2023. J'anime aussi le groupe de recherche Mathis.

Ma recherche porte sur les problèmes d'optimisation combinatoire impliquant graphes et polyèdres, avec un intérêt particulier pour les aspects géométriques et matriciels sous-jacents.

De 2011 à 2023, j'étais Maître de conférences en informatique dans l'équipe AOC du LIPN à l'Université Sorbonne Paris Nord. J'ai commencé à explorer les aspects polyédraux de l'optimisation combinatoire pendant mon post-doctorat à l'Université de Padoue, sous la direction de Michele Conforti. Auparavant, j'ai réalisé ma thèse en théorie des graphes à Grenoble, sous la direction de Zoltán Szigeti.

Sujets de recherche

Articles de journaux

  1. P. Chervet, R. Grappe: A weak box-perfect graph theorem. Journal of Combinatorial Theory, Series B 169: 367-372 (2024).
  2. P. Chervet, R. Grappe, M. Lacroix, F. Pisanu, R. Wolfler Calvo: Hard problems on box-totally dual integral polyhedra. Discrete Optimization 50: 100810 (2023).
  3. M. Barbato, R. Grappe, M. Lacroix, E. Lancini: Box-total dual integrality and edge-connectivity. Mathematical Programming 197(1): 307-336 (2023).
  4. M. Barbato, R. Grappe, M. Lacroix, E. Lancini, R. Wolfler Calvo: The Schrijver system of the flow cone in series-parallel graphs. Discrete Applied Mathematics 308: 162-167 (2022).
  5. P. Chervet, R. Grappe, L.-H. Robert: Box-total dual integrality, box-integrality, and equimodular matrices. Mathematical Programming 188(1): 319-349 (2021).
  6. D. Cornaz, R. Grappe, M. Lacroix: Trader multiflow and box-TDI systems in series-parallel graphs. Discrete Optimization 31: 103-114 (2019).
  7. R. Grappe, M. Lacroix: The st-bond polytope on series-parallel graphs. RAIRO - Operations Research 52(3): 923-934 (2018).
  8. M. Barbato, R. Grappe, M. Lacroix, C. Pira: Lexicographical polytopes. Discrete Applied Mathematics 240: 3-7 (2018).
  9. A. Bernáth, R. Grappe, Z. Szigeti: Partition constrained covering of a symmetric crossing supermodular function by a graph. SIAM Journal on Discrete Mathematics 31(1): 335-382 (2017).
  10. M. Barbato, R. Grappe, M. Lacroix, R. Wolfler Calvo: Polyhedral results and a branch-and-cut algorithm for the double traveling Salesman problem with multiple stacks. Discrete Optimization 21: 25-41 (2016).
  11. S. Borne, P. Fouilhoux, R. Grappe, M. Lacroix, P. Pesneau: Circuit and bond polytopes on series-parallel graphs. Discrete Optimization 17: 55-68 (2015).
  12. Y. Faenza, S. Fiorini, R. Grappe, H. R. Tiwary: Extended Formulations, Nonnegative Factorizations, and Randomized Communication Protocols. Mathematical Programming 153(1): 75-94 (2015).
  13. M. Conforti, A. Del Pia, M. Di Summa, Y. Faenza, R. Grappe: Reverse Chvátal-Gomory Rank. SIAM Journal on Discrete Mathematics 29(1): 166-181 (2015).
  14. J. Gouveia, R. Grappe, V. Kaibel, K. Pashkovich, R. Z. Robinson, R. R. Thomas: Which nonnegative matrices are slack matrices? Linear Algebra and its Applications 439(10): 2921-2933 (2013).
  15. L. Beaudou, R. Grappe and G. Hahn: Gathering information in a graph. J. Combin. Math. Combin. Comput. 85: 65-78 (2013).
  16. A. Bernáth, R. Grappe, Z. Szigeti: Augmenting the Edge-Connectivity of a Hypergraph by Adding a Multipartite Graph. Journal of Graph Theory 72(3): 291-312 (2013).
  17. L. Beaudou, A. Gerbaud, R. Grappe, F. Palesi: Drawing disconnected graphs on the Klein bottle. Graphs and Combinatorics 26(4): 471-481 (2010).
  18. R. Grappe, Z. Szigeti: Covering symmetric semi-monotone functions. Discrete Applied Mathematics 156: 138-144 (2008).

Actes de conférence

  1. R. Grappe, M. Lacroix, S. Martin, The Multiple Pairs Shortest Path Problem for Sparse Graphs: Exact Algorithms. CoDIT 2023: 956-961 (2023).
  2. M. Barbato, R. Grappe, M. Lacroix, E. Lancini, On k-edge-connected Polyhedra: Box-TDIness in Series-Parallel Graphs. ISCO 2020: 27-41 (2020).
  3. J. David, R. Grappe, M. Lacroix, E. Traversi, Self-sufficient sets in smartgrids. Electronic Notes in Discrete Mathematics 69: 301-308 (2018).
  4. M. Barbato, R. Grappe, M. Lacroix, R. Wolfler Calvo: A Set Covering Approach for the Double Traveling Salesman Problem with Multiple Stacks. ISCO 2016: 260-272 (2016).
  5. M. Conforti, A. Del Pia, M. Di Summa, Y. Faenza, R. Grappe: Reverse Chvátal-Gomory Rank. IPCO 2013: 133-144 (2013).
  6. S. Borne, R. Grappe, M. Lacroix: The Uncapacitated Asymmetric Traveling Salesman Problem with Multiple Stacks. ISCO 2012: 105-116 (2012).
  7. Y. Faenza, S. Fiorini, R. Grappe, H. R. Tiwary: Extended Formulations, Nonnegative Factorizations, and Randomized Communication Protocols. ISCO 2012: 129-140 (2012).
  8. A. Bernáth, R. Grappe, Z. Szigeti: Partition constrained covering of a symmetric crossing supermodular function. SODA 2010: 1512-1520 (2010).
  9. R. Grappe, A. Bernáth, Z. Szigeti: Edge-connectivity augmentation of a hypergraph by adding a multipartite graph, Electronic Notes in Discrete Mathematics 34(1): 173-177 (2009).

Thèses

  • R. Grappe: Polyhedra: Some Matricial Perspectives, Habilitation à diriger des recherches, Slides, Université Sorbonne Paris Nord (2021).
  • R. Grappe: Augmentation de l'arête-connexité, Thèse de l'Université de Grenoble (2009).
<

Conférences internationales

  • Totally Equimodular Matrices (ISMP 2024)
  • Characterizations of Box-Totally Dual Integral Polyhedra (SPOC 22 - Invited speaker - Slides - Video)
  • Characterizations of Principally Box-Integer Polyhedra (Aussois 2018)
  • Principally Box-integer Polyhedra and Equimodular Matrices (Franco-Japanese Days on Combinatorics and Optimization 2017 - Invited speaker)
  • Characterizations of Box-Totally Dual Integral Polyhedra (JPOC10 2017)
  • The Trader Multiflow problem: When the cut cone is box-TDI (ICGT 2014)
  • Reverse Chvátal-Gomory Rank (PGMO 2013)
  • Extended formulations, non-negative factorizations and randomized communication protocols (ISCO 2012, ISMP 2012)
  • Polynomial cases of Hypergraph Local Edge-Connectivity Augmentation (Bled'11, ISCO 2012)
  • Partition constrained covering of a symmetric crossing supermodular function (SODA 2010)
  • Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph (EuroComb 2009)
  • Partition constrained covering of a symmetric crossing supermodular function (Workshop Aussois 2009)
  • Covering a symmetric semi-monotone function (BCC 2007)

Conférences nationales

  • Tutorial: Polyhedra Hidden Behind Min-Max Theorems (ROADEF 2023 - Invited speaker)
  • Augmentation de l'arête-connexité d'un hypergraphe en lui ajoutant un graphe multiparti (JGA 11)
  • Augmentation de l'arête-connexité d'un hypergraphe en lui ajoutant un graphe multiparti (JPOC 6)
  • Un problème de surveillance : modélisation et simulation avec la théorie des jeux (ROADEF 2008)

Séminaires

  • Matrices and Polyhedra Hidden Behind Min-Max Relations (2024: Journées du LAMSADE)
  • Totally Equimodular Matrices (2024: Séminaire Parisien d'Optimisation)
  • Tutte's TU signing Theorem (2024: LIPN)
  • Box-Totally Dual Integral Polyhedra (2022: LIPN)
  • On the Proof of the Sensitivity Conjecture (2020: LIPN)
  • Totally Equimodular Matrices (2019: LIPN)
  • Principally Box-integer Polyhedra and Equimodular Matrices (2018: LIS)
  • Principally Box-integer Polyhedra (2017: G-SCOP)
  • Mostly Box-integer Polyhedra and Equimodular Matrices (2017: Lamsade)
  • Complexity Results for Smartgrid Partitionning (2017: EDF Lab)
  • The Trader Multiflow problem: When the cut cone is box-TDI (2014: LIMOS)
  • Reverse Chvátal-Gomory Rank (2013: LIPN, G-SCOP)
  • Extended formulations, non-negative factorizations and randomized communication protocols (2011: LIF, LIPN)
  • Edge-connectivity augmentation (2010: Università di Padova)
  • Augmentation de l’arête-connexité d’un hypergraphe sous contraintes de partition (2009/10: G-SCOP, Lamsade, Equipe C&O)
  • Partition constrained covering of a symmetric crossing supermodular function (2009: CWI)
  • Orientation of graphs (2008: COPPE/UFRJ)
  • Node-to-area connectivity augmentation (2007: University of Waterloo)

Enseignements 2023-2024

Doctorants