Domaine de recherche

Mes travaux de recherche se rattachent au domaine de l'optimisation combinatoire et consistent en la résolution de problèmes d'optimisation basés sur des structures discrètes (généralement un graphe). Ces problèmes reviennent généralement à trouver le meilleur élément dans un ensemble fini. Dans la pratique, de nombreux problèmes peuvent se formuler comme des problèmes d'optimisation combinatoire, notamment les problèmes de transport. Cependant, bien que le nombre de solutions soit fini, l'explosion combinatoire rend impossible la résolution du problème par énumération des solutions. Il est donc nécessaire d'utiliser d'autres méthodes de résolution plus efficaces.

Une des méthodes les plus puissantes pour résoudre les problèmes d'optimisation combinatoire est la méthode dite polyédrale. Elle consiste à décrire l'enveloppe convexe des solutions du problème à l'aide d'inégalités linéaires, ramenant ainsi le problème à un programme linéaire qui peut être résolu en temps polynomial. Si le problème est NP-complet, il y a peu d'espoir de pouvoir décrire l'enveloppe convexe. Cependant, une description partielle peut permettre de développer un algorithme efficace de type coupes et branchements (Branch and Cut) pour résoudre le problème.

Mes travaux de recherche s'appliquent à différents problèmes de transport - tels que le problème de ramassage et livraison préemptif ou le problème du double voyageur de commerce asymétrique avec piles de capacité infinie - et au problème de l'analyse structurelle de systèmes algébro-différentiels.

Publications

Revues internationales

  1. Trader Multiflow and Box-TDI Systems in Series-Parallel Graphs
    D. Cornaz, R. Grappe, M. Lacroix
    Discrete Optimization accepté pour publication (2018)
  2. The Vertex k-cut Problem
    D. Cornaz, F. Furini, M. Lacroix, E. Malaguti, A. R. Mahjoub, S. Martin
    Discrete Optimization accepté pour publication (2018)
  3. The st-bond polytope on series-parallel graphs
    R. Grappe, M. Lacroix
    RAIRO - Operations Research, Vol. 52(3), pages 923-934 (2018)
  4. Lexicographical polytopes
    M. Barbato, R. Grappe, M. Lacroix, C. Pira
    Discrete Applied Mathematics, Vol. 240, pages 3-7 (2018)
  5. Polyhedral results and a branch-and-cut algorithm for the double traveling Salesman problem with multiple stacks
    M. Barbato, R. Grappe, M. Lacroix, R. Wolfler Calvo
    Discrete Optimization, Vol. 21, pages 25-41 (2016)
  6. Circuit and bond polytopes on series-parallel graphs
    S. Borne, P. Fouilhoux, R. Grappe, M. Lacroix, P. Pesneau
    Discrete Optimization, Vol. 17, pages 55-68 (2015)
  7. Robust location transportation problem under uncertain demands
    V. Gabrel, M. Lacroix, C. Murat et N. Remli
    Discrete Applied Mathematics, Vol. 164, Part 1, pages 100-111 (2014)
  8. On the complexity of the Eulerian closed walk with precedence path constraints problem
    H. Kerivin, M. Lacroix et A. R. Mahjoub
    Theoretical Computer Science, Vol. 439, pages 16-29 (2012)
  9. Models for the single-vehicle preemptive pickup and delivery problem
    H. Kerivin, M. Lacroix et A. R. Mahjoub
    Journal of Combinatorial Optimization, Vol. 23, n. 2, pages 196-223 (2012)
  10. On the NP-completeness of the perfect matching free subgraph problem
    M. Lacroix, A. R. Mahjoub, S. Martin et C. Picouleau
    Theoretical Computer Science, Vol. 423, pages 25-29 (2012)
  11. Tree based models and algorithms for the preemptive asymmetric Stacker Crane problem
    H. Kerivin, M. Lacroix, A. Quilliot et H. Toussaint
    RAIRO - Operations Research, Vol. 45, pages 179 - 207 (2011)
  12. Combinatorial Optimization model and MIP formulation for the structural analysis of conditional differential-algebraic systems
    M. Lacroix, A. R. Mahjoub et S. Martin
    Computers & Industrial Engineering (CIE), Vol. 61, pages 422-429 (2011)
  13. The splittable pickup and delivery problem with reloads
    H. Kerivin, M. Lacroix, A. R. Mahjoub et A. Quilliot
    European Journal of Industrial Engineering (EJIE), Vol. 2, n°2, pages 112-133 (2008)

Actes de conférences

  1. Efficient Discontinuous Phrase-Structure Parsing via the Generalized Maximum Spanning Arborescence
    C. Corro, J. Le Roux, M. Lacroix
    Empirical Methods in Natural Language Processings (EMNLP), pages 1644-1654 (2017)
  2. Self-sufficient sets in smartgrids
    J. David, R. Grappe, M. Lacroix, E. Traversi
    Electronic Notes in Discrete Mathematics (ENDM), Vol. 69, pages 301-308 (2018)
  3. Dependency Parsing with Bounded Block Degree and Well-nestedness via Lagrangian Relaxation and Branch-and-Bound
    C. Corro, J. Le Roux, M. Lacroix, A. Rozenknop, R. Wolfler Calvo
    Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) pages 355-366, (2016)
  4. A Set Covering Approach for the Double Traveling Salesman Problem with Multiple Stacks
    M. Barbato, R. Grappe, M. Lacroix, R. Wolfler Calvo
    Proceedings of 4th International Symposium on Combinatorial Optimization (ISCO) 2016. Lecture Notes in Computer Science, Vol. 9849 pages 260-272 (2016)
  5. Mathematical formulations for the Balanced Vertex k-Separator Problem
    D. Cornaz, F. Furini, M. Lacroix, E. Malaguti, A. R. Mahjoub et S. Martin.
    Proceeding of IEEE International Conference Control, Decision and Information Technologies (CoDIT'14) pages 176-181, (2014).
  6. The Uncapacitated Asymmetric Traveling Salesman Problem with Multiple Stacks
    S. Borne, R. Grappe et M. Lacroix
    Lecture Notes in Computer Science, Vol. 7422, pages 105-116 (2012),
    for International Symposium of Combinatorial Optimization (ISCO) (acceptation rate : 40%)
  7. Flow-based mathematical formulation and strengthening cuts for Cumulative CVRP
    S.U. Ngueveu et M. Lacroix
    Proceedings of Odysseus , pages 87-90 (2012)
  8. Polyhedral Analysis and Branch-and-Cut for the Structural Analysis Problem
    M. Lacroix, A. R. Mahjoub et S. Martin
    Lecture Notes in Computer Science, Vol. 7422, pages 117-128 (2012),
    for International Symposium of Combinatorial Optimization (ISCO) (acceptation rate : 40%)
  9. On the complexity of the Eulerian closed walk with precedence path constraints problem
    H. Kerivin, M. Lacroix et A. R. Mahjoub
    Electronic Notes in Discrete Mathematics, Vol. 36, pages 899-906 (2010),
    for International Symposium of Combinatorial Optimization (ISCO)
  10. Recourse problem of the 2-stage robust location transportation problem
    V. Gabrel, C. Murat, N. Remli et M. Lacroix
    Electronic Notes in Discrete Mathematics, Vol. 36, pages 167-174 (2010),
    for International Symposium of Combinatorial Optimization (ISCO)
  11. Structural analysis for Differential-Algebraic Systems : Complexity, formulation and facets
    M. Lacroix, A. R. Mahjoub et S. Martin
    Electronic Notes in Discrete Mathematics, Vol. 36, pages 1073-1080 (2010),
    for International Symposium of Combinatorial Optimization (ISCO)
  12. Résolution heuristique du Stacker Crane Problem préemptif et asymétrique à l'aide d'une Arbre-représentation des tournées
    H. Kerivin, M. Lacroix, A. Quilliot et H. Toussaint Actes de ROADEF, Recueil des articles longs, pages 19-34 (2010).
  13. Structural analysis in Differential-Algebraic Systems and Combinatorial Optimization
    M. Lacroix, A. R. Mahjoub et S. Martin
    Proceedings of 39th International Conference on Computers & Industrial Engineering (CIE39), pages 331-337 (2009).
    Récompense : Best Student Paper Award
  14. The capacitated vehicle routing problem with reloads
    H. Kerivin, M. Lacroix, A. R. Mahjoub et A. Quilliot
    Proceedings of International Conference on Service System and Service Management (IEEE), pages 1513 - 1518 (2006).

Thèse

Le problème de ramassage et livraison préemptif : complexité, modèles et polyèdres Soutenue le 7 décembre 2009.
Composition du jury :
  • A. Ridha Mahjoub, directeur de thèse
  • Alain Quilliot, directeur de thèse
  • Hervé Kerivin, co-encadrant de thèse
  • Michel Gendreau, rapporteur
  • Frédéric Semet, rapporteur
  • Mohamed Haouari, rapporteur
  • Jean-François Maurras, examinateur

Communications dans des conférences

  1. The Trader Multflow problem: When the cut cone is box-TDI (JSPOC 2015, ISCO 2016).
  2. Circuits and bond polytope in series-parallel graphs (JPOC 2013, ISCO 2014).
  3. The Uncapacitated Asymmetric Traveling Salesman Problem with Multiple Stacks (ISCO 2012, JFRO 2012).
  4. Le problème de ramassage et livraison mono-véhicule préemptif asymétrique unitaire : description polyédrale dans les cactus (ROADEF 2010).
  5. The structural analysis problem for differential-algebraic systems (Combinatorial Optimization Workshop Aussois 2010).
  6. Le problème de la grue préemptif asymétrique : polyèdre et algorithme de coupes et branchements (ROADEF 2009).
  7. The single-vehicle preemptive pickup and delivery (Combinatorial Optimization Workshop Aussois 2009).
  8. Le problème de cueillettes et livraisons préemptif avec un véhicule (ROADEF 2008).
  9. The single-vehicle preemptive pickup and delivery (NCP 07).
  10. Formulations pour le problème de cueillettes et livraisons préemptif avec un véhicule (JPOC 4).
  11. The capacitated vehicle routing problem with reloads (International Conference Service System and Service Management (IEEE) 2006).
  12. Le problème de trajets de véhicules avec déchargements/rechargements sous contraintes de capacités (ROADEF 2005).

Séminaires

  1. Résolution du problème de ramassage et livraison mono-véhicule préemptif asymétrique unitaire
    Séminaire à l’Université de Villetaneuse (Paris XIII), Paris, France, le 24 novembre 2009.
  2. Résolution du problème de ramassage et livraison mono-véhicule préemptif asymétrique unitaire
    Séminaire à l’ENSTA, Paris, France, le 20 novembre 2009.
  3. Le problème de ramassage et livraison préemptif avec un véhicule
    Séminaire au LAMSADE, Université Paris-Dauphine, France, le 3 novembre 2008.