Indice d'Optimalité pour la Coloration de Graphe et Comptage de Solutions

Alexandre Gondran (1) , Laurent Moalic (2)

1 ENAC - Ecole Nationale de l'Aviation Civile
2 Université de Haute-Alsace (UHA) - Université de Haute-Alsace (UHA) Mulhouse - Colmar

1 Problématique Sur les instances de grande taille d'un problème NP-difficile, les méthodes exactes ne per-mettent pas de trouver une solution optimale. Elles permettent au mieux de trouver une borne inférieure et/ou une borne supérieure à la valeur optimale. Les métaheuristiques quant à elles, ne permettent de trouver que des solutions admissibles de "bonne qualité", c'est-à-dire, dans le cas d'un problème de minimisation, une borne supérieure à la valeur optimale. Le gap d'op-timalité est l'écart entre ces deux bornes. L'optimalité n'est prouvée que lorsque ce gap est nul. Malheureusement pour les instances de grande taille d'un problème NP-difficile, ce gap est souvent important. Que faire dans cette situation ? On peut évidemment améliorer les méthodes exactes et heuristiques utilisées, mais si P = N P on trouvera toujours des instances où le gap est important. Que peut-on faire de mieux uniquement avec des heuristiques ? On montre qu'une heuristique ne fournit pas seulement une borne supérieure au problème mais peut apporter des informations supplémentaires comme le nombre de solutions admissibles différentes ayant le plus faible coût trouvé (nombre de meilleures bornes supérieures trouvées différentes). Notre approche est alors fondée sur l'observation suivante : pour un problème de minimisation, le nombre de solutions admissibles diminue avec la valeur de la fonction objectif. En d'autres termes, plus le nombre de solutions admissibles ayant le même coût diminue, plus on se rapproche de l'optimalité. D'abord, on démontre dans cette présentation l'exactitude de cette observation pour les problèmes de coloration de graphe et de recherche de clique maximum. Nous présentons ensuite une nouvelle approche qui permet de qualifier ou non une solution (trouvée par une heuristique) comme étant une potentielle solution optimale. Notre approche est appliquée au problème de coloration de graphe [1].

Domaines: Optimisation et contrôle [math.OC]

Alexandre Gondran, Laurent Moalic. Indice d'Optimalité pour la Coloration de Graphe et Comptage de Solutions. ROADEF 2019, congrès annuel de la société Française de Recherche Opérationnelle et d’Aide à la Décision, Feb 2019, Le Havre, France. ⟨hal-02073393⟩