An Overview of What We Can and Cannot Do with Local Search

Etant donné qu’on ne connaît pas un algorithme efficace pour résoudre les pro-blèmes d’optimisation NP-difficiles, on développe plusieurs algorithmes approchés. Parmi ces algorithmes est la Recherche Locale qui est une méthode générale. On considère une structure de voisinage de solutions d’un problème d’optimisation et au lieu de trouver la meilleure solution dans le domaine, nous trouvons une solution, appelée optimum local, qui est la meilleure dans ce voisinage. Ainsi, l’heuristique standard de la recherche locale commence par une solution initiale et se déplace à une meilleure solution voisine pour aboutir à un optimum local. Cette simple mé-thode se démontre en pratique très performante produisant des solutions de bonne qualité dans de temps d’exécution raisonnable. Le but principal de ce travail est de faire une synthèse du travail théorique qui est réalisé sur les limites de la recherche locale en général et son efficacité d’approxi-mation pour de problèmes spécifiques. Ainsi, d’un côté nous présentons la théorie de PLS-complétude et nous montrons que pour un problème PLS-complet l’heuristique de la recherche locale standard nécessite dans le pire de cas de temps exponentiel. Nous montrons aussi que s’il est NP-difficile d’obtenir une ε−approximation d’un problème d’optimisation alors il n’existe pas de voisinage qui conduit à un opti-mum local ε−proche d’un optimum global, sauf si NP=co-NP. De l’autre côté, nous présentons plusieurs exemples de problèmes NP-difficiles pour lesquels certains voi-sinages peuvent garantir des optima locaux ε−proche d’un optimum global. Cette garantie est souvent, la meilleure qu’on puisse obtenir pour certains problèmes par n’importe quel algorithme. L’algorithme de la recherche locale est pseudopolyno-mial. Par conséquent, lorsque les problèmes sont sans poids ou avec des poids poly-nomialement bornés l’algorithme atteint un optimum local en temps polynomial. Mots-clefs: recherche locale, PLS-complétude, approximatio