CHallenge en Optimisation Combinatoire
Présentation
Le projet CHOC se place dans le domaine des Grands défis applicatifs proposé par l'ANR-CICG. Choc a été labellisé en réponse à l'appel d'offre de 2005 (code ANR-05-CICG-06).Résumé du projet
Le challenge est la résolution de deux problèmes célèbres et très difficiles de l'Optimisation Combinatoire : l'Affectation Quadratique (QAP) et l'une de ses extensions le Q3AP (3 dimensions). Notre objectif est de pousser le plus loin possible la résolution exacte de ces problèmes et d'améliorer la valeur de la meilleure solution connue pour les instances non résolues grâce au parallélisme. Nous souhaitons étudier le couplage d'une part de la librairie de développement de Branch-and-Bound (B&B), Bob++ (Versailles) avec Kaapi (Grenoble), qui gère automatiquement l'ordonnancement à grain fin et l'ajout/retrait dynamique de ressources, et la plate-forme de résolution approchée ParadisEO (Lille) pour améliorer la solution donnée pour les exemples de grande taille. Nous effectuerons nos tests sur les systèmes parallèles les plus performants actuellement.Adresse
Coordonateur : Bertrand Le Cun
Laboratoire PRISM (Computer Science Department)
Université de Versailles-Saint Quentin
45, avenue des Etats-Unis,
78035 Versailles Cedex, France
Tel : 33 (0)1 39 25 40 50
Fax : 33 (0)1 39 25 40 57
E-mail: Bertrand.Lecun AT prism.uvsq.fr
Motivations
Le problème d'Affectation Quadratique, fait partie des problèmes académiques les plus marquants du domaine. Plusieurs équipes internationales ont défrayé la chronique en résolvant exactement des grandes instances de ce problème à l'aide du parallélisme massif. L'équipe Opale du laboratoire PRiSM en collaboration avec Van-Dat Cung du laboratoire GILCO, travaille depuis des années sur la résolution exacte du problème d'Affectation Quadratique, par méthode Branch and Bound. En s'alliant avec le LIFL qui amènerait leur savoir faire en metaheuristiques et avec l'équipe MOAIS, pour améliorer encore les performances parallèles, nous pouvons repousser encore les limites actuelles en utilisant des machines performantes du territoire français : Grid5000, Teranova,... Nous voulons aussi réutiliser notre expérience sur le QAP, pour résoudre des instances de problème de Q3AP de taille supérieure à 13.Retombées scientifiques
Le fait de repousser la limite de résolution d'un problème comme le QAP, est déjà une retombée significative, mais notre but est aussi de populariser les bibliothèques Bob++, ParadisEO, et Kaapi, en proposant une véritable plate-forme parallèle de résolution de problèmes d'Optimisation Combinatoire (exactes et/ou heuristiques). Une autre retombée est de proposer la parallélisation d'un Branch and Bound portant en même temps sur l'arbre de recherche et sur le calcul de la borne inférieure. Même si beaucoup s'accordent à dire que c'est une perspective très intéressante, très peu de travaux ont été proposé dans ce sens.Délivrables
- La bibliothèque Kaapi : Ordonnancement de tâches parallèles indépendantes, sur machines hétérogènes, et tolérance aux fautes.
- La bibliothèque Bob++ : suite logicielle facilitant l'écriture de programme résolvant des problèmes par Branch-and-Bound parallèle.
- La bibliothèque ParadisEO : suite logicielle facilitant l'écriture de programme résolvant des problèmes par metaheuristiques parallèles hybrides.
- Codes applicatifs Bob++ et ParadisEO pour les problèmes QAP et Q3AP.
Cloture
Le projet est maintenant officiellement cloturé.- Le compte rendu final
- Les slides de la revue lors du colloque ANR « modélisation, calcul intensif et simulation »
