Sites Inria

Version française

FHCP Challenge

Anne Schneider - 29/11/2016

When researchers play to solve 1001 instances of the Hamiltonian Cycle Problem

The challenge proposed by the University Flinders in Adelaïde ( Australia ) to the researchers of the whole world consisted in solving 1001 instances of the Hamiltonian Cycle Problem.

Two researchers, Nathann Cohen, a CNRS researcherat LRI (Paris XI) and David Coudert, Inria research director in charge of the project-team COATI , a joint-team between Inria Sophia Antipolis - Mediterranée research centre and I3S laboratory made the best score and won the challenge.

They managed to solve 985 cycles and won the Prize on December 1st, 2016 using an original method.

Hamiltonian Cycle

Le problème du cycle hamiltonien est un problème classique en théorie des graphes, réputé très difficile à résoudre. Il est également connu sous le nom de problème du “voyageur de commerce », qui doit honorer de nombreux rendez-vous dans des villes éloignées sans jamais retourner sur ses pas. L’équipe du Flinders Hamiltonian Cycle Project (FHCP) a donc lancé un défi à tous les chercheurs du domaine en leur proposant de résoudre 1001 instances et récompensant le chercheur ou l’équipe de chercheurs qui parviendrait à trouver une solution pour tous les graphes proposés dans le délai du concours (un an). Douze équipes ont finalement envoyé des résultats complets mais chaque équipe n'est parvenue à résoudre en moyenne que 338 instances. L'équipe arrivée en deuxième position a trouvé 614 cycles. Aucune équipe n'a trouvé à ce jour de solution pour les seize graphes non élucidés par les lauréats.

Operational research and progressive decomposition

Nathann Cohen et David Coudert se sont attaqués à ce challenge comme à un jeu. Plutôt que d’utiliser des logiciels dédiés ou développer et tester de longs algorithmes, ils ont préféré le résoudre comme un casse-tête : après une première classification par caractéristiques principales (nombre de sommets, diamètre, degrés minimum et maximum),  ils ont analysé les différents graphes un par un pour en identifier visuellement le type, les classer par « famille » et imaginer la bonne approche de résolution. Certains graphes ayant jusqu’à 10 000 sommets, ils ont cherché à réduire la taille des instances en combinant des méthodes de séparation, substitution, élimination, réduction, etc. et ont ensuite traité les graphes d’une même famille de façon identique, à l’aide de logiciels différents de ceux utilisés habituellement pour ce type de problème, donc non spécifiques à cette problématique.

La résolution s’est ensuite poursuivie famille par famille jusqu’à permettre la résolution de 985 graphes sur les 1001 proposés par l’université Flinders ! D’une certaine façon ce prix récompense un savoir-faire très opérationnel plutôt qu’un nouveau logiciel.

Keywords: Flinders university Hamiltonian cycles Research centre Sophia Antipolis - Mediterranee COATI

Top