Úvod do smerovania vozidiel PG 534

Smerovanie vozidiel PG 534 Úvod Markus Chimani a Karsten Klein LS11, TU Dortmund

Ciele PG Framework Branch & Cut, Branch & Price, voliteľné objektové funkcie, obmedzenia, heuristika, nerovnosti, separačné metódy atď. Experimentálne štúdium aj praktické údaje

Prehľad základov: Malé príklady Metódy riešenia LP vs. ILP Riešiteľ/Rámec Veľký príklad TSP: formulácia, škrty SCIP: Základné SCIP kód pre organizačné účty TSP, webový server atď. Piatok

Lineárne programovanie Formulácia optimalizačného problému s variabilným vektorom x = (x 1, xn) pomocou: Funkcia lineárnych nákladov s vektorom nákladov c = (c 1. cn) min i = 1.ncixi (tiež max.) Lineárne (ne) rovnice ako obmedzenia i = 1.naixib (tiež,) špeciálne tvary: xi 0 vektor x, ktorý spĺňa všetky podmienky: platné riešenie vektor x * s cx * cx platné x: optimálne riešenie

Lineárny program Vypísaný: min/max c 1 x 1 +. + c n x n sto a 11 x 1 +. + a 1n x n b 1. Štandardné tlačivo: a m1 x 1 +. + a mn x n b m x i neobmedzené premenné alebo x i 0 pôvodne transformovaná objektívna funkcia max cx min -cx rovnica a j x b j a j x + s = b j, s 0 neobmedzená premenná x i x i + x i - s x i +, x i- 0

Kompaktný zápis lineárneho programu s maticou A R m, n, vektory b R m, c, x R n: min

Príklad: Problém stravovania xi: Rôzne potraviny bi: Ideálny prísun živín (napr. Vitamínov) ci: Náklady na jedlo Objekt: Najlacnejšia strava s dostatočným prísunom potravy Výhrevnosť/kcal Vitamín C/mg Cena/chlieb (500 g) 1230 0 2,99 Pomarančová šťava ( 1l) 560 300 2,50 Požiadavka: 2000 60 min. 2,99 x 1 + 2,50 x 2 sto 1230 x 1 + 560 x 2 2000 300 x 2 60 x 1, x 2 0

Lineárne programovanie Zložitosť: problémy s lineárnou optimalizáciou je možné vyriešiť v polynomiálnom čase Metódy: Metóda vnútorných bodov Elipsoidná metóda Simplexná metóda (najhorší exponenciálny)

Vektory geometrickej interpretácie: smer, náklady na dĺžku x 1 + x 2 vektor c = (1,1) 4 3 2 1 1 2 3 4

Geometrické interpretačné vektory: smer, dĺžka, náklady x 1 + x 2 vektor c = (1,1) rovnica x 1 + 2x 2 = 3 vektor a = (1,2) 4 3 2 1 1 2 3 4

Geometrické interpretačné vektory: smer, dĺžka, náklady x 1 + x 2 vektor c = (1,1) rovnica x 1 + 2x 2 = 3 vektor a = (1,2) 4 x 2 = ½ (3-x 1) 3 2 1 1 2 3 4

Geometrické interpretačné vektory: smer, dĺžka, náklady x 1 + x 2 vektor c = (1,1) rovnica x 1 + 2x 2 = 3 vektor a = (1,2) 4 3 2 1 x 1 + 2x 2 = 4 1 2 3 4

Vektory geometrickej interpretácie: smer, náklady na dĺžku x 1 + x 2 vektor c = (1,1) rovnica x 1 + 2x 2 = 3 vektor a = (1,2) 4 3 2 1 nadrovina, všeobecne, n-1 rozmerná 1 2 3 4

Geometrické interpretačné vektory: smer, dĺžka, náklady x 1 + x 2 vektor c = (1,1) rovnica x 1 + 2x 2 = 3 vektor a = (1,2) 4 3 nerovnosť x 1 + 2x 2 3? 2 1 polopriestor, všeobecný, n-rozmerný 1 2 3 4

Geometrické interpretačné vektory: smer, dĺžka, náklady x 1 + x 2 vektor c = (1,1) rovnica x 1 + 2x 2 = 3 vektor 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 mnohosten, všeobecne, 1 2 3 4 optimálne riešenie (1, 1), hodnota 2

Intermezzo Interactive CPLEX: LP1

Riešením lineárneho programovania v poslednom príklade bolo celé číslo! Čo ak nie, ale vyžaduje sa celé číslo?

Integer Linear Programming ILP: integer of the solution required (discrete) Mixed ILP: If only for some xi integers 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 Interaktívny CPLEX: LP2 1 2 3 4

Integer Linear Programming ILP: integer of the solution required (discrete) Mixed ILP: If only for some xi integers 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 Optimálne riešenie (4,5, 4), hodnota 8,5

Integer Linear Programming ILP: integer solution required (discrete) Mixed ILP: If only for some xi integers separate invalid solution 4 Generate x 1 Cut 4 x 1 5 max x 1 + x 2 3 2 or branch sto 14 x 1-18x 2 -9 2x 1-2 x 2 1 x 1, x 2 0 1 x 1, x 2 celé číslo Najprv vypočítajte relaxáciu 1 2 3 4

Integer Linear Programming ILP: integer solution required (discrete) Mixed ILP: If only for a few xi integers Interactive CPLEX: 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 integer optimálne riešenie (2, 2), hodnota 4 1 2 3 4

Integer Linear Programming ILP je NP-úplné, dokonca aj v špeciálnom prípade x i Sila formulácie: Oveľa dôležitejšie ako pri LP! Počet premenných a obmedzení tu nie je rozhodujúci, ale to, ako presne obmedzenia popisujú konvexný trup platných celočíselných riešení!

B&C & P (some) Solver/Frameworks COIN-OR LP (M) ILP CPlex CPlex SCIP SoPlex Abacus BCP Symphony CBC OSI CLP drahý, ale najrýchlejší slobodný softvér a oveľa viac.

TSP: Formulácia (1) Zadané: Hľadané: n miest: S = vzdialenosti medzi mestami: d (a, b) Najkratšia okružná cesta cez všetky mestá Premenné: xv, wv, w S Cieľová funkcia: min d (v, w) xv, wv, w p

TSP: Formulácia (2) Premenné: xv, wv, w S Cieľová funkcia: min d (v, w) xv, w Obmedzenia: v, w S w S xv, w = 2 v S v T w T xv, w 2 TS exponenciálne veľa!

Dokončili ste všetky čiastkové problémy? TSP: Metódy riešenia Vypočítajte heuristiku: horná hranica O Podproblém 1. Vyriešte PL (polynóm, CPLEX) Začnite s jednoduchším lineárnym programom P min v, w S 0 xv, w 1 d (v, w) xv, wv, w S 2. Skutočná L platné? O min (o, L)! 3. Je L O? Ukončiť podproblém. 4. Heuristika založená na L prípadne nová O 5. Nájsť porušenú nerovnosť (*)? Pridajte do P & choďte na 1. O je optimálne w S x v, w = 2 v S subproblém x v, w = 0 subproblem x v, w = 1 x v, w 2 T S (*) v T w T

SCIP: Prehľad SCIP = Riešenie celočíselných programov s obmedzeniami http://scip.zib.de, Doxygen-Docs (veľmi dobré a užitočné) @home: stiahnuť, kompilovať pomocou (predvolené: gcc, linux) urobiť LPS =? READLINE = false ZLIB = false ZIMPL = false spx (SoPlex), clp (CLP) @uni: nainštalovaný a kompilovaný (LPS = cpx/CPlex) v /home/plug/scip-1.1.0 Príklady: TSP, VRP,/home/plug /scip-1.1.0/examples/

TSP so SCIP: (Niektoré) dôležité súbory Základné súbory mymain.cpp main () Nastavenie štruktúr SCIP Registrácia doplnkov (čítačka, separácia, heuristika, ceny,) myreader.h myreader.cpp mysubtour.h mysubtour.cpp Čítanie problému Vytvorenie počiatočnej separácie LP obmedzení obrysu

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, nový MyReader (scip), TRUE)); SCIP_CALL (SCIPincludeObjConshdlr (scip, new MySubtour (), TRUE)); SCIP_CALL (SCIPincludeDefaultPlugins (scip)); SCIP_CALL (SCIPprocessShellArguments (scip, argc, argv, "parameter.txt")); SCIP_CALL (SCIPfree (& scip)); vrátiť 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) návrat ret; SCIPprocessShellArgumenty. SCIPsolve (scip);.

TSP so SCIP: (Niektoré) dôležité súbory Základné súbory mymain.cpp myreader.h myreader.cpp main () Nastavenie štruktúr SCIP Registrácia doplnkov (čítačka, separácia, heuristika, cena), Čítanie problému Vytvorenie počiatočného LP mysubtour. h mysubtour.cpp Oddelenie obmedzení obrysu

MyReader () <> virtuálny SCIP_RETCODE scip_free (SCIP * scip, SCIP_READER * čítačka) < return SCIP_OKAY; >virtuálny SCIP_RETCODE scip_write (. SCIP_RESULT * výsledok) < >* výsledok = SCIP_DIDNOTRUN; vrátiť SCIP_OKAY; >; virtuálny SCIP_RETCODE scip_read (SCIP * scip, SCIP_READER * čítačka, const char * názov súboru, SCIP_RESULT * výsledok);

myreader.cpp #include "myprobdata.h" // trieda MyProbData: public scip: objprobdata; SCIP_RETCODE MyReader: scip_read (SCIP * scip, SCIP_READER * čítačka, const char * názov súboru, SCIP_RESULT * výsledok) < *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; názov reťazcového prúdu; meno id; SCIP_CALL (SCIPcreateVar (scip, & var, name.str (). C_str (), 0, 1, edge-> dĺžka, SCIP_VARTYPE_BINARY, TRUE, FALSE, NULL, NULL, NULL, NULL)); edge-> zodpovedajúcevar = var; SCIP_CALL (SCIPaddVar (scip, var)); > *** ďalšia snímka tu: pridajte obmedzenia *** * result = SCIP_SUCCESS; vrátiť SCIP_OKAY; 0, 1, okraj-> dĺžka dolná hranica: 0, horná hranica: 1, koeficient v objektívnej funkcii

myreader.cpp // pridať obmedzenia stupňa pre (všetky uzly uzlov grafu) < 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->zodpovedajúci var, 1,0)); 0, NULL, NULL 0 premenných, prázdne pole pre premenné, prázdne pole pre koeficienty> SCIP_CALL (SCIPaddCons (scip, proti)); SCIP_CALL (SCIPreleaseCons (scip, & proti)); // pridať obsluhu obmedzenia obrysu SCIP_CONS * proti; SCIP_CONSDATA * consdata; SCIP_CALL (SCIPallocMemory (scip, & consdata)); consdata-> graf = graf; SCIP_CALL (SCIPcreateCons (scip, cons, name, SCIPfindConshdlr (scip, "subtour"), consdata, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE)); SCIP_CALL (SCIPaddCons (scip, proti)); SCIP_CALL (SCIPreleaseCons (scip, & proti)); 2,0, 2,0 ľavé a pravé obmedzenie 2.0 obmedzenie 2.0

MySubtour () <> // je riešenie platné? virtuálny SCIP_RETCODE scip_check (. SCIP_SOL * sol.); virtuálny SCIP_RETCODE scip_enfolp (.); lp = čiastkové riešenie virtuálneho SCIP_RETCODE scip_enfops (.); ps = pseudo riešenie enfo = vynútiť // zaokrúhľovanie dôsledkov obmedzení virtuálny SCIP_RETCODE scip_lock (.); Pre platnosť // samostatný virtuálny SCIP_RETCODE scip_sepalp (.); virtuálny SCIP_RETCODE scip_sepasol (. SCIP_SOL * sol.); >; Pre rýchlosť (*), (**) väčšinou identické alebo veľmi podobné implementácie