Contact

roupin Equipe Algorithmes et Optimisation Combinatoire du LIPN UMR CNRS 7030 de l'Université Paris 13

Courriel mel
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

combinatoire

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

- Programmation mathématique

- Optimisation dans les graphes

- Complexité et approximation

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

Responsabilités

ijmor

Projets et Réalisations

BiqCrunch – BiqCrunch, a semidefinite branch-and-bound method for solving binary quadratic problems" Site web du solveur BiqCrunch

– Version multithread de Biqcrunch (avec C. Coti, F. Butelle, et E. Leclercq)

– BiqCrunch permet de résoudre tout problème quadratique en variables 0-1. Ce solveur utilise les nouvelles bornes semidéfinies présentées dans [11]. Le site web propose un solveur online avec des versions spécifiques pour plusieurs problèmes combinatoires : max-cut, k-cluster, programme quadratique quelconque en 0-1.





SDLS – Projet LMI-SDP2 "Toward new semidefinite optimization tools for control and combinatorial optimization". – 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.





SDPS – SDP_S "Un logiciel libre pour élaborer automatiquement et tester numériquement des relaxations semidéfinies" SDP_S.1.1.tar.gz

– 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

2018

  1. Leclercq, E and Roupin, F A dedicated version of BiqCrunch for solving the Max-Stable Set problem exactly. In ISMP'18, International Symposium on Mathematical Programming, Bordeaux, France, 2018.
  2. Létocart, L; Roupin, F and Wiegele, A Exact methods based on SDP for the k-item quadratic knapsack problem. In ISMP'18, International Symposium on Mathematical Programming, Bordeaux, France, 2018.
  3. Gandouin, Y; Leclercq, E and Roupin, F Résolution exacte du problème du stable par une approche mixte semidéfinie et polyédrale. In ROADEF'18, Lorient, France, 2018.

2017

  1. Krislock, N; Malick, J and Roupin, F BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems. In ACM Transactions on Mathematical Software. 43(4), 2017.
  2. Coti, C; Lelercq, E; Roupin, F and Butelle, F Une version Multithread du solveur BiqCrunch. In ROADEF'17, Metz, 2017.
  3. Coti, C; Lelercq, E; Roupin, F and Butelle, F Solving 0-1 Quadratic Problems with Two-Level Parallelization of the BiqCrunch Solver. In FProceedings of the 2017 Federated Conference on Computer Science and Information Systems, pages 445-452, Prague, Czech Republic, 2017.

2016

  1. Roupin, F Semidefinite Optimization for MINLP. In MINO/COST Spring School on MINLP, Paris, 2016.
  2. Krislock, N; Malick, J and Roupin, F Computational results of a semidefinite branch-and-bound algorithm for k-cluster. In Computers and Operations Research, 66: 153-159, 2016.

2015

  1. Butelle, et al., Fast machine reassignment. In Annals of Operations Research: 1-28, 2015.

2014

  1. Culus, J.-F; Roupin, F and Toulouse, S Satisfaction guaranteed. In IFORS 2014, 20th Conference of the International Federation of Operational Research Societies, Barcelona, 2014.
  2. Krislock, N; Malick, J and Roupin, F BiqCrunch in Action: Solving Difficult Combinatorial Optimization Problems Exactly. In SIAM Conference on Optimization, San diego, 2014.
  3. Létocart, L; Guignard-Spielberg, M; Plateau, G; Roupin, F and Wiegele, A Approches exactes pour le problème du sac à dos quadratique avec contrainte de cardinalité. In ROADEF'14, Bordeaux, 2014.
  4. Krislock, N.; Malick, J. and Roupin, F. Improved semidefinite bounding procedure for solving Max-Cut problems to optimality. ISMP 2012, 21st International Symposium on Mathematical Programming, 19-24 August, Berlin. In Math. Prog. A., 143(1/2): 61-86, 2014.

2013

  1. 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. B, 140(1): 99-124, 2013.

2012

  1. 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.
  2. 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.
  3. Toulouse, S.; Culus, J-F. and Roupin, F. Differential Approximation Of SNP Optimization Problems. In ISCO'12, International Symposium on Combinatorial Optimization, Athens, 2012.
  4. Krislock, N.; Malick, J. and Roupin, F. Nonstandard Semidefinite Bounds For Solving Exactly 0-1 Quadratic Problems. In EURO XXV, Vilnius, 2012.
  5. Malick, J. and Roupin, F. Solving k-cluster problems to optimality using semidefinite programming. In Math. Prog. B pp 279-300, 136, 2012.

2011

  1. 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.
  2. 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.
  3. Malick, J. and Roupin, F. Computing Dense Subgraphs with Semidefinite Programming. In Optimization 2011, Lisbon, Portugal, 2011.

2010

  1. Malick, J. and Roupin, F. Computing Dense Subgraphs with Semidefinite Programming. In EWMINLP'10, European Workshop on Mixed Integer Nonlinear Programming, Marseille, France, 2010.
  2. 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.
  3. Malick, J. and Roupin, F. Résolution exacte du problème k-cluster par optimisation semidéfinie. In ROADEF'10, Toulouse, France, 2010.

2009

  1. 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.
  2. 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.
  3. 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.
  4. 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

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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. Roupin, F. Semidefinite Relaxations for the QAP : A Lagrangian Point of View. In ECCO XX, European Chapter on Combinatorial Optimization, Limassol, Chypre, 2007.
  6. Roupin, F. Semidefinite Approaches for Quadratic Integer Programming. In EURO XXII, Prague, République Tchèque, 2007.

2006

  1. 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.
  2. Faye, A and Roupin, F Partial Lagrangian relaxation for General Quadratic Programming. In JOPT'06, Montréal, Canada, mai, 2006.
  3. 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. more.. 

2005

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. Faye, A. and Roupin, F. Relaxations Lagrangienne et Semidéfinie de Programmes Quadratiques. In ROADEF'05, Tours, France, 2005.

2004

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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

  1. 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.
  2. 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.
  3. 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.
  4. Elloumi, S; Roupin, F and Soutif, E Comparison of Different Lower Bounds for the Constrained Module Allocation Problem. Technical Report, CNAM-CEDRIC, 2003.
  5. 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

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

2001

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

2000

  1. Billionnet, A. and Roupin, F. Résolution approchée du problème k-cluster. In ROADEF'00, Nantes, France, 2000.
  2. 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.
  3. 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

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

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

Enseignements

GalileeL'é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 de 2010 à 2022 :

Autres enseignements :

Liens



© F. Roupin