-
Application of semidefinite programming and high-performance computing in discrete optimization : doctoral thesisHrga, TimotejPri problemu maksimalnega prereza grafa iščemo tako delitev množice vozlišč na dva dela, da je vsota uteži na povezavah, ki imajo krajišča v različnih delih particije, največja. V ... disertaciji študiramo semidefinitne poenostavitve tega kombinatoričnega problema in uporabo dobljenih mej znotraj metode razveji in omeji. Predstavljena sta dva paralelna eksaktna reševalca BiqBin in MADAM, ki izkoriščata nove poenostavitve, dobljene z okrepitvijo osnovne semidefinitne poenostavitve s podmnožico hipermetričnih neenakosti. Pri tem sta za izračun zgornjih mej uporabljeni metoda svežnjev ter okrepljena Lagrangeva metoda in njene izpeljanke. V primeru MADAM je prednost novega pristopa v cenejšem izračunu dualnih spremenljivk, ki pripadajo pogojem neenakosti. Posledično se zmanjša računska kompleksnost vsake iteracije algoritma, saj se izkaže, da sestoji iz reševanja razpršenega sistema linearnih enačb ter projekcije na nenegativen ortant in stožec pozitivno semidefinitnih matrik. Numerično delovanje metode je podkrepljeno tudi z dokazom konvergence. Poleg tega predlagamo novo strategijo za hitrejše preiskovanje dinamičnega binarnega drevesa, dobljenega pri metodi razveji in omeji, in novo hevristiko za separacijo kršenih hipermetričnih neenakosti. Dodatno prikažemo, kako lahko z uporabo predlaganih algoritmov rešujemo širši razred problemov. Namreč, vsak nevezan kvadratičen problem v binarni spremenljivki ali kvadratičen problem z linearnimi omejitvami se da prevesti na problem maksimalnega prereza. Za transformacijo slednjih uporabimo metodo natančnega kaznovanja. Če ohranimo diskretnost spremenljivk in prenesemo pogoje enakosti v kriterijsko funkcijo, dobimo primer problema maksimalnega prereza, ki ga nato rešimo z metodo razveji in omeji. V nadaljevanju je predstavljena učinkovita implementacija sekvenčnega in paralelnega razveji in omeji algoritma. Slednji temelji na paradigmi mojster-delavci in s pomočjo MPI izkorišča porazdeljeni način paralelizacije. Učinkovitost dobljenih reševalcev primerjamo z BiqCrunch, Gurobi in SCIP na štirih družinah binarnih kvadratičnih problemov. Obsežni numerični rezultati kažejo, da sta BiqBin in MADAM zelo konkurenčna in trenutno najsodobnejša reševalca za tak tip problemov. Razlog za to je boljše razmerje med časom, ki je potreben za izračun semidefinitne poenostavitve in kvaliteto dobljene rešitve. Zmogljivost končnega paralelnega algoritma je testirana na superrračunalniku, kjer je tudi dodatno ovrednotena dobra skalabilnost. S pomočjo paralelnega reševalca lahko občutno zmanjšamo čas iskanja eksaktnih rešitev problema maksimalnega prereza in binarnih kvadratičnih programov z linearnimi omejitvami, ter hkrati povečamo velikost instanc, ki jih znamo rešiti do optimalnosti.Vrsta gradiva - disertacija ; neleposlovje za odrasleZaložništvo in izdelava - Ljubljana : [T. Hrga], 2022Jezik - angleškiCOBISS.SI-ID - 113758467
Povezava(-e):
Repozitorij Univerze v Ljubljani – RUL
Digitalna knjižnica Slovenije - dLib.siDostop z namenskih računalnikov v prostorih NUK
Avtor
Hrga, Timotej
Drugi avtorji
Povh, Janez, 1973- |
Wiegele, Angelika
Teme
matematika |
kombinatorična optimizacija |
problem maksimalnega prereza grafa |
semidefinitno programiranje |
metoda multiplikatorjev alternirajočih smeri |
razveji in omeji |
visokozmogljivo računalništvo |
mathematics |
combinatorial optimization |
Max-Cut problem |
semidefinite programming |
alternating direction method of multipliers |
branch-and-bound |
high-performance computing
Knjižnica | Signatura – lokacija, inventarna št. ... | Status izvoda |
---|---|---|
Narodna in univerzitetna knjižnica, Ljubljana | GS II 746415 glavno skladišče | prosto - za čitalnico |
FMF in IMFM, Matematična knjižnica, Ljubljana | Skladišče-Jadranska 21 14521/43 |
prosto - za čitalnico |
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Hrga, Timotej | 50783 |
Povh, Janez, 1973- | 22649 |
Wiegele, Angelika |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.