Application of semidefinite programming and high-performance computing in discrete optimization : doctoral thesis

angleški

doktorska dela

2022

kombinatoricˇna optimizacija   matematika   metoda multiplikatorjev alternirajocˇih smeri   problem maksimalnega prereza grafa   razveji in omeji   semidefinitno programiranje   visokozmogljivo racˇunalnisˇtvo

Univerza v Ljubljani, Fakulteta za matematiko in fiziko
(Obvezni izvod spletne publikacije)

Pri problemu maksimalnega prereza grafa isˇcˇemo tako delitev mnozˇice vozlisˇcˇ na dva dela, da je vsota utezˇi na povezavah, ki imajo krajisˇcˇa v razlicˇnih delih particije, najvecˇja. V disertaciji sˇtudiramo semidefinitne poenostavitve tega kombinatoricˇnega problema in uporabo dobljenih mej znotraj metode razveji in omeji. Predstavljena sta dva paralelna eksaktna resˇevalca BiqBin in MADAM, ki izkorisˇcˇata nove poenostavitve, dobljene z okrepitvijo osnovne semidefinitne poenostavitve s podmnozˇico hipermetricˇnih neenakosti. Pri tem sta za izracˇun zgornjih mej uporabljeni metoda svezˇnjev ter okrepljena Lagrangeva metoda in njene izpeljanke. V primeru MADAM je prednost novega pristopa v cenejsˇem izracˇunu dualnih spremenljivk, ki pripadajo pogojem neenakosti. Posledicˇno se zmanjsˇa racˇunska kompleksnost vsake iteracije algoritma, saj se izkazˇe, da sestoji iz resˇevanja razprsˇenega sistema linearnih enacˇb ter projekcije na nenegativen ortant in stozˇec pozitivno semidefinitnih matrik. Numericˇno delovanje metode je podkrepljeno tudi z dokazom konvergence. Poleg tega predlagamo novo strategijo za hitrejsˇe preiskovanje dinamicˇnega binarnega drevesa, dobljenega pri metodi razveji in omeji, in novo hevristiko za separacijo krsˇenih hipermetricˇnih neenakosti. Dodatno prikazˇemo, kako lahko z uporabo predlaganih algoritmov resˇujemo sˇirsˇi razred problemov. Namrecˇ, vsak nevezan kvadraticˇen problem v binarni spremenljivki ali kvadraticˇen problem z linearnimi omejitvami se da prevesti na problem maksimalnega prereza. Za transformacijo slednjih uporabimo metodo natancˇnega kaznovanja. Cˇe ohranimo diskretnost spremenljivk in prenesemo pogoje enakosti v kriterijsko funkcijo, dobimo primer problema maksimalnega prereza, ki ga nato resˇimo z metodo razveji in omeji. V nadaljevanju je predstavljena ucˇinkovita implementacija sekvencˇnega in paralelnega razveji in omeji algoritma. Slednji temelji na paradigmi mojster-delavci in s pomocˇjo MPI izkorisˇcˇa porazdeljeni nacˇin paralelizacije. Ucˇinkovitost dobljenih resˇevalcev primerjamo z BiqCrunch, Gurobi in SCIP na sˇtirih druzˇinah binarnih kvadraticˇnih problemov. Obsezˇni numericˇni rezultati kazˇejo, da sta BiqBin in MADAM zelo konkurencˇna in trenutno najsodobnejsˇa resˇevalca za tak tip problemov. Razlog za to je boljsˇe razmerje med cˇasom, ki je potreben za izracˇun semidefinitne poenostavitve in kvaliteto dobljene resˇitve. Zmogljivost koncˇnega paralelnega algoritma je testirana na superrracˇunalniku, kjer je tudi dodatno ovrednotena dobra skalabilnost. S pomocˇjo paralelnega resˇevalca lahko obcˇutno zmanjsˇamo cˇas iskanja eksaktnih resˇitev problema maksimalnega prereza in binarnih kvadraticˇnih programov z linearnimi omejitvami, ter hkrati povecˇamo velikost instanc, ki jih znamo resˇiti do optimalnosti.

12.05.2023