Professor Photo

Roland Grappe

Professor

roland.grappe(at)lamsade.dauphine.fr

Office P625

About

Since September 2023, I am Professor at LAMSADE in Université Paris Dauphine-PSL. I am in the Optimisation, Structure & Algorithms team and I animate the Mathis research group.

My research focuses on combinatorial optimization problems involving graphs and polyhedra, with a particular interest in underlying geometrical and matricial aspects.

From 2011 to 2023, I was an Associate Professor in Computer Science at the AOC team of LIPN in Université Sorbonne Paris Nord. I started exploring polyhedral aspects of combinatorial optimization during my post-doc at the University of Padua, under Michele Conforti's supervision. Previously, I completed my thesis in graph theory in Grenoble, under the guidance of Zoltán Szigeti.

Research topics

Journal papers

  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).

Proceedings

  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).

Theses

  • 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).

International conferences

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

National conferences

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

Lectures

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

Teaching 2023-2024

PhD Students