Etude d'instances pour les problèmes NP-difficiles

National audienceD évelopper des algorithmes demande d'être capable de les tester afi n de les comparer aux autres m éthodes existantes. L' évaluation des performances pratiques d'un algorithme, appel ée benchmarking, s'appuie sur des jeux d'instances. Ces compilations d'instances sont des bases d'exp érimentation sur lesquelles sont test ées le comportement des m éthodes de r ésolution. L'effi cacit é de l' évaluation d épend donc directement de la qualit é du jeu d'instances. Actuellement ces instances sont généralement issues d'applications industrielles ou de cas pathologiques rencontr és dans la recherche. Or peu de travaux portent un regard critique sur le choix de ces jeux d'instances [1] [2]. Notre étude a pour objectif d'évaluer la pertinence des instances pour le bench- marking. Ceci s'appuie sur la notion de diffi cult é d'instance, utilis ée comme outil de mesure. Dans notre cas, elle repose sur les performances d'algorithmes, formant une base d'exp érimentation, pour tester la pertinence des instances. A l'inverse du benchmarking classique, nous utilisons les m éthodes de r ésolution pour faire du benchmarking d'instances. Cette méthodologie off re un moyen de quali fier les instances. De plus, cela ouvre la voie pour la conception de nouvelles instances pour le benchmarking. Nous illustrerons notre approche à travers une application au Probl eme du Voyageur de Commerce