ALL libraries (COBIB.SI union bibliographic/catalogue database)
13.
Application of semidefinite programming and high-performance computing in discrete optimization : doctoral thesis
Hrga, Timotej
Pri 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.
Type of material - dissertation
; adult, serious
Publication and manufacture - Ljubljana : [T. Hrga], 2022
It was not necessary to add the material to the shelf.
Bibliographic material was successfully added on shelf.
Adding bibliographical material on shelf was not successful.
Material is already on the shelf.
Permalink
URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year
Impact factor
Edition
Category
Classification
JCR
SNIP
JCR
SNIP
JCR
SNIP
JCR
SNIP
Select the library membership card:
DRS,
in which the journal is indexed
Database name
Field
Year
Links to authors' personal bibliographies
Links to information on researchers in the SICRIS system
Subject headings in COBISS General List of Subject Headings
Select pickup location
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
