Cours de modelisation en PLI

Description

Chapitre 6Mod´elisation en P.L.I.6.1 Lien entre PL et PLI(P) probl`eme de PL.– On restreint les variables `a ˆetre enti`eres : on a un probl`eme de PLI (ILP en anglais).– On restreint certaines variables `a ˆetre enti`eres : on a un probl`eme mixte (MILP enanglais).– On peut aussi contraindre les variables `a ˆetre dans {0,1} : on a un probl`eme deprogrammation 0-1.La question de r´esoudre efficacement les problemes de PLI se pose donc. On sait qu’onpeut le faire de mani`ere efficace pour la PL en th´eorie (le probl`eme est polynomial) eten pratique (bien que exponentiel dans le pire cas, le simplexe fonctionne bien). Peut-onobtenir les mˆemes r´esultats pour le probl`eme de PLI?6.1.1 Approximation de la PLIUne m´ethode imm´ediate consiste `a r´esoudre le probl`eme de PL obtenu en relachant lacontrainte x∈N en x∈R, `a r´esoudre le probl`eme de PL obtenu, puis `a prendre commesolution la solution enti`ere la plus proche. Plusieurs probl`emes se posent :– Quelle approximation? partie enti`ere inf´erieure ou sup´erieure, la plus proche?x = 1.22 est proche de ⌊x⌋ = 1 et ⌈x⌉ = 2, le plus proche est 1. Mais x = 1.5 estaussi proche de 1 que de 2.Par contre le dessin suivant montre que c¸a ne donne pas forc´ement une solution!1´2 CHAPITRE 6. MODELISATION EN P.L.I.– Quelle est le lien entre solution enti`eres et solution r´eelles? Le dessin suivant montrequ’elle peuvent ˆetre tr`es ´eloign´ees.Le seul lien exact qu’on peut ´etablir (pour un probl`eme de ...

Informations

• Publié par: Onfue
• Nombre de lectures: 35
• Langue: Français

Extrait

Chapitre 6

Mod´elisationenP.L.I.

6.1 Lienentre PL et PLI

(P)proble`medePL. –Onrestreintlesvariablesa`ˆetreenti`eres:onaunproble`medePLI(ILPenanglais). –Onrestreintcertainesvariablesa`eˆtreentie`res:onaunproble`memixte(MILPen anglais). –Onpeutaussicontraindrelesvariables`aeˆtredans{0,1}:uanoorpne`lbmede programmation 01. Laquestionder´esoudreefficacementlesproblemesdePLIseposedonc.Onsaitqu’on peutlefairedemanie`reefficacepourlaPLenthe´orie(leprobl`emeestpolynomial)et en pratique (bien que exponentiel dans le pire cas, le simplexe fonctionne bien). Peuton obtenirlesmeˆmesre´sultatspourleproble`medePLI?

6.1.1 Approximationde la PLI

Uneme´thodeimm´ediateconsistea`re´soudreleproble`medePLobtenuenrelachantla contraintex∈ Nenx∈ Rcerdemmoreudso´ear,`medePeoLelrpbo`lis`aprenbtenu,pu solutionlasolutionenti`erelaplusproche.Plusieursproble`messeposent: –Quelleapproximation?partieenti`ereinfe´rieureousupe´rieure,laplusproche? x= 1.22 est proche de⌊x⌋= 1 et⌈x⌉= 2, le plus proche est 1. Maisx= 1.5 est aussi proche de 1 que de 2. Parcontreledessinsuivantmontreque¸canedonnepasforc´ementunesolution! 1

2

´ CHAPITRE 6.MODELISATION EN P.L.I.

–Quelleestlelienentresolutionentie`resetsolutionr´eelles?Ledessinsuivantmontre qu’ellepeuventeˆtretr`es´eloigne´es.

Leseullienexactqu’onpeut´etablir(pourunprobl`emedemaximisation)estquesi zimptfotiecbjnoioedeme`lborpudelaestlPL,sinotclefauedrvalazest la valeur de lafonctionobjectifduprobl`emedePLI,alorsz≥zteiseCalidtamme´oute:.ra¯jrla contrainted’inte´grit´elimitelenombredevaleursadmissiblesdonclenombredevaleurs possibles de la fonction objectif. (Pourunproble`medeminimisation,onauraz≤z¯).

6.1.2Me´thodesadhoc Onpeutcherchera`mettreaupointdestechniquesadapt´eesauxproble`mesparticuliers de PLI. –Programmationdynamiquequiestunem´ethodea`basedetabulationpourstocker desr´esultatsinterm´ediairesquinesontdonccalcul´esqu’unefois. –Me´thodesbranchandbound(Se´parationetEvaluation,enfran¸cais).M´ethodesqui permettentdetrouverlasolutionen´enume´rantdemani`ereintelligentetoutesles valeursenti`erespossiblespourlesvariables. –Me´thodeparticulie`rescommelescoupesdeGomory.

6.1.3Limitethe´orique Ensereportantaucoursdecomplexit´e,vousverrezqueleproble`medeprogrammation lin´eaireennombreentiersestunproble`meNPcomplet:cesontlesproble`meslesplus difficilesdelaclasseNPetsionsavaitlesr´esoudreentempspolynomial,alorsonaurait 1 P=NP,cequiestconsid´er´ecommeimprobable(encoreque...).Donctoutalgorithme d´eterministepolynomialqu’ontrouverapourre´soudreleproble`medemanderaaumoins un temps exponentiel. Enfaitlesimplefaitprobl`emeder´esoudreunsyste`med’´equationdiophantiennes(donc uneconjonctiond’e´galit´es)quicorresponda`uncastr`esparticulierdelaPLIpuisqu’aucune fonctionobjectifnedoiteˆtreoptimis´eeetquetouslescoefficientssontentiersestde´ja`un probl`emeNPcomplet. 1 voirl’articledeDelahayedanspourlasciencenume´rode2005

6.2. EXEMPLES

3

Iln’estd’ailleurspase´videntdemontrerqueleproble`medePLI(`acoefficientsentiers) est dans la classe NP. Pour cela une majoration de la taille des solutions minimales est n´ece´ssaireetilfaut´egalementsupposerquelesentierssontr´epresent´esenbaseb >1 (sinon uneexponentiellesuppl´ementaireintervient).

6.2 Exemples 6.2.1 Levoyageur de commerce Unvoyageurdecommercedoitfairesatourne´eenvisitantnvillesx 1 , . . . , x n en ne visitant chaque villex i , (i6= 1) qu’une seule fois en partant dex 1 puis en y retournant. La distance entre la villex i et la villex j rapee´nnodtsec i,j >0 (i6=j)et la question est deminimiserladistanceparcouruedanslatourn´ee.L’ensembledesvillessemod´elisepar ungraphecomplete´tiquett´e(toutevilleestaccessibled’uneautrevile).Ceprobl`emeest connu comme celui du voyageur de commerce (TSP en anglais). Remarque : on peut avoirc i,j =c j,i pour touti, j)euoiruqibnero(p`eblsymeetm´ c i,j 6=c j,i pour certainsi, joN.etiartsuilicnsro`exieuedestleplumecasquila.gse´´nre 2 – Choixdes variables :x i,j (nlbaiq)seravournilatut1suivaa’crtnlepmure´eeia`j. –Mode´liserlechemin: –jen’arrivequ’uneseulefois`alavillei: un seul arc entrant suriestemprunt´e j=n i x j,i = 1 Σ j=1 c j, –uneseulevilleestvisit´eeenpartantdei: un seul arc sortant suristeprem´tnue j=n Σc j=1 i,j x i,j = 1 –Ladistance`aminimiser:z= Σ i∈{1,..,n} Σ j6=i,j∈{1,..,n} x i,j c i,j 2 On a donc de l’ordre deO(nea´iulqbvs)ertaesn.taoi Cettemod´elisationsemblecorrecte,malheureusementelleestincompl`ete.Ilpeuty avoir des souscycles comme dans l’exemple suivant : Comment´eliminercessolutionsparasites? Ajout de contraintesalamod´erajoute`l,canortilasitnoprexeqimntaiuieqnOopeuru tout sousensembleSga´eonunal`oedivnon{1, ..., n}, il y a au moins un chemin entreS ¯ etsoncomple´mentaireS: Σ ¯ x≥1 i∈S,j∈ S i,j n Cela donne un nombre de contraintes enOacsiavuamse`rttsiequce),2(duitntroroni unnombreexponentieldecontraintesdontlar´esolutionestcouteuse. Uneapprochepluspragmatique(utilise´edanslar´ealit´e)consistea`utiliserlapremi`ere mode´lisation.Sionaunesolutionsanscycleonagagne´(carlamode´lisationautoriseplus desolutionsquedanslare´alit´eetdoncsilasolutioncorrespond`aunevraietourn´eealors c’estbienceluicherche´).Sinononadescyclesinde´pendantson“casse”lecycleenrajoutant unecontraintequiexprimequ’ilyaaumoinsunarcemprunte´entredeuxsouscycles.Cela revient`anerajouterlescontraintes Σ i∈S,j∈S x i,j ≥1 ¯