Skip to Main content Skip to Navigation
Conference papers

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].
Document type :
Conference papers
Complete list of metadatas

Cited literature [2 references]  Display  Hide  Download

https://hal-enac.archives-ouvertes.fr/hal-02073393
Contributor : Laurence Porte <>
Submitted on : Tuesday, March 19, 2019 - 8:09:08 PM
Last modification on : Tuesday, October 20, 2020 - 10:32:07 AM
Long-term archiving on: : Thursday, June 20, 2019 - 4:35:02 PM

File

ROADEF2019_paper_186.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

71

Files downloads

60