Optimisation combinatoire Springer Paris Berlin Heidelberg New York Hong Kong Londres Milan Tokyo Bernhard Korte Jens Vygen Optimisation combinatoire Théorie et algorithmes Traduit de l’anglais par Jean Fonlupt et Alexandre Skoda Bernhard Korte Jens Vygen Research Institute Research Institute for Discrete Mathematics for Discrete Mathematics University of Bonn University of Bonn Lennéstraße 2 Lennéstraße 2 53113 Bonn 53113 Bonn Germany Germany [email protected] [email protected] Traducteurs Jean Fonlupt Alexandre Skoda Professeur émérite Université Paris-I Université Paris-VI Panthéon-Sorbonne Faculté de mathématiques Centre d’économie de la Sorbonne 175,rue du Chevaleret 106-112,boulevard de l’Hôpital 75013 Paris 75013 Paris [email protected] [email protected] ISBN : 978-2-287-99036-6 Springer Paris Berlin Heidelberg New York ©Springer-Verlag France 2010 Imprimé en France Springer-Verlag France est membre du groupe Springer Science+ Business Media Cet ouvrage est soumis au copyright. Tous droits réservés,notamment la reproduction et la représentation,la traduc- tion,la réimpression,l’exposé,la reproduction des illustrations et des tableaux,la transmission par voie d’enregistre- ment sonore ou visuel, la reproduction par microfilm ou tout autre moyen ainsi que la conservation des banques données. La loi française sur le copyright du 9 septembre 1965 dans la version en vigueur n’autorise une reproduction intégrale ou partielle que dans certains cas,et en principe moyennant les paiements des droits. Toute représentation, reproduction,contrefaçon ou conservation dans une banque de données par quelque procédé que ce soit est sanctionnée par la loi pénale sur le copyright. L’utilisation dans cet ouvrage de désignations,dénominations commerciales,marques de fabrique,etc.,même sans spécification ne signifie pas que ces termes soient libres de la législation sur les marques de fabrique et la protection des marques et qu’ils puissent être utilisés par chacun. La maison d’édition décline toute responsabilité quant à l’exactitude des indications de dosage et des modes d’emplois. Dans chaque cas il incombe à l’usager de vérifier les informations données par comparaison à la littérature existante. Maquette de couverture:Jean-François MONTMARCHÉ Illustration de couverture :Ina PRINZ Collection IRIS Dirigée par Nicolas Puech Ouvrages parus : – Méthodes numériques pour le calcul scientifique. Programmes en Matlab A. Quarteroni, R. Sacco, F. Saleri, Springer-Verlag France, 2000 – Calcul formel avec MuPAD F. Maltey, Springer-Verlag France, 2002 – Architecture et micro-architecture des processeurs B. Goossens, Springer-Verlag France, 2002 – Introduction aux mathématiques discrètes J. Matousek, J. Nesetril, Springer-Verlag France, 2004 – Les virus informatiques : théorie, pratique et applications É. Filiol, Springer-Verlag France, 2004 – Introduction pratique aux bases de données relationnelles. Deuxième édition A. Meier, Springer-Verlag France, 2006 – Bio-informatique moléculaire. Une approche algorithmique P.A. Pevzner, Springer-Verlag France, 2006 – Algorithmes d’approximation V. Vazirani, Springer-Verlag France, 2006 – Techniques virales avancées É. Filiol, Springer-Verlag France, 2007 – Codes et turbocodes C. Berrou, Springer-Verlag France, 2007 – Introduction à Scilab. Deuxième édition J.P. Chancelier, F. Delebecque, C. Gomez, M. Goursat, R. Nikouhah, S. Steer, Springer-Verlag France, 2007 – Maple : règles et fonctions essentielles N. Puech, Springer-Verlag France, 2009 – Les virus informatiques : théorie, pratique et applications. Deuxième édition É. Filiol, Springer-Verlag France, 2009 À paraître : – Concepts et méthodes en phylogénie moléculaire G. Perrière, Springer-Verlag France, 2010 Pre´face Ce livre est la traduction franc¸aise de la quatrie`me e´dition du livre Combina- torial Optimization : Theory and Algorithms e´crit par deux e´minents spe´cialistes, BernhardKorteetJensVygen,professeursa`l’universite´deBonn.Conside´re´comme unouvragedere´fe´rence,ils’adressea`deschercheursconfirme´squitravaillentdans le champ de la recherche fondamentale ou de ses applications (R&D). Il donne unevisioncomple`tedel’optimisationcombinatoireetpeutdoncaussiinte´resserde nombreuxscientifiquesnonspe´cialistesayantunebonnecultureenmathe´matiques etdesconnaissancesdebaseeninformatique. L’optimisationcombinatoireestundomaineassezre´centdesmathe´matiquesap- plique´es,quiplongesesracinesdanslacombinatoire(principalementlathe´oriedes graphes),larechercheope´rationnelleetl’informatiquethe´orique.Unedesraisonsde sonde´veloppementestlie´eaunombreconside´rabledeproble`mesconcreˆtsqu’elle permetdeformuler.Ils’agitengrandepartiedeproble`mespourlesquelsonconnaˆıt de «bons» algorithmes de re´solution; ceux-ci sont e´tudie´s dans la premie`re partie de ce livre. Une des originalite´s de cet ouvrage, par rapport a` d’autres traite´s, est de pre´senter les algorithmes de re´solution ayant la meilleure borne de complexite´ connuea`cejour. Lasecondepartietraitedesproble`mesdifficilesa` re´soudresurleplanalgorith- mique et connus sous le nom de proble`mes NP-difficiles. Le plus ce´le`bre d’entre eux, celui du voyageur de commerce, fait l’objet, au chapitre 21, d’une e´tude par- ticulie`rementapprofondie.D’autrestoutaussiimportants,commelesproble`mesde conception de re´seaux, de multi-flots, de localisation de services, etc., be´ne´ficient e´galementd’unepre´sentationde´taille´e,cequiestpeufre´quentdanslalitte´ratureet me´rited’eˆtresignale´. Danslatraductionquenousproposons,nousavonscherche´a`traduireenfranc¸ais touteslesexpressionsettouslestermesanglo-saxonsmeˆmequandaucunetraduc- tion n’existait; il y a cependant quelques exceptions pour des termes tre`s tech- niques qui ne sont universellement connus que sous leur de´nomination anglaise. Nousavonsenoutreinclusquelquesame´liorationsetcorrectionse´critesparlesau- teursapre`slaparutiondel’e´ditionoriginaleactuelle;celles-ciserontinte´gre´esdans lacinquie`mee´ditionanglaise,actuellementenpre´paration. Paris,juillet2009 JeanFonluptetAlexandreSkoda Avant-propos a` la quatrie`me e´dition originale Avecquatree´ditionsanglaisesetquatretraductionsencours,noussommestre`s heureuxdel’e´volutiondenotrelivre;celui-ciae´te´ re´vise´,actualise´ etame´liore´ de manie`resignificativepourcettequatrie`mee´dition.Nousyavonsinclusdesmatie`res classiques, parfois manquantes dans les e´ditions pre´ce´dentes, notamment sur la programmation line´aire, la me´thode network simplex et le proble`me de la coupe maximum. Nous avons e´galement ajoute´ de nouveaux exercices et mis a` jour les re´fe´rences. Noussommesreconnaissantsa` l’Uniondesacade´miesallemandesdessciences etdeslettreseta` l’Acade´miedessciencesduLandRhe´nanie-du-Nord-Westphalie pourleursoutienpermanentparl’interme´diaireduprojet«Mathe´matiquesdiscre`tes etapplications».Nousremercionse´galementpourleurscommentairespre´cieuxtous ceux qui nous ont contacte´ apre`s la troisie`me e´dition, en particulier Takao Asano, ChristophBartoschek,BertBesser,UlrichBrenner,JeanFonlupt,SatoruFujishige, Marek Karpinski, Jens Maßberg, Denis Naddef, Sven Peyer, Klaus Radke, Rabe von Randow, Dieter Rautenbach, Martin Skutella, Markus Struzyna, Ju¨rgen Wer- ber,MinyiYue,etGuochuanZhang.Nouscontinueronsa` fournirdesinformations actualise´essurcetouvragea` l’adresse: http ://www.or.uni-bonn.de/∼vygen/co.html Bonn,aouˆt2007 BernhardKorteetJensVygen Sommaire Pre´face ........................................................ vii Avant-proposa` laquatrie`mee´ditionoriginale........................ ix Sommaire...................................................... xi 1 Introduction ............................................... 1 1.1 E´nume´ration............................................... 2 1.2 Tempsd’exe´cutiondesalgorithmes ........................... 5 1.3 Proble`mesd’optimisationline´aire ............................ 8 1.4 Tri ....................................................... 9 Exercices ...................................................... 11 Re´fe´rences..................................................... 12 2 Graphes ................................................... 13 2.1 De´finitionsfondamentales ................................... 13 2.2 Arbres,cycles,coupes ...................................... 17 2.3 Connexite´ ................................................ 25 2.4 Grapheseule´riensetbipartis ................................. 32 2.5 Planarite´ ................................................. 34 2.6 Dualite´ planaire ........................................... 42 Exercices ...................................................... 45 Re´fe´rences..................................................... 49 3 Programmationline´aire ..................................... 51 3.1 Polye`dres ................................................. 53 3.2 Algorithmedusimplexe .................................... 56 3.3 Imple´mentationdel’algorithmedusimplexe ................... 59 3.4 Dualite´ ................................................... 63 3.5 Enveloppesconvexesetpolytopes ............................ 67 Exercices ...................................................... 68 Re´fe´rences..................................................... 71 xii Optimisationcombinatoire–The´orieetalgorithmes 4 Algorithmesdeprogrammationline´aire......................... 73 4.1 Tailledessommetsetdesfaces ............................... 74 4.2 Fractionscontinues ........................................ 76 4.3 Me´thoded’e´liminationdeGauss ............................. 79 4.4 Me´thodedesellipso¨ıdes ..................................... 83 4.5 The´ore`medeKhachiyan..................................... 88 4.6 Se´parationetoptimisation ................................... 90 Exercices ...................................................... 97 Re´fe´rences..................................................... 99 5 Programmationennombresentiers ............................ 101 5.1 Enveloppeentie`red’unpolye`dre .............................103 5.2 Transformationsunimodulaires ...............................107 5.3 Totaleduale-inte´gralite´ .....................................109 5.4 Matricestotalementunimodulaires ...........................112 5.5 Planscoupants ............................................117 5.6 Relaxationlagrangienne.....................................122 Exercices ......................................................124 Re´fe´rences.....................................................128 6 Arbrescouvrantsetarborescences ............................. 131 6.1 Arbrecouvrantdepoidsminimum ............................132 6.2 Arborescencedepoidsminimum .............................138 6.3 Descriptionspolye´drales ....................................142 6.4 Empilementsd’arbresetd’arborescences ......................145 Exercices ......................................................148 Re´fe´rences.....................................................152 7 Pluscourtschemins ......................................... 155 7.1 Pluscourtscheminsa` partird’unesource ......................156 7.2 Pluscourtscheminsentretouteslespairesdesommets ...........161 7.3 Circuitmoyenminimum ....................................163 Exercices ......................................................165 Re´fe´rences.....................................................167 8 Flotsdanslesre´seaux ........................................ 171 8.1 The´ore`meflot-max/coupe-min................................172 8.2 The´ore`medeMenger .......................................176 8.3 Algorithmed’Edmonds-Karp.................................178 8.4 FlotsbloquantsetalgorithmedeFujishige......................180 8.5 AlgorithmedeGoldberg-Tarjan...............................182 8.6 ArbresdeGomory-Hu ......................................187 8.7 Capacite´ d’unecoupedansungraphenonoriente´ ...............193 Exercices ......................................................195 Re´fe´rences.....................................................201 Sommaire xiii 9 Flotsdecouˆtminimum ...................................... 205 9.1 Formulationduproble`me ...................................205 9.2 Uncrite`red’optimalite´ ......................................207 9.3 Algorithmepare´liminationducircuitmoyenminimum ..........210 9.4 Algorithmeparpluscourtscheminssuccessifs ..................213 9.5 Algorithmed’Orlin .........................................217 9.6 Algorithmenetworksimplex .................................221 9.7 Flotsdynamiques ..........................................225 Exercices ......................................................227 Re´fe´rences.....................................................231 10 Couplagemaximum ......................................... 235 10.1 Couplagedanslesgraphesbipartis ............................236 10.2 MatricedeTutte ...........................................238 10.3 The´ore`medeTutte .........................................240 10.4 De´compositionsenoreillesdesgraphesfacteur-critiques .........243 10.5 Algorithmeducouplaged’Edmonds...........................249 Exercices ......................................................259 Re´fe´rences.....................................................262 11 Couplageavecpoids ......................................... 267 11.1 Proble`med’affectation ......................................268 11.2 Aperc¸udel’algorithmeducouplageavecpoids .................269 11.3 Imple´mentationdel’algorithmeducouplageavecpoids ..........272 11.4 Postoptimalite´ .............................................286 11.5 Polytopeducouplage .......................................287 Exercices ......................................................291 Re´fe´rences.....................................................293 12 b-couplagesetT-joints....................................... 295 12.1 b-couplages ...............................................295 12.2 T-jointsdepoidsminimum ..................................299 12.3 T-jointsetT-coupes........................................303 12.4 The´ore`medePadberg-Rao...................................306 Exercices ......................................................310 Re´fe´rences.....................................................313 13 Matro¨ıdes ................................................. 315 13.1 Syste`mesd’inde´pendanceetmatro¨ıdes ........................315 13.2 Autresaxiomes ............................................320 13.3 Dualite´ ...................................................324 13.4 Algorithmeglouton ........................................329 13.5 Intersectiondematro¨ıdes ....................................334 13.6 Partitiondematro¨ıdes ......................................339 13.7 Intersectiondematro¨ıdesavecpoids ..........................341 Exercices ......................................................345 Re´fe´rences.....................................................348