Approximation polynomiale des problèmes NP-difficiles - Optima locaux et rapport différentiel Sophie Toulouse, Jérôme Monnot, Vangelis Paschos To cite this version: Sophie Toulouse, Jérôme Monnot, Vangelis Paschos. Approximation polynomiale des problèmes NP- difficiles - Optima locaux et rapport différentiel. 2002. ￿hal-00003255￿ HAL Id: hal-00003255 https://hal.archives-ouvertes.fr/hal-00003255 Preprint submitted on 10 Nov 2004 HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire HAL, est archive for the deposit and dissemination of sci- destinée au dépôt et à la diffusion de documents entific research documents, whether they are pub- scientifiques de niveau recherche, publiés ou non, lished or not. The documents may come from émanant des établissements d’enseignement et de teaching and research institutions in France or recherche français ou étrangers, des laboratoires abroad, or from public or private research centers. publics ou privés. Approximation polynomiale des problèmes NP-difficiles : optima locaux et rapport différentiel Jérôme MONNOT etVangelisTh. PASCHOS et Sophie TOULOUSE 17décembre2002 Remerciements Unlivre,avantd’êtreédité,adéjàvécuunelonguehistoire.L’histoiredecelui-ci, cesontdestravauxderecherchequiontinspiréletravaildethèsedeSophieToulouse; c’estl’encouragementàfairedecetravailunouvrageàpartentière,lafinalisationd’un manuscritenvuedesonédition.Pourtoutescesétapes,noustenonsàremerciercelles etceuxquinousontpermisd’avancer. Nous pensons tout d’abord à Lalo Fernandez de la Vega qui est à l’initiative de cet ouvrage : il nous a donné l’envie, le souffle et l’enthousiasme de le faire. Nous pensons aussià Giorgio Ausiellodont les rechercheset les réflexionsontnourri nos propresrecherches.NouspensonségalementàlaparticipationdeCristinaBazgan,à celle de Jean-Xavier Rampon et, bien évidemment, à l’accompagnementde tous les joursdeDominiqueChamp-Brunetpourladocumentation,maisaussilesourireetla décontraction.Enfin,merciauxmaîtresduLATEXStratosPaschosetDenisBouyssou pourleurdisponibilitéetleprécieuxsecoursqu’ilsnousontporté.Enfinl’essentiel:la disciplineettousceuxquiontconcouruetencourentencoreàlaprésenteretl’enrichir. Unlivre, aprèssonédition, commencesa véritablevie;nousremercions leslec- teurs,qui,nousl’espérons,trouverontintérêtàsalecture:c’estàeuxqu’ilrevientde donneruneâmeàcetouvrage. 5 Table des matières Avant-propos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Chapitre1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Chapitre2.L’approximationpolynomiale . . . . . . . . . . . . . . . . . . . . 23 2.1. Lesproblèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1.1. Qu’est-cequ’unproblèmedeNPO?. . . . . . . . . . . . . . . . . 23 2.1.2. Définitionsindispensables . . . . . . . . . . . . . . . . . . . . . . 25 2.2. Leurrésolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2.1. Lamissiondel’approximationpolynomiale . . . . . . . . . . . . 28 2.2.2. Sonarme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3. L’évaluationdeleursalgorithmes . . . . . . . . . . . . . . . . . . . . . 29 2.3.1. Ferdelancedel’approximationpolynomiale:lerapportclassique 29 2.3.2. Unealternative:lerapportdifférentiel . . . . . . . . . . . . . . . 30 2.3.3. L’erreur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.4. Degrésd’approximation. . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.4.1. Approximationàrapportconstantr0 . . . . . . . . . . . . . . . . 32 2.4.2. Approximationàr,raussiprochede1quel’onveut . . . . . . . 34 2.5. Définitionlogique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.5.1. LesclassesMaxNPetMaxSNP . . . . . . . . . . . . . . . . . . . 38 2.5.2. Logiqueetapproximation. . . . . . . . . . . . . . . . . . . . . . . 40 2.6. Effetsdeclasse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.6.1. Leprincipederéduction . . . . . . . . . . . . . . . . . . . . . . . 43 2.6.1.1. Réductionpolynomiale . . . . . . . . . . . . . . . . . . . . . 43 2.6.1.2. Réductionpréservantl’optimalité . . . . . . . . . . . . . . . 44 2.6.1.3. Réductionpréservantl’approximation. . . . . . . . . . . . . 45 2.6.2. Lanotiondecomplétude . . . . . . . . . . . . . . . . . . . . . . . 48 2.6.3. Lafermeture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7 8 Optimalocauxetrapportdifférentiel 2.7. Affinitéentreproblèmes. . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.7.1. Réductionscontinues . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.7.2. Réductionsaffines . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.8. Voyageurdecommerceetaffinité . . . . . . . . . . . . . . . . . . . . . 56 2.8.1. Lecasmétrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.8.2. Sescousins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.8.3. Lecasbivalué . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.8.4. Lecasgénéral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.9. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Chapitre3.Optimumlocalgaranti . . . . . . . . . . . . . . . . . . . . . . . . 63 3.1. Quelquesconcepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.1.1. Qu’est-cequ’unalgorithmederecherchelocale? . . . . . . . . . 63 3.1.1.1. LSA–algorithmederecherchelocale. . . . . . . . . . . . . 64 3.1.1.2. Complexitéd’unLSA . . . . . . . . . . . . . . . . . . . . . . 65 3.1.1.3. Conditionsnécessairesetconditionssuffisantesdepolyno- mialité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.1.2. Voisinagesh-bornés . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.2. LesclassesGLO[R] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.3. Exemplessimplespourvoisinages1-bornés . . . . . . . . . . . . . . . 71 3.4. Limitedesvoisinagesh-bornés. . . . . . . . . . . . . . . . . . . . . . . 74 3.5. Réductionspréservantl’approximationlocale . . . . . . . . . . . . . . 75 3.5.1. Préserverlevoisinage . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.5.1.1. LaLOC-réduction . . . . . . . . . . . . . . . . . . . . . . . . 76 3.5.1.2. LaLOC0-réduction . . . . . . . . . . . . . . . . . . . . . . . 79 3.5.2. LaréductiondansGLO[R] . . . . . . . . . . . . . . . . . . . . . . 81 3.5.3. Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3.6. GLOetassociéspremièrepartie . . . . . . . . . . . . . . . . . . . . . . 84 3.6.1. VoisinagesmiroirsetclasseCGLO[R] . . . . . . . . . . . . . . . 84 3.6.2. OptimaaltérésetGGLO[R] . . . . . . . . . . . . . . . . . . . . . 86 3.6.3. MixageouGCGLO[R] . . . . . . . . . . . . . . . . . . . . . . . . 86 Chapitre4.ProblèmesdansGLOetGLO[(cid:14)] . . . . . . . . . . . . . . . . . . 87 4.1. Desvoisinages1-et2-bornés . . . . . . . . . . . . . . . . . . . . . . . . 87 4.1.1. Couvertured’ensembles. . . . . . . . . . . . . . . . . . . . . . . . 90 4.1.2. Ensembleminimumd’arêtesretour . . . . . . . . . . . . . . . . . 94 4.1.3. Couplagemaximumdansunhypergraphe. . . . . . . . . . . . . . 95 4.1.4. Lesproblèmesd’ordonnancement . . . . . . . . . . . . . . . . . . 96 4.1.5. Leproblèmedesous-graphepartielmaximumlibredeH . . . . 97 0 4.1.6. Ensembleminimumdesommetsretour . . . . . . . . . . . . . . . 100 4.2. Exemplespourlesvoisinages3-bornésetplus . . . . . . . . . . . . . . 101 4.2.1. Retour sur le problème de sous-graphe partiel maximum libre deH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 0 Tabledesmatières 9 4.2.2. Levoyageurdecommerceetlevoisinage2-opt . . . . . . . . . . 106 4.3. Résultatsnégatifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 4.3.1. Satisfaisabilitémaximum . . . . . . . . . . . . . . . . . . . . . . . 109 4.3.2. Lesac-à-dos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 4.4. OùlesclassesGLO[R]sesituent-elles?. . . . . . . . . . . . . . . . . . 112 4.4.1. GLO[R]etlesclassesd’approximation . . . . . . . . . . . . . . . 112 4.4.2. GLO[R]etlesclasseslogiques . . . . . . . . . . . . . . . . . . . . 117 4.4.3. Quelleunitédanstoutça? . . . . . . . . . . . . . . . . . . . . . . 119 4.5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Chapitre5.Lesproblèmesdesatisfaisabilité . . . . . . . . . . . . . . . . . . 123 5.1. Lesproblèmesdesatisfaisabilitéentreeux . . . . . . . . . . . . . . . . 123 5.1.1. Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.1.2. Touspourun . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 5.2. GLOetassociésdeuxièmepartie. . . . . . . . . . . . . . . . . . . . . . 128 5.3. DéclinaisondesproblèmesdesatisfaisabilitémaximumenGLO. . . . 130 5.3.1. Uneoppositiondeplusentrerapportsclassiqueetdifférentiel . . 130 5.3.2. MaxSatetCGLO . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 5.3.3. Maxk-SatetGLO . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 5.3.4. Maxk-SatetCGLO . . . . . . . . . . . . . . . . . . . . . . . . . . 133 5.3.5. MaxNAEk-SatetGLO . . . . . . . . . . . . . . . . . . . . . . . . 134 5.3.6. Maxk-SatetGCGLO . . . . . . . . . . . . . . . . . . . . . . . . . 135 5.4. Lesproblèmesdesatisfactiondecontraintesconjonctives. . . . . . . . 136 5.4.1. Unproblèmedifficile . . . . . . . . . . . . . . . . . . . . . . . . . 136 5.4.2. Versle1/4différentiel . . . . . . . . . . . . . . . . . . . . . . . . . 140 5.4.3. Approximationà1/3. . . . . . . . . . . . . . . . . . . . . . . . . . 143 5.5. Limitesdel’approcheGLO . . . . . . . . . . . . . . . . . . . . . . . . . 144 5.5.1. 1/3,lemeilleurdeCGLOpourMax2-CCSP . . . . . . . . . . . . 144 5.5.2. 1/5,lemeilleurespoirdeCGLO[(cid:14)]pourMax2-CCSP . . . . . . . 147 5.5.3. 1/2,lemeilleurdeGLOpourMaxNAE2-Sat . . . . . . . . . . . . 148 5.5.4. 1/3,lemeilleurespoirdeGLO[(cid:14)]pourMaxNAE2-Sat . . . . . . 149 5.6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 Chapitre6.Réductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 6.1. Danslesgraphesetleshypergraphes(systèmesd’ensembles) . . . . . 151 6.1.1. Régularisationpourlacouvertured’ensembles . . . . . . . . . . . 152 6.1.2. Dépondérationpourlacouvertured’ensembles. . . . . . . . . . . 153 6.1.3. Dépondérationpourlacouverturedesommets . . . . . . . . . . . 156 6.1.4. Autresproblèmessimplesdanslesgraphes . . . . . . . . . . . . . 158 6.2. Lesproblèmesdelogique . . . . . . . . . . . . . . . . . . . . . . . . . . 159 6.2.1. AutourdeMinEQ . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 6.2.2. AutourdeMaxNAESat . . . . . . . . . . . . . . . . . . . . . . . . 163 6.2.3. Denseoupasdense? . . . . . . . . . . . . . . . . . . . . . . . . . 166 10 Optimalocauxetrapportdifférentiel 6.3. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 6.3.1. Uncertaingoûtd’inachevé . . . . . . . . . . . . . . . . . . . . . . 172 6.3.2. Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 Chapitre7.En-deçàdeGLO . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 7.1. LaclassePLSdesproblèmesderecherchelocale . . . . . . . . . . . . 175 7.1.1. Deladifficultédedéterminationdesoptimalocaux . . . . . . . . 176 7.1.1.1. Quelquesnotionsindispensables . . . . . . . . . . . . . . . . 176 7.1.1.2. Legraphedetransition . . . . . . . . . . . . . . . . . . . . . 177 7.1.2. Approximationdesoptimalocaux . . . . . . . . . . . . . . . . . . 179 7.2. Lesproblèmesradiaux. . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 7.2.1. Qu’est-cequeradial? . . . . . . . . . . . . . . . . . . . . . . . . . 181 7.2.2. Lesproblèmes(cid:28)-radiaux . . . . . . . . . . . . . . . . . . . . . . . 184 7.2.2.1. Définitionetexemples . . . . . . . . . . . . . . . . . . . . . 185 7.2.2.2. Problèmes(cid:28)-radiauxetoptimalocaux . . . . . . . . . . . . 187 7.2.3. Unesous-familleremarquable . . . . . . . . . . . . . . . . . . . . 188 7.2.3.1. Lesproblèmesréguliers . . . . . . . . . . . . . . . . . . . . . 188 7.2.3.2. Lesproblèmeshéréditairesetanti-héréditaires . . . . . . . . 190 7.2.3.3. Lesproblèmesdepartitionnementhéréditaire . . . . . . . . 192 7.3. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 Annexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 A. Problèmesrencontrés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 A.1. Problèmesdanslesgraphes . . . . . . . . . . . . . . . . . . . . . . 194 A.2. Problèmesdeprogrammationlinéaire . . . . . . . . . . . . . . . . 199 A.3. Problèmesdelogique . . . . . . . . . . . . . . . . . . . . . . . . . . 200 A.4. Autresproblèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 B. Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 B.1. Lesfondements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 B.2. Lesclasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 B.2.1. Classesd’approximation . . . . . . . . . . . . . . . . . . . . . 207 B.2.2. Classesdéfiniesparlalogique . . . . . . . . . . . . . . . . . . 207 B.2.3. Classesd’approximationlocale . . . . . . . . . . . . . . . . . 208 B.3. Réductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 B.3.1. Propriétésremarquables . . . . . . . . . . . . . . . . . . . . . 209 B.3.2. Réductionsremarquables. . . . . . . . . . . . . . . . . . . . . 210 B.4. Localité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 B.5. Problèmesparticuliers . . . . . . . . . . . . . . . . . . . . . . . . . 212 Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 Avant-propos Larésolutiondesproblèmesdifficilesd’optimisationcombinatoirereposetrèssou- vent sur des méthodesdites « approchées». Elles visent non pas à résoudre un pro- blèmedefaçonoptimale,unetelletentativesurunproblèmedetaillemêmemodeste pouvantmettredesheures,desmois,desannéesvoiredessiècles1,maisdetellefaçon qu’unesolutionréalisableduproblèmeenquestionsoitcalculéeentempspolynomial, c’est-à-direenuntempsmajoréparunpolynômeenlatailledel’instancequel’onaà résoudre.Laplupartdesproblèmesréelssonttels:leursmeilleurs(plusrapides)algo- rithmesconnussontdecomplexitéexponentielle.Dansleurgrandemajoritécespro- blèmes sont formellement classés comme « intrinsèquement difficiles » (problèmes NP-difficiles — NP-hard). C’est notamment le cas de la plupart des problèmes non triviauxd’ordonnancement,desproblèmesderoutage(exemplenotoireetparadigma- tique pour la recherche opérationnelle et l’informatique fondamentale : le voyageur de commerce) ou encore des problèmes de couverture et de partitionnement. La re- cherche d’algorithmes approchés est une démarche principalement adressée à cette classe de problèmes. Pour les problèmes NP-difficiles, même si un tel fait n’est pas formellement démontré (et peut ne jamais l’être), il y a de très fortes présomptions depenserqu’ilsneserontjamaissolublespardesalgorithmespolynomiaux:ceciest la fameuse, et fondamentale pour l’informatique, conjecture P 6= NP). Les algo- rithmes approchés pour la résolution de problèmes d’optimisation combinatoire ont été très souvent utilisés dans l’histoire de l’informatique et surtout dès le début du développementdelarechercheopérationnelle.Danscelivre,nousnoussommesinté- ressésàuneclassebienparticulièredeméthodesapprochées,cellesquigarantissent la qualité de leurs solutions, c’est-à-dire capables de calculer des solutions dont la distance en valeur à la solution optimale est « petite » ou dont le positionnement en 1.Considéronsunalgorithmedecomplexitéexponentielle,parexempled’ordre2n(nétantla tailleduproblème);pourn = 100(unetaillebienmodestepourunproblèmeindustriel),le nombre2100 estplusgrandquelenombredemilliardièmesdesecondesquisesontécoulées depuislebig-bangjusqu’àaujourd’hui[PAP00]. 11 12 Optimalocauxetrapportdifférentiel termesdevaleurobjectivedanslerangdesvaleursobjectivesréalisablespossiblesest « assez proche » de la valeur optimale et « assez loin » de la pire valeur réalisable. Ces deux critères de qualité des solutions approchées désignent deux théories de la mesuredelaqualitéd’unalgorithmeapproché,théoriesquiserontappelées,respecti- vement,approximationstandardouclassiqueetapproximationdifférentielle2.Doré- navant,quandnousparleronsd’algorithmesapprochés,nousentendronsalgorithmes approchésavecgarantiedeperformance. Aussi nous adoptons le cadre d’évaluation appelé « au pire des cas » : quand on mesurelaperformance(soitencomplexité,soitenlaqualitédessolutionsapprochées qu’ilfournit)d’unalgorithme,onl’évalueparrapportàla«pireinstance»,c’est-à- direparrapportàl’instancepourlaquellesesperformancessontlesplusmauvaises, soitoùlecoûtdesonapplicationestleplusélevé(sil’onmesuresacomplexité),oùla mesured’approximationdessolutionsqu’ilcalculeestlaplusmauvaise(sil’onévalue sacapacitéàtrouverdesbonnessolutionsapprochées). Laconceptiond’algorithmesapprochéspeutêtreenvisagéesousdeuxangles: 1)soitl’onconçoitunalgorithmeapprochéparticulierpourunproblèmeparticu- lier, 2)soitl’onessaiedeconcevoirdesalgorithmesoudesclassesd’algorithmesqui s’adressentàuneclasseentièredeproblèmes. Dans le second cas, il faut d’abord comprendre les caractéristiques structurelles desinstancesdesproblèmesdelaclassequinousconcerne,puisessayerdedégager destechniquesetdesmécanismesgénérauxsurlesquelsnotreconceptions’appuiera. Nousnoussommesorientésdanscelivreverscedernierangle(point(ii))etplus particulièrementverslesméthodesderechercheetd’améliorationlocale.Leconcept d’amélioration locale est assez simple et surtout très intuitif. Une caractéristique de base des problèmes NP-difficiles est qu’une solution réalisable pour chacun de ces problèmespeutêtrecalculéeentempspolynomial.L’améliorationlocaleestdoncba- séesurl’idéesuivante: –oncalculeentempspolynomialunesolutionréalisableinitiale; –partantdecettesolution,onessaiedel’améliorer,tantquefairesepeut,pardes transformations locales, c’est-à-dire en remplaçant quelques éléments de la solution 2.Pourquoicettedésignationévocatricepourlapremière?Toutsimplementparrespectvis-à- vis de l’évolutionhistorique de la théorie de l’approximationpolynomialeà garantie de per- formance:cetteévolutions’estconstruitesurlathéorieappeléeici«classique»,théoriequi adoncétéplussouventexploitée(àtortpensons-nous)quelathéoriedifférentielle;cetteder- nière, bien qu’ayant donné lieu à quelques résultats ponctuels depuis la fin des années 1970 (voirparexemple[AUS80,HSU79],etc.),n’aétéréellementformaliséeetsystématiquement utiliséequedepuis1993[DEM93,DEM96]. Avant-propos 13 courantepard’autres,detellefaçonquelanouvellesolutionobtenueresteréalisable etaitunevaleurobjectivemeilleurequelasolutionprécédente; –dès lors qu’une telle amélioration n’est plus possible (on a atteint un opti- mum local), l’algorithme s’arrête et renvoie la dernière solution construite (qui est lameilleure,ausensdel’objectif,detoutescellesconsidérées). Cettetechniqued’améliorationlocalepeutavoirdesvariantespolynomialesouex- ponentielles.Si,parexemple,nouschoisissonsdechangerpeud’éléments(unnombre constant)lorsdupassaged’unesolutionàuneautre,laconvergenceversunoptimum localpeutsefaireentempspolynomial.Sienrevancheondécidedechangerbeaucoup d’élémentslorsdecepassage(parexempleunnombrefonctioncroissantedelataille del’instanceduproblème),alorslenombred’étapesàparcouriravantd’atteindreun optimumlocalsera,aupiredescas,exponentiel. L’amélioration locale est historiquement parmi les premières méthodes utilisées pour la résolution des problèmes combinatoires (voir, par exemple, ses diverses ap- plications à la résolution du problème du voyageur de commerce) et reste toujours d’actualité(laplupartdesmétaheuristiques–recuitsimulé,tabou,etc.–sontdesim- plémentations particulières de cette méthode). Exception faite des métaheuristiques quinenousconcernentpasdanscelivre,l’utilisationdelarecherchelocaleetsurtout desavariantepolynomialefutjusqu’iciponctuelleetsurtoutliéeàl’angle(i),c’est-à- direàlaconceptiond’unetelleméthodepourunproblèmeparticulierpourlequelles présomptionssontfortesdepenserquelaméthodemarcherait.Ici,nousadoptonsune démarchecompatibleavecl’angle(ii):nousconsidéronsdesalgorithmesapprochés s’adressant à des classes de problèmes et essayons de désigner des caractéristiques plus ou moins globales pour la conception de tels algorithmes. Nous traitons la re- cherche locale de cette façon et même, nous exigeons d’elle quelque chose de plus strictencore:quetoutoptimumlocalrespecteunecertainegarantiedeperformance (quecesoitlagarantieclassiqueoudifférentielle). Donc, le but de cet ouvrage n’est pas de parler de l’approximation polynomiale en général (quoiqu’un tel ouvrage manque à la littérature scientifique francophone). Pourceci,lelecteurintéresséestinvitéàseréférerà[AUS99,HOC97],maisaussi à [[GAR79] chapitre 6], ou encore à [[PAP81] chapitre 17] pour ce qui concerne l’approximationclassique.Notreobjectifesticidelierl’approximationpolynomiale àl’améliorationlocalequigarantitlesperformancesdesesoptimalocaux;cettega- rantieétantindifféremmentlagarantieclassiqueoulagarantiedifférentielle,avectout demêmeuneorientationplusmarquéeverslaseconde.Parlamêmeoccasion,nous faisons une présentation rapide mais assez formelle de ces deux théories d’approxi- mation polynomiale, de leurs fondements et de leur complémentarité. Nousmettons enévidencelefaitquel’utilisationconjointedesdeuxthéoriespeutcontribuerformi- dablementàunemeilleurecompréhensiondeladifficultéintrinsèquedes problèmes