MTA DOKTORA ÉRTEKEZÉS TÉZISEI
Computational Techniques of the Simplex Method
Írta: Maros István
Budapest, 2004
1. fejezet Az értekezés célkituzései, ˝ tudományos el˝ozmények A benyújtott értekezés egy kutatási monográfia, amely a Kluwer Academic Publishers kiadásában jelent meg „Computational Techniques of the Simplex Method” címmel 2003-ban [26]. A könyv a címben megjelölt témakör átfogó tárgyalását adja, amely a szerz˝o idevágó saját tudományos eredményein kívül tartalmazza mások hozzájárulását is. Az új eredmények felsorolásánál (jelen tézisek 3. fejezete) természetesen csak a saját eredmények szerepelnek. Az értekezés f˝o célja olyan algoritmusok és algoritmikus technikák kidolgozása, amelyek lehet˝ové teszik igen nagyméret˝u és nehéz lineáris programozási feladatok megbízható és hatékony megoldását a szimplex módszer segítségével. A lineáris programozási feladatok megoldására el˝oször Dantzig adott a gyakorlatban is használható algoritmust, amely a szimplex módszer néven vált ismertté 1951-ben [4]. Ez valójában egy algoritmus család, amelynek számos konkrét realizációját lehet elkészíteni. Ezek közös tulajdonsága, hogy a nagy számításigény miatt csak számítógépre kidolgozott implementációjuk alkalmas a triviálisnál nagyobb méret˝u feladatok megoldására. Ma már történelmi tény, hogy a számítógépek fejl˝odését a korai id˝oszakban a lineáris programozás (LP) igényei er˝osen motiválták. Általánosan elfogadott nézet szerint még az 1980-as évek elején is — nemzetközi szinten — a gépid˝o 40 százalékában LP feladatok megoldása folyt. Miután Dantzig módszere a ciklizálás elkerülésére kidolgozott elméleti eljárás után elvileg bármilyen LP feladat megoldására képes, világos, hogy a szimplex módszer további fejl˝odését els˝osorban a magasszint˝u gyakorlati igények vezérelték. Ennek a tevékenységnek a során azonban igen szép elméleti eredmények, új algoritmusok és algoritmikus technikák születtek. Jelen tézisek szerz˝oje 1970-t˝ol kapcsolódott be ebbe a kutatómunkába és elért eredményei
1
M AROS
Doktori tézisek
2 of 18
alapján 1981-ben kandidátusi fokozatot szerzett. A szakmai közvélemény ekkorra a szimplex módszert érettnek tekintette és a kutatás intenzitása egy id˝ore alábbhagyott. Az 1980-as évek második felében azonban két lényeges dolog történt. Egyrészt, megjelentek a gyakorlatilag is hatékony bels˝opontos algoritmusok, másrészt tért hódítottak az egyre jobb és nagyobb kapacitású személyi számítógépek. Ezzel egyidej˝uleg fontos új alkalmazási területek egyre nagyobb és bonyolultabb LP feladatokkal álltak el˝o. A kevert egészérték˝u problémák (MIP) megoldásához LP feladatok sorozatos megoldásán keresztül vezet az út. Itt els˝osorban az LP megoldások sebessége és megbízhatósága a követelmény. Nagyméret˝u LP feladatoknak gyakran van jól definiált struktúrája, f˝oleg azoknak, amelyek dinamikus vagy térben elosztott rendszereket reprezentálnak, illetve amelyek a bizonytalanságot modellezik (sztochasztikus programozás). Az ezeknél használatos dekompozíciós eljárások is LP feladatok sokaságának megoldását igénylik. Ezek mellett sorra jelentek meg az „igazi”, nem dekomponálható hatalmas méret˝u feladatok, els˝osorban az ipari alkalmazásoknál, de olyan újabb területeken is, mint például távközlés és pénzügyi számítások. Mindezek együttes hatásaként, de els˝osorban a bels˝opontosokkal való verseny és a MIP feladatok miatt, felélénkült a kutatási tevékenység a szimplex módszer körül. Egy sikeresen m˝uköd˝o számítógépes optimalizáló rendszer receptje viszonylag egyszer˝u: jó algoritmust kell jól implementálni. Mindezt elérni viszont már korántsem ilyen egyszer˝u. Az implementációs technológia tele van komoly elméleti meggondolásokkal és eredményes m˝uvelése több tudományterület tevékeny ismeretét igényli. Ebben rejlik a nagy kihívás. A szerz˝o érdekl˝odését hamar felkeltették a személyi számítógépekben (PC-kben, vagy ahogy eleinte hívták: mikro számítógépekben) rejl˝o potenciális lehet˝oségek az LP szempontjából. Korábbi implementációs ismereteit felhasználva, kidolgozott egy MILP nev˝u, PC-n m˝uköd˝o szimplex alapú LP rendszert. Ennek a munkának sok következménye lett, amelyek b˝o forrása volt a megvalósítás során szerzett rengeteg tapasztalat. Egy Bokor Józseffel közös cikkben az Alkalmazott Matematikai Lapokban áttekintették a PC-k szerepét az operációkutatásban [27]. Megállapításaikat a kés˝obbi események szépen igazolták. 1988-ban a MILP részt vett egy nagy nemzetközi összehasonlító vizsgálatban és egy professzionális rendszer (XPRESS-LP) mögött a második legjobbnak bizonyult, megel˝ozve a többi kereskedelmi és egyetemi kutatási programcsomagot [36; 35]. MILP felkerült különféle listákra és a róla szóló kutatási beszámolókat [16; 17; 18] több helyen (köztük a Mathematical Reviewsban) is idézték. A MILP-en végzett kutatás-fejlesztés mintegy „mellékterméke”-ként a szerz˝o elkészítette a MINET jel˝u hálózati szimplex programrendszerét, amely résztvett a DIMACS és az American Mathematical Society által 1992-ben rendezett International Implementation Challenge-en és
2004.2.11
M AROS
Doktori tézisek
3 of 18
ott szignifikánsan jobbnak bizonyult, mint az akkor legjobbnak tartott NETFLO program [20]. A fenti sikerek több összetev˝onek voltak köszönhet˝ok. Ebben az id˝oben a szerz˝o a szimplex iteráció két mozzanatát vizsgálta: a belép˝o változó megválasztását (pricing) és a degeneráció elleni stratégiákat. El˝oször a hálózati szimplex esetére dolgozott ki 1991-ben egy olyan általános pricing eljárást [19], amely az addig ismert eljárásokat speciális esetként tartalmazta, ugyanakkor lehet˝oséget teremtett tetsz˝oleges, akár a hálózat struktúráját is figyelembevev˝o új kiválasztási stratégiák megvalósítására. Ezt az eljárást kés˝obb MILP-ben is adaptálta, amelyr˝ol a publikáció azonban csak 2003-ban jelent meg önállóan [23] és a jelen tézisek alapját szolgáló monográfiában [26] is. Ez utóbbiban SIMPRI néven szerepel. A módszer 1995-ben beépült a Mitra által vezetett kutatócsoportnál kidolgozott FortMP [28] programcsomagba is. A degeneráció káros hatásának kiküszöbölésére tett er˝ofeszítések általában a kilép˝o vektor (pivot sor) meghatározására koncentráltak, mint például Gal és Geue [7] 1986-ban, valamint Gill és társai [8] 1989-ben. A szerz˝o, Greenberg [11] korábbi gondolataihoz kapcsolódva, azt vizsgálta, hogy lehet eleve olyan belép˝o vektorokat felismerni, amelyek jobb esélyt jelentenek nem-degenerált iterációk végzésére. Az 1986-ban publikált eredmény [14] negatív, vagyis azokat a vektorokat könnyebb jellemezni amelyekkel csak degenerált lépést lehet megtenni. Ez az ismeret azonban jól hasznosítható, mert amíg van más választás, addig ezeket az oszlopokat el lehet kerülni, mégpedig viszonylag elviselhet˝o számítási többletmunka árán. A hálózati szimplex módszernél viszont a szerz˝o alkalmazott el˝oször degeneráció ellenes kilép˝o eljárást 1993ban [21], ami különösen az els˝o fázisban bizonyult nagyon hatásosnak, lényegében számítási többletmunka nélkül. Ez egy fontos tényez˝o volt a MINET sikeres szereplésében a DIMACS Challenge-en. Ezt követ˝oen a szerz˝o az általános szimplex számára kidolgozott ismert degeneráció ellenes pivot meghatározó eljárásokat vetette vizsgálat alá, majd sorra helyezte azokat általános környezetbe és eszközölt javításokat rajtuk. Ezek: Wolfe nagyon fontos, noha többnyire figyelmen kívül hagyott ad hoc módszere 1963-ból [37], Benichou és társai perturbációs módszere 1977-ben az IBM MPSX rendszerben [1], valamint Gill és társai EXPAND eljárása 1989-ben [8]. Mindezek a javítások az értekezésben vannak publikálva el˝oször. A szerz˝o 1993 és 1996 között Mitra-val dolgozott a fentebb már idézett ForMP programrendszer fejlesztésén. Ennek keretén belül került sor az induló bázist meghatározó eljárások revíziójára. Egy valamilyen szempontból jó kezd˝o megoldás jelent˝osége igen nagy, hiszen az kihatással van a megoldás hatékonyságára. Érdekes módon Orchard-Hays (1968) [34] óta sokáig nem történt lényeges el˝orelépés ezen a területen. S˝ot, Gould és Reid 1989-as, egyébként szépen átgondolt munkája [10] is visszhang nélkül maradt és nem ismeretes, hogy valahol is használnák. Bixby 1993-ben publikálta a CPLEX programcsomagban alkalmazott induló el-
2004.2.11
M AROS
Doktori tézisek
4 of 18
járást, ami máig is szinte az egyetlen részlet, amit err˝ol a programcsomagról tudni lehet. Maros kidolgozott egy szimbolikus triangularizáción alapuló eljárás családot, amit Mitrával több közös publikációban közölt [30; 31; 33]. A módszer lényege egy lehet˝o legnagyobb és ugyanakkor legmegengedettebb, struktúrális oszlopokból álló trianguláris bázis megtalálása. Már az eljárás legegyszer˝ubb változata is hatásosságban felülmúlta a CPLEX bázist. Maros [33]-ben az eljárás család egy másik lehetséges tagját is kidolgozta, amikoris a triangularitáson kívül a degeneráltság csökkentése a cél. A társszerz˝o hozzájárulása ezekhez a cikkekhez egy successive overrelaxation (SOR) elven alapuló iteratív eljárás, ami numerikusan nehéz feladatok esetén kecsegtet sikerrel egy induló bázis meghatározására. Az 1990-es évek elején a szerz˝o több ízben beszélgetett Terlaky Tamással a duál szimplex módszerr˝ol és közösen úgy találták, hogy az el van maradva a primál mögött kidolgozottság és hatásosság szempontjából. Ez a nézet tovább er˝osödött a FortMP munka kezdeti id˝oszakában amikor a kevert egészérték˝u feladatok Branch-and-Bound (B&B) módszerrel történ˝o megoldó algoritmusának megtervezése és implementálása került napirendre. A szimplex módszer egyik leger˝osebb oldala a warm start képesség (indulás tetsz˝oleges bázisról) ami primálra és duálra egyaránt igaz. B&B esetén az egy csomópontban megoldott feladat (node problem) optimális bázisa duál megengedett bázis a két al-feladat (subproblem) számára, így err˝ol indulva rögtön duál második fázissal lehet az al-feladatokat megoldani. Miután ezek csak nagyon kicsit különböznek az aktuális csomóponti feladattól, várhatóan kevés iterációt kell elvégezni, ha a duál módszerrel oldjuk meg a feladatot. A primál módszer használata esetén erre nem lehet számítani, mert ekkor a számítások az els˝o fázisban kezd˝odnek. A megoldandó feladatok jellemz˝oje, hogy — az integritás relaxációja miatt — általában nagyon sok egyedi fels˝okorlátos változó van bennük. A megoldásra akkoriban a Chvatal által publikált [3] fels˝okorlátos duál algoritmust használták. Miután ez elég jól m˝uködött, sokáig nem látszott fontosnak egy új duál második fázis algoritmus kidolgozása. Fourer 1994-es keltezés˝u nem publikált megjegyzései a duálról továbblépést jelentettek volna a Chvatal platformról, de azok kidolgozatlanok voltak és a matematikai programozó közösségnek hosszú ideig nem is volt tudomása róluk. Jelen értekezés szerz˝oje alapos vizsgálatnak vetette alá a duált és el˝oször a Chvatal változaton egy kisebb általánosítást hajtott végre (Dual-G [26]-ban), hogy az bármilyen típusú változó esetén helyesen m˝uködjön. Ezt követ˝oen kidolgozott egy olyan új duál algoritmust (BSD [24]ben, illetve Dual-GX [26]-ban), amely a „drágán” el˝oállított transzformált pivot sor többszörös felhasználásán alapul. Ez nemcsak tetsz˝oleges típusú változókat tud algoritmikusan kezelni, hanem minden egyes iterációban a lehet˝o legnagyobb célfüggvény javulást éri el, ami az el˝ozetesen kiválasztott kilép˝o változó esetén egyáltalán lehetséges. Az algoritmusnak, amellett, hogy
2004.2.11
M AROS
Doktori tézisek
5 of 18
rendkívül hatásosan képes m˝uködni, van néhány egyéb kedvez˝o tulajdonsága: igen eredményes tud lenni duál degenerált bázisok esetén és nagyobb numerikus stabilitást tud biztosítani a flexibilis pivot választási lehet˝oségnek köszönhet˝oen. Az iterációnkénti többletmunka nem jelent˝os, ha a helyzethez hangolt transzformáló, rendez˝o és listakezel˝o algoritmusokat használunk az implementáció során. Az idézett publikációkban, de f˝oleg az értekezésben ezek az eljárások pontosan specifikálva vannak. Mindezek alapján az új algoritmus eredményesen használható nemcsak a B&B-n belül, hanem általánosan is, amennyiben ismeretes egy duál megengedett bázis. Nemzetközi fórumon el˝oször az 1996 márciusában Mátraházán tartott XIII International Conference on Mathematical Programming találkozón ismertette a szerz˝o az BFD els˝o változatát, ami a B&B-re volt „kihegyezve”, és ami 1998-ban jelent meg a konferencia proceedingsben [22]. A kés˝obbi változatok több fórum elé kerültek és jelentek meg Research Report-ként miel˝ott a szerz˝o publikálta a legutolsó változatot 2003-ban [24], ami az értekezésben is szerepel. Az új duál második fázis eljárás nagy érdekl˝odést váltott ki és nemcsak FortMP-be és a MILP utódjaként létez˝o HIPLEX-be épült be, hanem, a sok email megkeresés tanúsága szerint, jó néhány egyetemi kutatási programba is. A fejleszt˝ok minden esetben igen sikeresnek találták az algoritmust. Közvetett információk szerint a kereskedelmi rendszerek közül is többen átvették ezt az eljárást. Dual-GX sikere kapcsán felmerült a kérdés, lehet-e hasonlóan hatásos duál els˝o fázist kidolgozni egy duál megengedett megoldás megkeresésére? Ez esetben ugyanis a duált a primállal szemben egy teljes érték˝u, vagy annál akár jobb alternatív algoritmusként lehetne használni tetsz˝oleges típusú feladat esetén. A duál els˝o fázis vizsgálatának a kiindulási pontja ugyanaz volt mint a duál második fázisé: maximálisan kihasználni a drágán meghatározott transzformált pivot sort. Ez el˝ott viszont még azt is tisztázni kellett, hogy az általánosan felírt feladat esetén mi jellemzi azokat a kilép˝o jelölteket, amelyekkel a duál megengedettség irányába lehet lépni. Több lehet˝oség végiggondolása után a szerz˝o kidolgozta a GDPO (General Dual Phase One) algoritmusát, ami az összes felvetésre pozitív választ ad és f˝obb jellemz˝oi hasonlítanak Dual-GX-re. GDPO minden iterációban a kiválasztott kilép˝o változóval a lehet˝o legnagyobb el˝orehaladást teszi meg a duál megengedettség felé. Ez persze nem jelenti azt, hogy esetleg egy másik kilép˝o esetén nem tudna nagyobb javulást elérni. Éppen ezért fontos egy jó kilép˝o változó meghatározása, ami az ismert normalizáló pricing módszerekkel érhet˝o el. GDPO is hatásos tud lenni duál degeneráció, illetve numerikusan nehéz feladatok esetén. Lényeges különbség Dual-GX és GDPO között az, hogy míg az el˝obbi el˝onyös tulajdonságai akkor mutatkoznak meg látványosan, ha a feladatban
2004.2.11
M AROS
Doktori tézisek
6 of 18
sok egyedi korlátos változó van, addig az utóbbinál ezek akkor jelentkeznek, ha a hagyományos nem-negatív és szabad változókból van sok. GDPO els˝o változatai 1998-ban kezdtek m˝uködni és a legutolsó változatot a szerz˝o 2003-ban publikálta [25]. Az értekezésben lev˝o változat az utolsó el˝otti és csak annyival kevesebb, hogy nem tartalmazza a duál els˝o fázisú árnyékárak transzformációjának opcióját, ami bizonyos körülmények közt el˝onyösebb lehet, mint az újraszámolás. A GDPO-vel elvégzett kisebb számítási tanulmány [25] jó egyezést mutat az elméleti elvárásokkal. Az eddig ismertetett „f˝o csapás” mellett a szerz˝o az algoritmusok számítógépes implementációjának számos egyéb elemét is vizsgálta. A matematikai programozási algoritmusok implementációjának követelményeit el˝oször egy Mitra-val közös cikkben tárgyalta [31], amit aztán PhD hallgatójával, Khaliq-kal együtt kib˝ovített és megfogalmazta az optimalizációs software implementációs technológiájának alapjait. Ez volt a XVII EURO konferencián 2000-ben elhangzott semi-plenary el˝oadásának a témája, ami cikk formában is megjelent [29] és részét képezi az értekezésnek is. A szimplex algoritmusban nagyon sok pricing módszer ismeretes. Ezek különböz˝o hatásossággal m˝uködnek különféle feladatok esetén. A szerz˝o kidolgozott egy kooperatív parallel keret-algoritmust, aminek segítségével el lehet végezni a pricing módszerek vizsgálatát. A Mitra által biztosított háttér segítségével lefolytatott kísérletek igen érdekes eredményeket hoztak [32]. Az derült ki, hogy egy önmagában egyébként igen szerényen m˝uköd˝o pricing módszer is képes a megoldás bizonyos szakaszaiban az összes többinél hatásosabban m˝uködni. Ez az észrevétel indokolta, hogy az értekezésbe belekerüljön gyakorlatilag minden pricing technika. A nagyméret˝u LP feladatok legfontosabb jellemz˝oje a ritkásság. A nem-nullák aránya gyakran jóval 0.1% alatt van. Ezen tulajdonság kihasználása képezi az implementációk hatékonyságának az egyik alapját. Ennek elérésére jól megtervezett adatstruktúrákra és rajtuk definiált m˝uveletekre van szükség. Ehhez a számítástudomány bizonyos eredményeinek újragondolásán és adaptálásán keresztül vezet az út. A fentebb említett, legnagyobb el˝orehaladást biztosító algoritmusok speciális igényei számára a szerz˝o egy priority queue alapján m˝uköd˝o rendez˝o eljárást dolgozott ki és alkalmazott a programjaiban. A kétszeresen láncolt listáknak is elkészítette egy olyan változatát, amely a szimplexben el˝oforduló igények legjobb kielégítésére van hangolva. Ez utóbbi sok algoritmikus elemben is kulcsszerepet játszik és az értekezésben részletesen tárgyalva van. A gyorsítás mértéke könnyen lehet százszoros vagy még annál is több. Megfigyelések azt mutatják, hogy gyakran bizonyos transzformált vektorok is elég ritkásak maradnak. Ezt szintén igen jól ki lehet használni például a transzformált pivot sor meghatározásának felgyorsítására, illetve az árnyékárak transzformálására, amiknek egyébként
2004.2.11
M AROS
Doktori tézisek
7 of 18
nagy a számításigénye. Mindezek feltétele, hogy legyen elegend˝o hely a feltételi mátrix sor- és oszlopfolytonos tárolására. A gyorsulás mértéke itt is elérheti a harminctól ötvenszerest. A szimplex módszer gyakorlati hatékonyságát, jobb híján, a megoldási id˝ovel szokás jellemezni. Ez persze feltételezi, hogy a feladatot egyáltalán meg tudja oldani, ami nem is mindig nyilvánvaló. Ebb˝ol a szempontból mindegy, hogy sok olcsó, vagy kevés drága iterációval sikerült egy megoldást elérni. Miután az algoritmikus elemek legcélravezet˝obb kombinációja feladatonként változhat, egy korszer˝u programcsomagban nagy algoritmikus gazdagságra van szükség, hogy a felmerül˝o feladatok széles körét hatékonyan tudja megoldani. Ez tette indokolttá, hogy az értekezés mindezekre kitérjen.
2004.2.11
2. fejezet A tudományos kutatások során alkalmazott módszerek Miután az értekezés f˝o célja a szimplex módszer olyan változatainak a kidolgozása, amelyek lehet˝ové teszik igen nagyméret˝u és nehéz lineáris programozási feladatok megbízható és hatékony megoldását, szükséges volt a módszer minden egyes elemének az alapos vizsgálatára és revíziójára. Valójában még ennél is többr˝ol volt szó, hiszen olyan elemeket is meg kellett vizsgálni, amelyek a szimplex módszer elméleti változatában nem is szerepelnek, mint például LP el˝ofeldolgozás (presolve), normálás, jó kezd˝o megoldás meghatározása. Noha az ma már általánosan elfogadott tény, hogy egy elméleti algoritmus számítógépes implementációja igen komoly intellektuális er˝ofeszítést igényel, az már korántsem nyilvánvaló, hogy ezt hogyan lehet megvalósítani. A kutatás során az derült ki, hogy a sikerhez az LP esetén a következ˝o szakterületek mély ismerete és alkotó továbbm˝uvelése vagy adaptációja szükséges: (a) matematikai algoritmusok, (b) a számítástudomány néhány területe, (c) modern software engineering, (d) numerikus analízis és (e) a modern számítógépek architektúrája. A kutatás során alkalmazott vizsgálati módszerek az operációkutatás és az informatika tudományok által használt módszertant követték. Az eredmények kisebb része született deduktív úton, nagyobb részük pedig induktív módon a „tapasztalat ⇒ következtetés” paradigma alapján, azonban ilyenkor is minden esetben matematikailag korrekt algoritmusok születtek. A vizsgálatok elvégzéséhez a szerz˝o kifejlesztett egy MILP nev˝u, szimplex alapú LP programcsomagot. Ez volt az algoritmusok kipróbálásának az környezete. Az itt szerzett tapasztalatok felhasználásával fejlesztette tovább az algoritmusokat és ellen˝orizte, hogy azok milyen mérték˝u javulást eredményeznek a korábban használt eljárásokkal szemben. A kísérleteket els˝osorban az általánosan elfogadott netlib/lp/data és netlib/lp/data/kennington LP teszt 8
M AROS
Doktori tézisek
9 of 18
feladattárak nagyméret˝u feladatain, valamint számos egyéb feladaton végezte. Néhány adat a nagyobb netlib/lp/data feladatok méretének az érzékeltetésére:
Name 80BAU3B DEGEN3 GREENBEA FIT2P MAROS-R7 PILOT87 STOCFOR3
Rows
Cols
2263 1504 2393 3001 3137 2031 16676
9799 1818 5405 13525 9408 4883 15695
Nonzeros
BR
29063 26230 31499 60784 151120 73804 74004
B B B B
Optimal Value 9.8723216072E+05 -9.8729400000E+02 -7.2462405908E+07 6.8464293232E+04 1.4971851665E+06 3.0171072827E+02 -3.9976661576E+04
illetve néhány a netlib/lp/data/kennington feladattárból:
Name CRE-B CRE-D KEN-13 OSA-60 PDS-10 PDS-20
rows
columns
nonzeros
bounds
optimal value
9649 8927 28633 10281 16559 33875
72447 69980 42659 232966 48763 105728
328542 312626 139834 1630758 140063 304153
0 0 85318 0 16148 34888
2.3129640e+07 2.4454970e+07 -1.0257395e+10 4.0440725e+06 2.6727095e+10 2.3821659e+10
Ez utóbbiak nagyobb méret˝uek, de algoritmikusan valamivel könnyebbek. A vizsgálatok kiterjedtek az új matematikai algoritmusokra (operációkutatás), az adaptált rendez˝o eljárásokra, célirányosan kifejlesztett listakezel˝o algoritmusokra (számítástudomány), programozástechnikai alternatívákra (software engineering), numerikus tulajdonságok elleno˝ rzésére (numerikus analízis), valamint a hardware lehet˝oségek kihasználására (hardware). A fentiek közül egyedül a speciális rendez˝o eljárások nem szerepelnek explicit módon tárgyalva az értekezésben. A felsorolt eredmények nagy többségét a szerz˝o egyedül érte el. Ett˝ol eltér˝o esetben a társszerz˝ok meg vannak nevezve.
2004.2.11
3. fejezet Az értekezésben közölt új tudományos eredmények tételes listája A könyv a címben megjelölt témakör átfogó vizsgálatát t˝uzte ki célul. Ez egy új megközelítés, mivel ilyen jelleg˝u m˝u, a könyvr˝ol eddig megjelent recenziók tanúsága szerint, még nem állt rendelkezésre a szakirodalomban. Az átfogó jelleg miatt szerepelnek benne olyan eredmények is, amelyeket nem a szerz˝o ért el. Ezek nincsenek feltüntetve az alábbi felsorolásban. Vannak továbbá olyan eredmények is, amelyeket ugyan a szerz˝o ért el, de ezek a kandidátusi fokozat megszerzésével kapcsolatosak. Ezen eredmények azonban vagy továbbfejlesztve, vagy újszer˝u megvilágításban jelennek meg a könyvben. Az egyértelm˝uség érdekében ezek külön felsorolásban szerepelnek. A könyv els˝o részében, az elméleti háttér tárgyalásakor számos tétel és bizonyítás szerepel. Ezek nem tartalmaznak új eredményeket. Ugyanakkor ezek egységes keretbe foglalása újszer˝u és a kés˝obbi vizsgálatokhoz nélkülözhetetlen. Az új eredmények, amelyek nagyrészt (de nem kizárólagosan) algoritmusok formájában jelennek meg, többségében a m˝u második részében találhatók.
3.1.
Új tudományos eredmények
1. A szerz˝o eredménye a legáltalánosabban felírt LP feladatnak a számítási célokra alkalmas alakjai közül a Computational form #2 bevezetése (1.2.2 szakasz, 13–17 oldal), a Computational form #1 Orchard-Hays-t˝ol eltér˝o definiálása (1.2.1 szakasz, 5–13 oldal) és a Yet another formulation (1.3.2 szakasz, 17–18 oldal) számítástechnikai tulajdonságainak elemzése. 10
M AROS
Doktori tézisek
11 of 18
2. A szerz˝o eredménye az Artificial Elimination Procedure (2.2.4 szakaszban, 36–37 oldal), amely egy algoritmust ad arra, hogy a standard LP feladat módosított szimplex módszerrel történ˝o megoldása során, degeneráció esetén, hogyan lehet a mesterséges változókat eliminálni a bázisból. 3. A szerz˝o fogalmazza meg el˝oször a lineáris programozási software kívánatos tulajdonságait, amelyek azonban messze túlmutatnak ezen a körön és tetsz˝oleges optimalizációs software esetére érvényesek (4. fejezet bevezetése és 4.1 szakasz, 59–62 oldal). 4. A szerz˝o, M. H. Khaliq PhD hallgatójával közösen [29] megmutatja, hogy néhány fontos hardware tulajdonságot hogyan lehet kihasználni az LP software hatékonyságának növelésére (cache memory, pipelining, branch prediction) és tárgyal néhány programozástechnikai megoldást is (4.2 szakasz, 63–65 oldal). 5. A láncolt listák (linked lists) alapvet˝o szerepet tudnak játszani a szimplex módszer különböz˝o részeinek a hatékonyságában. A szerz˝o kidolgozott és részletesen bemutat egy olyan eljárást a kétszeresen láncolt listák kezelésére, amelyet a szimplex módszeren belül (de számos egyéb optimalizáló eljárásban is) igen el˝onyösen lehet használni és ami egyben alapját képezi számos kés˝obbi LP algoritmus és algoritmikus elem rendkívül gyors m˝uködésének (5.5 szakasz, 80–84 oldal). 6. Az el˝oz˝o részekben kidolgozott technikák alapján a szerz˝o megmutatja, hogyan lehet az inverz szorzatalakját (product form of the inverse, PFI) meghatározó algoritmust hatékonyan implementálni (8.1.3 szakasz, 129–131 oldal). Ugyanez a gondolat könnyen adaptálható az inverz LU formáját meghatározó algoritmus esetére is. 7. A 8.1.4.2 szakasz (132–133 oldal) egy fontos észrevételt tartalmaz a BTRAN m˝uveletre vonatkozóan, amely a használatával kapcsolatos számítási munka becslésének az alapjául szolgál. A szerz˝o ennek az észrevételnek alapján a kés˝obb bevezetett algoritmusokban a transzformálandó vektor ritkásságának mértékét figyelembevev˝o alternatív megoldásokat mutat be. 8. A szerz˝o új tárgyalást ad a CF#1-nek megfelel˝o általános LP feladat optimalitási kritériumára és annak bizonyítására (9.2 szakasz, 164–166 oldal). 9. A szerz˝o új tárgyalást és algoritmikus leírást ad a primál szimplex második fázisának hányadostesztjére CF#1 esetén, majd ezt általánosítja CF#2-re (9.3, 9.3.1 és 9.3.2 szakaszok, 167–176 oldal). 2004.2.11
M AROS
Doktori tézisek
12 of 18
10. A primál második fázis hányadostesztjének számítástechnikai elemzése során megadja a Harris-féle hányadosteszt egy módosítását, amely numerikusan ugyanolyan kedvez˝o, de algoritmikusan hatékonyabb (9.3.4 szakasz, 178–181 oldal). 11. A szerz˝o részletesen tárgyalja az árnyékárak transzformációjának ismert módjait, de azok számítástechnikai elemzését is megadja, majd megmutatja, hogy a m˝uveletben szerepl˝o vektorok gyakori ritkásságát kihasználva hogyan lehet a transzformációt jelent˝osen felgyorsítani (9.4.2 szakasz, 182–184 oldal). 12. A szerz˝o eddig nem publikált részletekbe men˝oen tárgyalja a Goldfarb és Reid által javasolt, majd Forrest és Goldfarb által továbbfejlesztett steepest edge [9; 5] oszlopkiválasztási technikát. Ezáltal nemcsak a jobb megértést segíti el˝o, hanem jól megvilágítja a technika hasznossági feltételeit. Végül a szerz˝o megadja a módszer számítástechnikai elemzését, ami a hatékony implemetáció alapjául szolgál (9.5.4.1 szakasz, 190–193 oldal). 13. A 9.5.5 szakaszban a szerz˝o egy új általános oszlopkiválasztási algoritmust (SIMPRI) mutat be, amely számos ismert oszlopkiválasztási módszert speciális esetként tartalmaz és amelynek a segítségével újabb stratégiák tervezhet˝ok. Megadja az algoritmus helyességének a bizonyítását is (198–203 oldal). 14. A szerz˝o a 9.7.2 szakaszban általánosítja és módosítja Wolfe ‘ad hoc’ módszerét a degenerációs ciklizálás és stalling elkerülésére. A módosítás eredményeként a kés˝obbi degenerált lépések valószín˝usége csökken (234–237 oldal). 15. A 9.7.3 szakaszban a szerz˝o általánosítja és módosítja, ezáltal hatékonyabbá teszi a Gill és társai által javasolt EXPAND eljárást [8] a degenerációs ciklizálás és stalling elkerülésére (237–241 oldal). 16. A 9.7.4.1 szakaszban a szerz˝o megfogalmaz egy általános perturbációs sémát (242 oldal). 17. A Benichou és társai által publikált perturbációs technikát [1], amely az IBM MPSX programcsomagja számára készült, a szerz˝o a 9.7.4.2 szakaszban módosítja, ami az eljárás hatékonyságának növekedését eredményezi (242–243 oldal). 18. A 9.8.2.1 szakaszban a szerz˝o egy új induló-bázis meghatározó algoritmust mutat be (CRASH(LTSF)), ami nemcsak a bázis triangularitására, hanem annak minél nagyobb fokú megengedettségére is törekszik. Az algoritmus rendkívül nagy sebességgel tud m˝uködni a korábban bevezetett kétszeresen láncolt listák segítségével (248–251 oldal). 2004.2.11
M AROS
Doktori tézisek
13 of 18
Különféle (a m˝uben nem részletezett) módosításokkal ez egy algoritmus családnak tekinthet˝o, amely még a legegyszer˝ubb változatában is eredményesebbnek bizonyult az ún. CPLEX bázisnál, amint az a szerz˝o Mitra-val közös cikkéb˝ol kiderül [33]. 19. A szerz˝o újszer˝u, eddig még nem publikált módon tárgyalja a duál megengedettséget CF#1-re és CF#2-re (10.1 szakasz, 261–262 oldal). 20. A szerz˝o egy egyszer˝u általánosítását adja Chvatal fels˝okorlátos duál algoritmusának, aminek eredménye a Dual-G algoritmus (10.2.2 szakasz, 266–267 oldal). 21. A szerz˝o a 10.2.3–10.2.6 szakaszokban (267–277 oldal) megfogalmaz egy duál második fázis eljárást, amelyre DUAL-GX néven hivatkozik. Ez akár CF#1-re és CF#2-re is alkalmazható és a hagyományosan használt algoritmusok általánosításának tekinthet˝o. A szerz˝o megadja a hatékony implementáció feltételeit is. Az algoritmus jellemz˝oje, hogy egy iterációban sok hagyományos iterációt tud elvégezni minimális számítási többlet munka árán. Sokkal hatékonyabb tud lenni duál degenerált bázisok és numerikusan nehéz feladatok esetén. Különösen a kevert egészérték˝u feladatok branch-and-bound típusú eljárásokkal történ˝o megoldása esetén mutatkoznak meg el˝onyös tulajdonságai (amikoris sok fels˝okorlátos változó van a feladatban), azonban egyéb feladatok megoldása során is rendszeresen és lényegesen felülmúlja a hagyományos verziókat. Erre vonatkozó néhány tapasztalat [24]-ben található. Az algoritmus alapjai a szerz˝o egy korábbi cikkében [22] fogalmazódtak meg. 22. Az egész 10.4 szakasz a szerz˝o által kidolgozott új duál els˝o fázis eljárás részletes tárgyalásának van szentelve (277–292 oldal). Az algoritmus, amely GDPO néven szerepel, egyaránt alkalmas CF#1-re és — a bemutatott minimális kiegészítéssel — CF#2-re is. A hatékony implementáció feltételei is meg vannak adva. Bár GDPO alapjaiban más, mint DUAL-GX, mégis sok hasonló tulajdonsága van. Ugyanúgy sok hagyományos iterációt tud végrehajtani egyetlen iteráció során (kevés többlet munka árán), adaptív módon képes hatékonyan m˝uködni duál degenerált, illetve numerikusan nehéz feladatok esetén. Lényeges különbség, hogy GDPO igazi ereje akkor mutatkozik meg amikor a feladatban a kevéssé korlátozott változók vannak többségben. A korlátozott változók kezelése ugyanis triviális a duál els˝o fázisban. Néhány számítási tapasztalat a szerz˝o [25] cikkében található, amelyek jó egyezésben vannak az elméleti elvárásokkal. 23. Optimalizáló algoritmusok eredményes fejlesztéséhez elengedhetetlenül fontos, hogy jó tesztfeladatok álljanak rendelkezésre. A szerz˝o nemcsak használta a netlib/lp/data 2004.2.11
M AROS
Doktori tézisek
14 of 18
feladatárat, hanem hozzá is járult annak tanulságos feladatokkal való b˝ovítéséhez. Ezek a feladatok maros.mps, maros-r7.mps és modszk1.mps néven kerültek bele a tárba és számos fejleszt˝o tudott javítani a rendszerén ezeknek a feladatoknak a segítségével. Néhány figyelemreméltó példa: CPLEX [2], AMPL [6], LINPROG [12]. Mindhárom feladat rendszeresen szerepel az újabb publikációk tesztelési eredményeket bemutató táblázataiban. 24. A kísérletekhez és az új eljárások ellen˝orzéséhez szükség volt egy komoly programrendszer létrehozására. A szerz˝o által kifejlesztett szimplex implementáció 1985-t˝ol 1996-ig MILP néven szerepelt, majd egy jelent˝osebb átdolgozás után 1996 óta HIPLEX néven ismeretes. MILP a második legjobbnak bizonyult egy R. Sharda által lefolytatott összehasonlító vizsgálat [36] eredményeként. A vizsgálatban az akkor létez˝o minden komolyabb, PC-re készült LP programcsomag részt vett. Az eredményeket Thiriez is idézi. [35]. A MILP-pel kapcsolatos fejlesztés mintegy „mellékterméke”-ként készült el a MINET nev˝u hálózati szimplex algoritmus és program, amely a DIMACS és a American Mathematical Society által 1992-ben rendezett International Implementation Challenge-en szignifikánsan jobbnak bizonyult, mint az akkor legjobbnak tartott NETFLO program [20].
3.2.
Korábbi eredmények továbbfejlesztése
1. A szerz˝o az általa korábban javasolt primal els˝o fázis eljárást [14] a 9.6 szakaszban továbbfejleszti és általánosítja CF#2-re, részletesen bemutatja az eljárás el˝onyös számítástechnikai tulajdonságait és megadja a hatékony m˝uködéshez szükséges implementációs feltételeket (203–227 oldal). 2. A szerz˝o korábbi eredménye egy adaptíve composite els˝o fázis eljárás [14], aminek kidolgozta egy alternatív változatát [15] és amely az értekezés 9.6.5 szakaszában található (229–230 oldal). 3. A szerz˝o korábbi eredménye [13] az a degeneráció ellenes trianguláris indulóbázis meghatározó algoritmus, amely most CRASH(ADG) néven van hivatkozva. Az algoritmuson végrehajtott néhány módosítás és a használati feltételek tisztázása tekinthet˝o újdonságnak ([33] és az értekezés 9.8.2.2 szakasza, 251-253 oldal). 2004.2.11
Irodalomjegyzék [1] M. B ENICHOU , J. G AUTIER , G. H ENTGES , AND G. R IBIERE, The efficient solution of large-scale linear programming problems, Mathematical Programming, 13 (1977), pp. 280–322. [2] R. E. B IXBY, Private communications, 1994. [3] V. C HVÁTAL, Linear Programming, Freeman Press, New York, 1983. [4] G. DANTZIG, Maximization of a linear function of variables subject to linear inequalities, in Activity analysis of production and allocation, T. Koopmans, ed., Wiley, New York, 1951, pp. 339–347. [5] J. F ORREST AND D. G OLDFARB, Steepest edge simplex algorithms for linear programming, Mathematical Programming, 57 (1992), pp. 341–374. [6] R. F OURER AND D. G AY, Experience with a Primal Presolve Algorithm, Numerical Analysis Manuscript 93–06, AT&T Bell Laboratiories, Murray Hill, NJ, USA, April 1993. [7] T. G AL AND F. G EUE, A new pivoting rule for various degeneracy problems, Operations Research Letters, 11 (1992), pp. 23–32. [8] P. G ILL , W. M URRAY, M. S AUNDERS , AND M. W RIGHT, A Practical Anti–Cycling Procedure for Linearly Constrained Optimization, Mathematical Programming, 45 (1989), pp. 437–474. [9] D. G OLDFARB AND J. R EID, A Practicable Steepest-Edge Simplex Algorithm, Mathematical Programming, 12 (1977), pp. 361–371. [10] N. G OULD AND J. R EID, New crash procedures for large systems of linear constraints, Mathematical Programming, 45 (1989), pp. 475–501.
15
M AROS
Doktori tézisek
16 of 18
[11] H. G REENBERG, Pivot selection tactics, in Design and Implementation of Optimization Software, H. Greenberg, ed., NATO ASI, Sijthoff and Nordhoff, 1978, pp. 143–174. [12] P. K IRKEGAARD AND P. E. G RONHEIT, LINPROG – A Linear Programming Solver, Research Report Risø–R–707(EN), Risø National Laboratory, Roskilde, Denmark, June 1995. [13] I. M AROS, Adaptív módszerek a lineáris programozásban, II., Alkalmazott Matematikai Lapok, 7 (1981), pp. 1–71. [14]
, A general Phase–I method in linear programming, European Journal of Operational Research, 23 (1986), pp. 64–77.
[15]
, A multicriteria decision problem within the simplex method, in Mathematical Models for Decision Support, G. Mitra, ed., Springer Verlag, 1988, pp. 263–272.
[16]
, MILP linear programming optimizer for personal computers under DOS, Preprints in Optimization, tech. report, Institute of Applied Mathematics, Braunschweig University of Technology, Braunschweig, Germany, September 1990. 16 pages.
[17]
, MILP Linear Programming System, User’s Guide for Version V3.40, Computer and Automation Institute (MTA SZTAKI), Budapest, Hungary, January 1990. In Hungarian.
[18]
, MILP linear programming optimizer for personal computers under DOS, Research Report 41, Computer and Automation Institute (MTA SZTAKI), Budapest, Hungary, 1991. 16 pages.
[19]
, A structure exploiting pricing procedure for network linear programming, Research Report 18–91, RUTCOR, Rutgers University, NJ, USA, May 1991. 15 pages.
[20]
, Performance evaluation of the MINET minimum cost netflow solver, in Network Flows and Matching: DIMACS Implementation Challenge, D. Johnson and C. McGeogh, eds., American Mathematical Society, 1993, pp. 199–217.
[21]
, A practical anti-degeneracy row selection technique in network linear programming, Annals of Operations Research, 47 (1993), pp. 431–442.
[22]
, A Piecewise Linear Dual Procedure in Mixed Integer Programming, in New Trends in Mathematical Programming, R. S. F. Giannesi and S. Komlosi, eds., Kluwer Academic Publishers, 1998, pp. 159–170. 2004.2.11
M AROS
[23]
Doktori tézisek
17 of 18
, A General Pricing Scheme for the Simplex Method, Annals of Operations Research, 124 (2003), pp. 193–203. , A Generalized Dual Phase-2 Simplex Algorithm, European Journal of Operational
[24]
Research, 149 (2003), pp. 1–16. [25]
, A Piecewise Linear Dual Phase-1 Algorithm for the Simplex Method, Computational Optimization and Applications, 26 (2003), pp. 63–81. , Computational Techniques of the Simplex Method, vol. 61 of International Series
[26]
in Operations Research and Management, Kluwer Academic Publishers, Boston, 2003. 325+xx pages, Research monograph. [27] I. M AROS AND J. B OKOR, Személyi számítógépek hatása az operációkutatásra, Alkalmazott Matematikai Lapok, 14 (1989), pp. 155–169. [28] I. M AROS , E. E LLISON , M. H AJIAN , R. L EVKOVITZ , G. M ITRA , AND D. S AYERS, FortMP Manual, Department of Mathematics and Statistics, Brunel University, London and NAG, Oxford, May 1994. Latest revised version: V3.0 in June 1999. [29] I. M AROS AND M. H. K HALIQ, Advances in Design and Implementation of Optimization Software, European Journal of Operational Research, 140 (2002), pp. 322–337. [30] I. M AROS AND G. M ITRA, Finding Better Starting Bases for the Simplex Method, in Operations Research Proceedings 1995, P. K. et al., ed., Springer Verlag, 1996, pp. 7–12. [31]
, Simplex Algorithms, in Advances in Linear and Integer Programming, J. Beasley, ed., Oxford University Press, 1996, pp. 1–46. , Investigating the Sparse Simplex Algorithm on a Distributed Memory Multiproces-
[32]
sor, Parallel Computing, 26 (2000), pp. 151–170. , Strategies for creating advanced bases for large-scale linear programming pro-
[33]
blems, INFORMS Journal on Computing, 10 (Spring 1998), pp. 248–260. [34] W. O RCHARD -H AYS, Advanced Linear-Programming Computing Techniques, McGrawHill, New York, 1968. [35] H. T HIRIEZ, OR Software, European Journal of Operational Research, 39 (1989), pp. 223– 224. 2004.2.11
M AROS
Doktori tézisek
18 of 18
[36] E. WASIL , B. G OLDEN , AND R. S HARDA, Mathematical Programming Software on Microcomputers: Recent Advances, Directions and Trends, in Impact of Recent Advances in Computers on Operations Research, R. Sharda, B. Golden, E. Wasil, O. Balci, and W. Stewart, eds., Elsevier, 1989, pp. 263–272. [37] P. W OLFE, A technique for resolving degeneracy in linear programming, SIAM Journal of Applied Mathematics, 11 (1963), pp. 205–211.
2004.2.11
