Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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

Résumé : 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].
Type de document :
Communication dans un congrès
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

https://hal-enac.archives-ouvertes.fr/hal-02073393
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : mardi 19 mars 2019 - 20:09:08
Dernière modification le : mercredi 3 novembre 2021 - 06:41:12
Archivage à long terme le : : jeudi 20 juin 2019 - 16:35:02

Fichier

ROADEF2019_paper_186.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-02073393, version 1

Collections

Citation

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⟩

Partager

Métriques

Consultations de la notice

67

Téléchargements de fichiers

86