---

Frédéric Roupin

Professeur des Universités

à l'Institut Galilée, Paris 13

---

---

mise à jour :

22/03/2012

---

Contact

membre de l'équipe AOC du LIPN UMR CNRS 7030

de l'Université Paris 13

Courriel
Adresse	Laboratoire d'Informatique Paris-Nord
	Institut Galilée
	99, avenue Jean-Baptiste Clément 93430 Villetaneuse, France
Téléphone	+33 1 49 40 35 95

---

Recherche

Ma recherche concerne l'Optimisation Combinatoire et comporte trois thèmes principaux :

- Optimisation dans les graphes

- Programmation mathématique

- Complexité et approximation

Un de mes axes de recherche privilégié est la Programmation semidéfinie appliquée à l'Optimisation Combinatoire



– Ma thèse d'Habilitation à diriger des Recherches est disponible ici



– Co-encadrements de thèses (avec Marie-Christine Costa) :

Lucas Létocart (2002), Cédric Bentz (2006), Nicolas Derhy (2008)

---

Enseignements

L’étudiant doit le savoir, l’assistant sait où c’est écrit, le professeur a quelqu’un qui sait où c’est écrit (proverbe allemand)

Enseignements 2011-2012 :

• Master Parisien de Recherche Opérationnelle MPRO
  Support du cours
  Polycopié
• L3 Algorithmique dans les graphes :
  Support (sans animation)
  Support (avec animation)
• L1 Math-Info :
  Le support du cours ainsi que l'énoncé du devoir à rendre pour le 27 avril sont disponibles sur l'ENT

Enseignements 2010-2011 :

• Optimisation Combinatoire (Sup Galilée MACS3)
• Algorithmique et complexité (Sup Galilée IR)
• Optimisation et Logiciels (Sup Galilee 3)
• Programmation impérative (Licence 1)
• Math-info (Licence 1)
• Conduite et gestion de projet (Master 1 info)
• Programmation Semidéfinie (ENSIIE, 3A)

Enseignements 2009-2010 :

J'ai bénéficié d'une année de CRCT.

Enseignements 2008-2009 :

• Modélisation, Optimisation, Complexité des algorithmes (CNAM)
• Recherche Opérationnelle, Aide à la décision (CNAM)
• Programmation Semidéfinie (ENSIIE, 3A)
• Recherche Opérationnelle (ENSIIE, 2A)
• Assembleur/Projet matériel (ENSIIE, 1A)
• Programmation Quadratique en variables 0-1 (Master M2 Modélisation et Méthodes Mathématiques en Économie et Finance Paris I)

Autres enseignements :

• Complexité des Algorithmes (ENSIIE, 3A)
• Etude de cas en Recherche Opérationnelle (ENSIIE, 3A)
• Algorithmique parallèle (ENSIIE 3A)
• Théorie des Graphes (ENSIIE, NFI)
• Optimisation Mathématique (ENSIIE, 1A)
• Projet Mathématique (ENSIIE, 2A)
• Algorithmique/Programmation/C (ENSIIE, 1A)
• Projet Informatique (ENSIIE, 2A)

---

Responsabilités

• Membre du comité éditorial de la revue International Journal of Mathematics in Operational Research (IJMOR)
• Responsable relations entreprises / CFA (Sup Galilée AIR) (depuis 2010)
• Expert extérieur pour le Fonds "Nature et Technologies", bourses des Fonds de recherche du Québec
• Membre du conseil de laboratoire du laboratoire CEDRIC (2008-2010)
• Responsable du parcours Recherche Opérationnelle et des stages du Master M2 MOCS du CNAM
(2009-2010)
• Responsable des mémoires de fin d’études d’ingénieurs de l'ENSIIE (2003-2007)
• Membre de la commission de spécialistes (section 27) du CNAM (2002-2007)
• Membre extérieur de la commission de spécialistes (sections 26-27) de Paris I (2004-2007)
• Membre élu du conseil d’Ecole de l’IIE (2003-2006)
• Membre de la commission technique de l’IIE au CNAM (2001-2004)

---

Projets et Réalisations

– Projet LMI-SDP2 "Toward new semidefinite optimization tools for control and combinatorial optimization" Site web du projet LMI-SDP2

– Une nouvelle génération de programmes convexes non-linéaires, Semidefinite Least-Squares Problems, a été considérée récemment pour élaborer des relaxations de problèmes combinatoires difficiles. Dans cette approche la modélisation des problèmes est moins directe, mais les solveurs que nous avons développés sont plus robustes et plus rapides que ceux de la programmation semidéfinie standard. Ce projet est mené en collaboration avec Jérôme Malick, CR à l'INRIA Grenoble.

– SDP_S "Un logiciel libre pour élaborer automatiquement et tester numériquement des relaxations semidéfinies" Site web de SDP_S

– SDP_S est un outil pour formuler et tester très facilement des relaxations semidéfinies pour les problèmes quadratiques en variables 0-1. Il intègre le solveur SB de C. Helmberg pour la résolution numérique des programmes semidéfinis obtenus. Aucune programmation additionnelle ni expertise en programmation semidéfinie ne sont nécessaires. Un utilitaire, Res2PLot, permet de visualiser les courbes de convergence obtenues.

---

Publications et Communications

2012

1. Krislock, N.; Malick, J. and Roupin, F. Improved semidefinite bounding procedure for solving Max-Cut problems to optimality. In Math. Prog. Soumis, 2012.
2. Krislock, N.; Malick, J. and Roupin, F. Mixing a Polyhedral Approach and a Nonlinear Optimization Algorithm for Integer Quadratic Programs. In INFORMS'12, Beijing, 2012.
3. Alfandari, L.; Butelle, F.; Coti, C.; Finta, L.; Plateau, G.; Rozenknop, A. and Roupin, F. Combining VNS, Simulated Annealing, and a Greedy Heuristic for the ROADEF/EURO 2012 Challenge. In EURO XXV, Vilnius, 2012.
4. Toulouse, S.; Culus, J-F. and Roupin, F. Differential Approximation Of SNP Optimization Problems. In ISCO'12, International Symposium on Combinatorial Optimization, Athens, 2012.
5. Krislock, N.; Malick, J. and Roupin, F. Nonstandard Semidefinite Bounds For Solving Exactly 0-1 Quadratic Problems. In EURO XXV, Vilnius, 2012.

2011

6. Krislock, N.; Malick, J. and Roupin, F. Efficient new semidefinite bounds for Max-Cut. In Second Alpen-Adria Workshop on Optimization 2011, University of Klagenfurt, Austria, 2011.
7. Malick, J. and Roupin, F. Une famille de bornes semidéfinies ajustables pour la programmation quadratique en variables 0-1. In ROADEF 2011, Saint-Etienne, France, 2011.
8. Malick, J. and Roupin, F. Computing Dense Subgraphs with Semidefinite Programming. In Optimization 2011, Lisbon, Portugal, 2011.
9. Malick, J. and Roupin, F. Solving k-cluster problems to optimality using adjustable semidefinite programming bounds. In Math. Prog. à paraître, 2011.
10. Malick, J. and Roupin, F. On the bridge between combinatorial optimization and nonlinear optimization: new semidefinite bounds for 0-1 quadratic problems leading to quasi-Newton methods. In Math. Prog. à paraître, 2011.

2010

11. Malick, J. and Roupin, F. Computing Dense Subgraphs with Semidefinite Programming. In EWMINLP'10, European Workshop on Mixed Integer Nonlinear Programming, Marseille, France, 2010.
12. Malick, J. and Roupin, F. Numerical Study of Semidefinite Bounds for the k-cluster Problem. In ISCO'10, International Symposium on Combinatorial Optimization, Electronic Notes in Discrete Mathematics, pages 399-406, Elsevier, 2010.
13. Malick, J. and Roupin, F. Résolution exacte du problème k-cluster par optimisation semidéfinie. In ROADEF'10, Toulouse, France, 2010.

2009

14. Bentz, C; Costa, M.-C; Derhy, N and Roupin, F Cardinality constrained and multicriteria (multi)cut problems. In Journal of Discrete Algorithms, 7(1): 102-111, 2009.
15. Bentz, C; Costa, M.-C; Létocart, L and Roupin, F Multicut and integral multiflow in rings. In European Journal on Operations Research, 196(3): 1251-1254, 2009.
16. Malick, J. and Roupin, F. Une approche par moindres carrés semidéfinis pour le problème k-cluster. In ROADEF'09, Nancy, France, 2009.
17. Roupin, F Standard Semidefinite relaxations for the Quadratic Assignment Problem in a Lagrangian Framework. In Int. J. of Mathematics in Operational Research, 1: 144-162, 2009.

2008

18. Billionnet, A and Roupin, F A Deterministic Approximation Algorithm for the Densest k-Subgraph Problem. In International Journal of Operational Research, 3(3): 301-314, 2008.

2007

19. Bentz, C; Costa, M.-C and Roupin, F Maximum integer multiflow and minimum multicut problems in uniform grid graphs. In Journal of Discrete Algorithms, 5(1): 36-54, 2007.
20. Costa, M-C.; Derhy, N. and Roupin, F. Un Branch and Bound utilisant la programmation semidéfinie pour un problème de placement de tâches et un problème de partition des sommets d'un graphe. In ROADEF'07, Grenoble, France, 2007.
21. Faye, A and Roupin, F Partial Lagrangian relaxation for General Quadratic Programming. In 4'OR, A Quarterly Journal of Operations Research, 5(1): 75-88, 2007.
22. Roupin, F Programmation Semidéfinie en Optimisation Combinatoire. In Tutoriel invité. Journées Franciliennes de Recherche Opérationnelle, Université Pierre et Marie Curie, 15 juin, 2007.
23. Roupin, F. Semidefinite Relaxations for the QAP : A Lagrangian Point of View. In ECCO XX, European Chapter on Combinatorial Optimization, Limassol, Chypre, 2007.
24. Roupin, F. Semidefinite Approaches for Quadratic Integer Programming. In EURO XXII, Prague, République Tchèque, 2007.

2006

25. Bentz, C; Costa, M.-C; Derhy, N and Roupin, F Etude du problème de la multicoupe minimale à cardinalité contrainte. In ROADEF'06 , Lille, février, 2006.
26. Faye, A and Roupin, F Partial Lagrangian relaxation for General Quadratic Programming. In JOPT'06, Montréal, Canada, mai, 2006.
27. Roupin, F Algorithmes Combinatoires et Relaxations par Programmation Linéaire et Semidéfinie. Application à la Résolution de Problèmes Quadratiques et d'Optimisation dans les Graphes. Habilitation à Diriger la recherche. Université Paris Nord.

2005

28. Bentz, C; Costa, M.-C and Roupin, F Maximum edge disjoint paths and minimum unweighted multicuts in grid graphs. In CIRO'05, Marrakech, mai, 2005.
29. Bentz, C.; Costa, M-C. and Roupin, F. Résoudre en temps linéaire le problème de la multicoupe minimum dans des grilles rectangulaires. In ROADEF'05, Tours, France, 2005.
30. Costa, M.-C; Letocart, L and Roupin, F Minimal multicut and maximal integer multiflow: a survey. In European Journal on Operations Research, 162(1): 55-69, 2005.
31. Faye, A. and Roupin, F. A cutting planes Algorithm based upon a Semidefinite relaxation for the Quadratic Assignment Problem. In European Symposium on Algorithms, ESA 2005, pages 850-861, Lecture Notes in Computer Science 3669, 2005.
32. Faye, A. and Roupin, F. Relaxations Lagrangienne et Semidéfinie de Programmes Quadratiques. In ROADEF'05, Tours, France, 2005.

2004

33. Bentz, C; Costa, M.-C; Létocart, L and Roupin, F A bibliography on multicut and integer multiflow problems. Technical Report, CNAM-CEDRIC 654, 2004.
34. Bentz, C.; Costa, M-C. and Roupin, F. Maximum edge disjoint paths and minimum unweighted multicut problems in grid graphs. In Graph Theory 2004, a conference in memory of Claude Berge, 2004.
35. Faye, A. and Roupin, F. A lower bound for the Quadratic Assignment Problem based upon a semidefinite relaxation and a cutting planes approach. In ECCO XVII, European Chapter on Combinatorial Optimization, Beyrouth, Liban, 2004.
36. Roupin, F L'approche par Programmation Semidéfinie en Optimisation Combinatoire. In Article invité dans le Bulletin de la Société Française de Recherche Opérationnelle et d'aide à la décision, 13: 7-11, 2004.
37. Roupin, F From Linear to Semidefinite Programming: an Algorithm to obtain Semidefinite Relaxations for Bivalent Quadratic Problems. In Journal of Combinatorial Optimization, 8(4): 469-493, 2004.

2003

38. Costa, M-C.; Létocart, L. and Roupin, F. Minimal multicut and maximal integer multiflow in rings. In ISMP'03, International Symposium on Mathematical Programming, Copenhague, Danemark, 2003.
39. Costa, M.-C; Létocart, L and Roupin, F A greedy algorithm for multicut and integral multiflow in rooted trees. In Operations Research Letters, 31(1): 21-27, 2003.
40. Delaporte, G.; Jouteau, S. and Roupin, F. SDP_S: a Tool to formulate and solve Semidefinite relaxations for Bivalent Quadratic problems. In ROADEF'03, Avignon, France, 2003.
41. Elloumi, S; Roupin, F and Soutif, E Comparison of Different Lower Bounds for the Constrained Module Allocation Problem. Technical Report, CNAM-CEDRIC, 2003.
42. Roupin, F. Une approche semidéfinie pour un problèmede placement de tâches avec contraintes de ressources. In ROADEF'03, Avignon, France, 2003.

2002

43. Costa, M-C.; Létocart, L. and Roupin, F. Multiflots entiers et multicoupes: analyse de leur difficulté. In ROADEF'02, Paris, France, 2002.
44. Létocart, L. and Roupin, F. A semidefinite approach to solve multicut in trees. In JOPT'02, Optimization days, Montréal, Canada, 2002.
45. Roupin, F. Semidefinite relaxations for several quadratic problems. In CIRO'02, Conférence Internationale en Recherche Opérationnelle, Marrakech, Maroc, 2002.

2001

46. Roupin, F. Résolution de MAX 2SAT par programmation semidéfinie. In JOPT'01, Optimization days, Québec, Canada, 2001.

2000

47. Billionnet, A. and Roupin, F. Résolution approchée du problème k-cluster. In ROADEF'00, Nantes, France, 2000.
48. Costa, M-C.; Crémieu, J-L. and Roupin, F. A variable neighborhood search using an interior point descent method for the module allocation problem. In ECCO XIII, European chapter on combinatorial optimization, Capri, Italie, 2000.
49. Cung, V-D.; Roupin, F. and Hoeve, W-J. va A parallel Branch-and-Bound algorithm using a semidefinite programming relaxation for the maximum independent set problem. In ROADEF'00, Nantes, France, 2000.

1999

50. Cung, V.-D and Roupin, F. A Parallel Branch-and-Bound Algorithm using a Semidefinite Programming Relaxation for the Vertex-Cover Problem. In ECCO XII, European chapter on combinatorial optimization, Bandol, France, 1999.

1997

51. Billionnet, A. and Roupin, F. Linear Programming to pproximate quadratic 0-1 maximization problems. In 35th Southeast ACM conference, pages 171-173, Murfreesboro, USA, Proceedings , 1997.
52. Roupin, F. A fast heuristic for continuous quadratic programs subject to linear constraints. In MIC'97, 2nd International Conference on Metaheuristics, pages 195-198, Sophia-Antipolis, France, 1997.
53. Roupin, F. A fast heuristic for the module allocation problem. In 15th IMACS World Congress, pages 405-410, Proceedings 1, 1997.
54. Roupin, F On approximating the memory-constrained module allocation problem. In Information Processing Letters, 61(4): 205-208, 1997.

---

Liens

• ENSIIE je suis ingénieur IIE 1993 (devenue ENSIIE en 2006)
• ROADEF Société Française de Recherche Opérationnelle et d'Aide à la Décision
• Portail sur la RO Un ensemble très fourni d’informations et de liens sur la Recherche Opérationnelle par Maurice Diamantini de l'ENSTA
• NFORMS The Institute for Operations Research and the Management Sciences
• Christoph Helmberg's Semidefinite Programming Page Une mine d'articles et de liens concernant la programmation semidéfinie
• Michael Trick's Operations Research Page

---

© 2010 F. Roupin