PG 534 Járműútvonalak bemutatása

PG 534 Jármű-útválasztás Bevezetés Markus Chimani és Karsten Klein LS11, TU Dortmund

PG Objectives Framework Branch & Cut, Branch & Price, választható célfüggvények, kényszerek, heurisztika, egyenlőtlenségek, szétválasztási módszerek stb. Kísérleti tanulmány gyakorlati adatokkal is

Az alapok áttekintése: Kis példák LP és ILP megoldási módszerek Megoldó/keretrendszer Nagy példa TSP: megfogalmazás, vágások SCIP: Alapok SCIP kód TSP szervezeti fiókokhoz, webszerverekhez stb.

Lineáris programozás Optimalizálási probléma megfogalmazása változó vektorral x = (x 1, xn) keresztül: Lineáris költségfüggvény költségvektorral c = (c 1. cn) min i = 1.ncixi (szintén max) Lineáris (be) egyenletek korlátozásként i = 1.naixib (is,) speciális formák: xi 0 vektor x, amely minden feltételnek megfelel: érvényes megoldási vektor x * cx-szel * cx érvényes x: optimális megoldás

Lineáris program Kiírva: min/max c 1 x 1 +. + c n x n sto a 11 x 1 +. + a 1n x n b 1. Szabványos forma: a m1 x 1 +. + a mn x n b m x i korlátlan változó, vagy x i 0 eredetileg transzformált célfüggvény max cx min -cx egyenlet a j x b j a j x + s = b j, s 0 korlátlan változó x i x i + x i - x i +, x i- 0

Lineáris program kompakt jelölés A mátrixszal R m, n, b R m, c, x R n vektorok: min

Példa: xi étrendprobléma: Különböző ételek bi: Ideális tápanyagellátás (pl. Vitaminok) ci: Élelmiszer költsége Tárgy: A legolcsóbb étrend elegendő élelmiszerellátással Fűtőérték/kcal C-vitamin/mg Ár/kenyér (500g) 1230 0 2,99 Narancslé ( 1l) 560 300 2,50 Szükséglet: 2000 60. perc 2,99x 1 + 2,50x 2 sto 1230x 1 + 560x 2 2000 300x 2 60 x 1, x 2 0

Lineáris programozási komplexitás: a lineáris optimalizálási problémák megoldhatók polinom időben. Módszerek: Belső pontok módszer Ellipszoid módszer Simplex módszer (legrosszabb esetben exponenciális)

Geometriai értelmezési vektorok: irány, hosszköltségek x 1 + x 2 vektor c = (1,1) 4 3 2 1 1 2 3 4

Geometriai értelmezési vektorok: irány, hosszköltségek x 1 + x 2 vektor c = (1,1) egyenlet x 1 + 2x 2 = 3 vektor a = (1,2) 4 3 2 1 1 2 3 4

Geometriai értelmezési vektorok: irány, hosszköltségek x 1 + x 2 vektor c = (1,1) egyenlet x 1 + 2x 2 = 3 vektor a = (1,2) 4 x 2 = ½ (3-x 1) 3 2 1 1 2 3 4

Geometriai értelmezési vektorok: irány, hosszköltségek x 1 + x 2 vektor c = (1,1) egyenlet x 1 + 2x 2 = 3 vektor a = (1,2) 4 3 2 1 x 1 + 2x 2 = 4 1 2 3 4

Geometriai értelmezési vektorok: irány, hosszköltségek x 1 + x 2 vektor c = (1,1) egyenlet x 1 + 2x 2 = 3 vektor a = (1,2) 4 3 2 1 hipersík, általános, n-1 dimenziós 1 2 3 4

Geometriai értelmezési vektorok: irány, hosszköltségek x 1 + x 2 vektor c = (1,1) egyenlet x 1 + 2x 2 = 3 vektor a = (1,2) 4 3 egyenlőtlenség x 1 + 2x 2 3? 2 1 féltér, általános, n-dimenziós 1 2 3 4

Geometriai értelmezési vektorok: irány, hosszköltségek x 1 + x 2 vektor c = (1,1) egyenlet 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 poliéder, általános, 1 2 3 4 optimális megoldás (1, 1), 2. érték

Intermezzo Interactive CPLEX: LP1

Az utolsó példában a lineáris programozási megoldás egész szám volt! Mi van, ha nem, de egész szám szükséges?

Egész lineáris programozási ILP: a szükséges megoldás egész száma (diszkrét) Vegyes ILP: Ha csak néhány xi egész számra 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ív CPLEX: LP2 1 2 3 4

Egész lineáris programozási ILP: a szükséges megoldás egész száma (diszkrét) Vegyes ILP: Ha csak néhány xi egész számra 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ális megoldás (4.5, 4), értéke 8.5

Egész lineáris programozási ILP: egész megoldás szükséges (diszkrét) Vegyes ILP: Ha csak néhány xi egész számra külön külön érvénytelen megoldás 4 Generál x 1 Vág 4 x 1 5 max x 1 + x 2 3 2 vagy elágazás 14 x 1-18x 2 -9 2x 1-2 x 2 1 x 1, x 2 0 1 x 1, x 2 egész szám Először a relaxáció kiszámítása 1 2 3 4

Egész lineáris programozási ILP: egész megoldás szükséges (diszkrét) Vegyes ILP: Ha csak néhány xi egész számra Interaktív 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 egész szám optimális megoldás (2, 2), értéke 4 1 2 3 4

Integer Lineáris Programozás Az ILP NP-teljes, még az x i speciális esetben is. A készítmény erőssége: Sokkal fontosabb, mint az LP-vel! A változók és a kényszerek száma itt nem meghatározó, de hogy a korlátozások pontosan leírják-e az érvényes egész megoldások konvex héját!

B&C & P (néhány) Megoldó/Keretrendszer COIN-OR LP (M) ILP CPlex CPlex SCIP SoPlex Abacus BCP Symphony CBC OSI CLP drága, de a leggyorsabb ingyenes szoftver és még sok más.

TSP: Megfogalmazás (1) Adva: Keresett: n város: S = városok közötti távolság: d (a, b) Rövidebb oda-vissza út az összes városon Változók: xv, wv, w S Célfüggvény: min d (v, w) xv, wv, w p

TSP: Formuláció (2) Változók: xv, wv, w S Célfüggvény: min d (v, w) xv, w Korlátozások: v, w S w S xv, w = 2 v S v T w T xv, w 2 TS exponenciálisan sok!

Befejezte az összes részproblémát? TSP: Megoldási módszerek Heurisztika kiszámítása: felső határ O Oprobléma 1. Oldja meg a PL-t (polinom, CPLEX) Indítsa el egy egyszerűbb lineáris programmal: P min v, w S 0 xv, w 1 d (v, w) xv, wv, w S 2. L érvényes? O perc (o, L)! 3. L O? Alprobléma befejezése. 4. Heurisztika L esetleg új O alapján 5. Megtalálja a megsértett egyenlőtlenséget (*)? Adja hozzá a P-hez és ugorjon az 1. O értékre: optimális w S x v, w = 2 v S részprobléma x v, w = 0 részprobléma x v, w = 1 x v, w 2 T S (*) v T w T

SCIP: Áttekintés SCIP = Constraint Integer Programs megoldása http://scip.zib.de, Doxygen-Docs (nagyon jó és hasznos) @home: letöltés, fordítás via (alapértelmezett: gcc, linux) make LPS =? READLINE = hamis ZLIB = hamis ZIMPL = hamis spx (SoPlex), clp (CLP) @uni: telepítve és lefordítva (LPS = cpx/CPlex) a /home/plug/scip-1.1.0 könyvtárban. Példák: TSP, VRP,/home/plug /scip-1.1.0/examples/

TSP SCIP-vel: (Néhány) fontos fájl Alapvető fájlok mymain.cpp main () SCIP struktúrák beállítása A beépülő modulok regisztrálása (olvasó, elválasztás, heurisztika, árképzés) myreader.h myreader.cpp mysubtour.h mysubtour.cpp A probléma olvasása A kezdeti LP létrehozása A subtour korlátok szétválasztása

mymain.cpp #include #include "objscip/objscip.h" #include "objscip/objscipdefplugins.h" #include "myreader.h" #include "mysubtour.h" SCIP_RETCODE runcip (int argc, char ** argv) < >SCIP * scip = NULL; SCIP_CALL (SCIPcreate (& scip)); SCIP_CALL (SCIPincludeObjReader (scip, új MyReader (scip), IGAZ)); SCIP_CALL (SCIPincludeObjConshdlr (scip, új MySubtour (), IGAZ)); SCIP_CALL (SCIPincludeDefaultPlugins (scip)); SCIP_CALL (SCIPprocessShellArguments (scip, argc, argv, "parameter.txt")); SCIP_CALL (SCIPfree (& scip)); visszatérés SCIP_OKAY; int main (int argc, char ** argv) < >SCIP_RETCODE retcode = runcip (argc, argv); if (újrakódolás! = SCIP_OKAY) SCIPprintError (újrakódolás, stderr); SCIP_CALL (. ()); SCIP_RETCODE ret =. (); if (ret! = SCIP_OKAY) visszatér ret; SCIPprocessShellArguments. SCIPsolve (scip);.

TSP SCIP-vel: (Néhány) fontos fájl Alapvető fájlok mymain.cpp myreader.h myreader.cpp main () Az SCIP struktúrák beállítása A plug-inek regisztrálása (olvasó, elválasztás, heurisztika, pricer,) Olvasás a problémában A kezdeti LP mysubtour létrehozása. h mysubtour.cpp A részturisztikai korlátok elválasztása

MyReader () <> virtuális SCIP_RETCODE scip_free (SCIP * scip, SCIP_READER * olvasó) < return SCIP_OKAY; >virtuális SCIP_RETCODE scip_write (. SCIP_RESULT * eredmény) < >* eredmény = SCIP_DIDNOTRUN; visszatérés SCIP_OKAY; >; virtuális SCIP_RETCODE scip_read (SCIP * scip, SCIP_READER * olvasó, const char * fájlnév, SCIP_RESULT * eredmény);

myreader.cpp #include "myprobdata.h" // class MyProbData: public scip: objprobdata; SCIP_RETCODE MyReader: scip_read (SCIP * scip, SCIP_READER * olvasó, const char * fájlnév, SCIP_RESULT * eredmény) < *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; stringstream név; név azonosítója; SCIP_CALL (SCIPcreateVar (scip, & var, name.str (). C_str (), 0, 1, edge-> length, SCIP_VARTYPE_BINARY, TRUE, FALSE, NULL, NULL, NULL, NULL); él-> megfelelővar = var; SCIP_CALL (SCIPaddVar (scip, var)); > *** következő dia itt: korlátozások hozzáadása *** * eredmény = SCIP_SIKER; visszatérés SCIP_OKAY; 0, 1, él-> hossz alsó határ: 0, felső határ: 1, együttható a célfüggvényben

myreader.cpp // fokkorlátozások hozzáadása (a gráf összes csomópontja) < 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->megfelelővar, 1,0)); 0, NULL, NULL 0 változó, üres tömb a változókhoz, üres tömb az együtthatókhoz> SCIP_CALL (SCIPaddCons (scip, cons)); SCIP_CALL (SCIPreleaseCons (scip, & cons)); // subtour kényszerkezelő hozzáadása SCIP_CONS * hátrányok; SCIP_CONSDATA * consdata; SCIP_CALL (SCIPallocMemory (scip, & consdata)); consdata-> gráf = gráf; SCIP_CALL (SCIPcreateCons (scip, cons, name, SCIPfindConshdlr (scip, "subtour"), consdata, FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE, FALSE); SCIP_CALL (SCIPaddCons (scip, cons)); SCIP_CALL (SCIPreleaseCons (scip, & cons)); 2.0, 2.0 bal és jobb határok 2.0 kényszer 2.0

TSP SCIP-vel: (Néhány) fontos fájl Alapvető fájlok mymain.cpp main () SCIP struktúrák beállítása A plug-inek regisztrálása (olvasó, elválasztás, heurisztika, árképzés) myreader.h myreader.cpp mysubtour.h mysubtour.cpp A probléma olvasása A kezdeti LP létrehozása A subtour korlátok szétválasztása

A MySubtour () <> // érvényes megoldás? virtuális SCIP_RETCODE scip_check (. SCIP_SOL * sol.); virtuális SCIP_RETCODE scip_enfolp (.); lp = tört megoldás virtuális SCIP_RETCODE scip_enfops (.); ps = pszeudo megoldás enfo = kényszerítés // a kényszerek kerekítésének lekerekítése virtuális SCIP_RETCODE scip_lock (.); Érvényességhez // külön virtuális SCIP_RETCODE scip_sepalp (.); virtuális SCIP_RETCODE scip_sepasol (. SCIP_SOL * sol.); >; A sebességhez (*), (**) többnyire azonos vagy nagyon hasonló megvalósítások