PG 534 Introducere rutare vehicul

PG 534 Introducere rutare vehicul Markus Chimani & Karsten Klein LS11, TU Dortmund

Obiective PG Cadru ramură și tăiere, ramură și preț, funcții obiective selectabile, constrângeri, euristici, inegalități, metode de separare etc. Studiu experimental și date practice

Prezentare generală a elementelor de bază: exemple mici LP vs. Metode de soluție ILP Solver/Framework Exemplu mare TSP: formulare, reduceri SCIP: Cod de bază SCIP pentru conturi organizaționale TSP, server web etc. Vineri

Programare liniară Formularea unei probleme de optimizare cu vector variabil x = (x 1, xn) prin: Funcție de cost liniar cu vector de cost c = (c 1. cn) min i = 1.ncixi (de asemenea, max) Ecuații liniare (în) ca constrângeri i = 1.naixib (de asemenea,) forme speciale: xi 0 vector x care îndeplinește toate condițiile: vector soluție validă x * cu cx * cx valid x: soluție optimă

Program liniar Scris: min/max c 1 x 1 +. + c n x n sto a 11 x 1 +. + a 1n x n b 1. Formă standard: a m1 x 1 +. + a mn x n b m x i variabile nelimitate, sau x i 0 inițial transformată funcția obiectivă max cx min -cx ecuație a j x b j a j x + s = b j, s 0 variabilă nelimitată x i x i + x i - cu x i +, x i- 0

Notare compactă cu program liniar cu matrice A R m, n, vectori b R m, c, x R n: min

Exemplu: Problema dietei xi: Diverse alimente bi: Aprovizionare ideală cu nutrienți (de exemplu, vitamine), ci: Costul unui aliment Obiect: Cea mai ieftină dietă cu aport suficient de alimente Valoare calorică/kcal Vitamina C/mg Preț/pâine (500g) 1230 0 2,99 Suc de portocale ( 1l) 560 300 2,50 Cerință: 2000 60.min 2.99x 1 + 2.50x 2 sto 1230x 1 + 560x 2 2000 300x 2 60 x 1, x 2 0

Programare liniară Complexitate: Problemele de optimizare liniară pot fi rezolvate în timp polinomial Metode: Metoda punctelor interioare Metoda elipsoidelor Metoda Simplex (cel mai rău caz exponențial)

Vectorii de interpretare geometrică: direcție, lungime costuri x 1 + x 2 vector c = (1,1) 4 3 2 1 1 2 3 4

Vectorii de interpretare geometrică: direcția, lungimea costă x 1 + x 2 vectorul c = (1,1) 4 3 2 1 1 2 3 4

Vectorii de interpretare geometrică: direcție, lungime costuri x 1 + x 2 vector c = (1,1) ecuație x 1 + 2x 2 = 3 vector a = (1,2) 4 3 2 1 1 2 3 4

Vectorii de interpretare geometrică: direcția, lungimea costă x 1 + x 2 vector c = (1,1) ecuație x 1 + 2x 2 = 3 vector a = (1,2) 4 x 2 = ½ (3-x 1) 3 2 1 1 2 3 4

Vectorii de interpretare geometrică: direcția, lungimea costă x 1 + x 2 vector c = (1,1) ecuație x 1 + 2x 2 = 3 vector a = (1,2) 4 3 2 1 x 1 + 2x 2 = 4 1 2 3 4

Vectorii de interpretare geometrică: direcție, lungime costuri x 1 + x 2 vector c = (1,1) ecuație x 1 + 2x 2 = 3 vector a = (1,2) 4 3 2 1 hiperplan, general, n-1 dimensional 1 2 3 4

Vectorii de interpretare geometrică: direcția, lungimea costă x 1 + x 2 vector c = (1,1) ecuație x 1 + 2x 2 = 3 vector a = (1,2) 4 3 inegalitate x 1 + 2x 2 3? 2 1 jumătate de spațiu, general, n-dimensional 1 2 3 4

Vectorii de interpretare geometrică: direcția, lungimea costă x 1 + x 2 vector c = (1,1) ecuație x 1 + 2x 2 = 3 vector a = (1,2) 4 3 2 1 max x 1 + x 2 x 1 + 2x 2 3 2x 1 + x 2 3 x 1, x 2 0 poliedre, general, 1 2 3 4 soluție optimă (1, 1), valoare 2

Intermezzo Interactive CPLEX: LP1

Soluția de programare liniară din ultimul exemplu a fost un număr întreg! Dacă nu, dar este necesar un întreg?

Programare liniară întreagă ILP: întreg al soluției necesare (discret) ILP mixt: Dacă este doar pentru unele întregi 4 3 2 max x 1 + x 2 sto 14 x 1-18x 2-9 2x 1-2 x 2 1 x 1, x 2 0 1 CPLEX interactiv: LP2 1 2 3 4

Programare liniară în întregime ILP: Soluția necesită un număr întreg (discret) ILP mixt: Dacă este doar pentru unele întregi 4 3 2 max x 1 + x 2 sto 14 x 1-18x 2-9 2x 1-2 x 2 1 x 1, x 2 0 1 1 2 3 4 Soluție optimă (4.5, 4), valoare 8.5

Programare liniară întreagă ILP: numere întregi ale soluției necesare (discrete) ILP mixtă: Dacă numai pentru unele întregi xi separă soluția invalidă 4 Creați x 1 Tăiați 4 x 1 5 max x 1 + x 2 3 2 sau ramificați sto 14 x 1-18x 2 -9 2x 1-2 x 2 1 x 1, x 2 0 1 x 1, x 2 întreg Calculați mai întâi relaxarea 1 2 3 4

Programare liniară întreagă ILP: numere întregi ale soluției necesare (discrete) ILP mixtă: Dacă numai pentru unele întregi Xi CPLEX interactiv: LP2ILP 4 3 2 1 max x 1 + x 2 sto 14 x 1-18x 2-9 2x 1-2 x 2 1 x 1, x 2 0 x 1, x 2 soluție optimă întreagă (2, 2), valoare 4 1 2 3 4

Programarea liniară în întregime ILP este NP-completă, chiar și în cazul special x i Puterea formulării: Mult mai important decât cu LP! Numărul de variabile și constrângeri nu este decisiv aici, dar modul în care constrângerile descriu exact corpul convex al soluțiilor întregi valide!

B&C & P (unele) Solver/Cadre COIN-OR LP (M) ILP CPlex CPlex SCIP SoPlex Abacus BCP Symphony CBC OSI CLP scump, dar cel mai rapid software gratuit și multe altele.

TSP: Formulare (1) Dat: dorit: n orașe: S = distanțe între orașe: d (a, b) Cea mai scurtă călătorie dus-întors prin toate orașele Variabile: xv, wv, w S Funcția țintă: min d (v, w) xv, wv, w p

TSP: Formulare (2) Variabile: xv, wv, w S Funcția țintă: min d (v, w) xv, w Constrângeri: v, w S w S xv, w = 2 v S v T w T xv, w 2 TS exponențial mulți!

Ați terminat toate problemele secundare? TSP: Metode de soluție Calculați euristică: limita superioară O Subproblemă 1. Rezolvați PL (polinom, CPLEX) Începeți cu un program liniar mai simplu P min v, w S 0 xv, w 1 d (v, w) xv, wv, w S 2. Actual Sunt valabil? O min (o, L)! 3. Este L O? Terminați subproblema. 4. Euristică bazată pe L posibil nou O 5. Găsiți o inegalitate încălcată (*)? Adăugați la P și mergeți la 1. O este optim w S x v, w = 2 v S subproblemă x v, w = 0 subproblemă x v, w = 1 x v, w 2 T S (*) v T w T

SCIP: Prezentare generală SCIP = Rezolvarea programelor întregi de constrângeri http://scip.zib.de, Doxygen-Docs (foarte bun și util) @home: descărcați, compilați prin (implicit: gcc, linux) faceți LPS =? READLINE = false ZLIB = false ZIMPL = false spx (SoPlex), clp (CLP) @uni: instalat și compilat (LPS = cpx/CPlex) în /home/plug/scip-1.1.0 Exemple: TSP, VRP,/home/plug /scip-1.1.0/examples/

TSP cu SCIP: (Unele) fișiere importante Fișiere esențiale mymain.cpp main () Configurarea structurilor SCIP Înregistrarea plug-in-urilor (cititor, separare, euristică, tarifare) myreader.h myreader.cpp mysubtour.h mysubtour.cpp Citirea problemei Crearea LP-ului inițial Separarea constrângerilor subtur

mymain.cpp #include #include "objscip/objscip.h" #include "objscip/objscipdefplugins.h" #include "myreader.h" #include "mysubtour.h" SCIP_RETCODE runscip (int argc, char ** argv) < >SCIP * scip = NULL; SCIP_CALL (SCIPcreate (& scip)); SCIP_CALL (SCIPincludeObjReader (scip, MyReader nou (scip), TRUE)); SCIP_CALL (SCIPincludeObjConshdlr (scip, MySubtour nou (), TRUE)); SCIP_CALL (SCIPincludeDefaultPlugins (scip)); SCIP_CALL (SCIPprocessShellArguments (scip, argc, argv, "parametru.txt")); SCIP_CALL (SCIPfree (& scip)); returnează SCIP_OKAY; int main (int argc, char ** argv) < >SCIP_RETCODE retcode = runscip (argc, argv); if (retcode! = SCIP_OKAY) SCIPprintError (retcode, stderr); SCIP_CALL (. ()); SCIP_RETCODE ret =. (); if (ret! = SCIP_OKAY) returnează ret; SCIPprocessShellArguments. SCIPsolve (scip);.

TSP cu SCIP: (Unele) fișiere importante Fișiere esențiale mymain.cpp myreader.h myreader.cpp main () Configurarea structurilor SCIP Înregistrarea plug-in-urilor (cititor, separare, euristică, tarifare) Citirea problemei Crearea mysubtour-ului LP inițial. h mysubtour.cpp Separarea constrângerilor subtour

MyReader () <> virtual SCIP_RETCODE scip_free (SCIP * scip, SCIP_READER * cititor) < return SCIP_OKAY; >SCIP_RETCODE virtual scip_write (. rezultat SCIP_RESULT *) < >* rezultat = SCIP_DIDNOTRUN; returnează SCIP_OKAY; >; SCIP_RETCODE virtual scip_read (SCIP * scip, SCIP_READER * cititor, const char * nume de fișier, rezultat SCIP_RESULT *);

myreader.cpp #include "myprobdata.h" // clasa MyProbData: public scip: objprobdata; SCIP_RETCODE MyReader: scip_read (SCIP * scip, cititor SCIP_READER *, const char * nume de fișier, rezultat SCIP_RESULT *) < *result = SCIP_DIDNOTRUN; MyProbData* graph = loadgraphfromfile(filename); // assume function exists if(graph == NULL) return SCIP_READERROR; SCIP_CALL( SCIPcreateObjProb(scip, "MyProblemData", graph, TRUE) ); // add variables for( alle kanten edge von graph ) < >SCIP_VAR * var; numele stringstream; id-ul numelui; SCIP_CALL (SCIPcreateVar (scip, & var, name.str (). C_str (), 0, 1, margine-> lungime, SCIP_VARTYPE_BINARY, TRUE, FALSE, NULL, NULL, NULL, NULL)); edge-> corespunzătorvar = var; SCIP_CALL (SCIPaddVar (scip, var)); > *** următorul diapozitiv aici: adăugați constrângeri *** * rezultat = SCIP_SUCCESS; returnează SCIP_OKAY; 0, 1, margine-> lungime limită inferioară: 0, limită superioară: 1, coeficient în funcția obiectivului

myreader.cpp // adaugă constrângeri de grad pentru (toate nodurile noduri ale graficului) < SCIP_CONS* cons; stringstream name; name id; SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name.str().c_str(), 0, NULL, NULL, 2.0, 2.0, TRUE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) ); w S x v,w = 2 v S for( alle kanten edge adjazent zu node ) SCIP_CALL( SCIPaddCoefLinear(scip, cons, edge->corespunzător, 1.0)); 0, NULL, NULL 0 variabile, matrice goală pentru variabile, matrice goală pentru coeficienți> SCIP_CALL (SCIPaddCons (scip, contra)); SCIP_CALL (SCIPreleaseCons (scip, & contra)); // adăugați controlerul de constrângeri subtour SCIP_CONS * contra; SCIP_CONSDATA * consdata; SCIP_CALL (SCIPallocMemory (scip, & consdata)); consdata-> grafic = grafic; SCIP_CALL (SCIPcreateCons (scip, contra, nume, SCIPfindConshdlr (scip, "subtour"), consdata, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE)); SCIP_CALL (SCIPaddCons (scip, contra)); SCIP_CALL (SCIPreleaseCons (scip, & contra)); 2.0, 2.0 stânga și dreapta limitează 2.0 constrângerea 2.0

MySubtour () <> // este valabilă o soluție? virtual SCIP_RETCODE scip_check (. SCIP_SOL * sol.); virtual SCIP_RETCODE scip_enfolp (.); lp = soluție fracțională virtuală SCIP_RETCODE scip_enfops (.); ps = pseudo soluție enfo = enforce // rotunjirea implicațiilor constrângerilor virtuale SCIP_RETCODE scip_lock (.); Pentru validitate // separați SCIP_RETCODE virtual scip_sepalp (.); virtual SCIP_RETCODE scip_sepasol (. SCIP_SOL * sol.); >; Pentru viteze (*), (**) implementări în mare parte identice sau foarte similare