-
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.Type of material - dissertation ; adult, seriousPublication and manufacture - Ljubljana : [T. Hrga], 2022Language - englishCOBISS.SI-ID - 113758467
Link(s):
Repository of the University of Ljubljana – RUL
Digitalna knjižnica Slovenije - dLib.siDostop z namenskih računalnikov v prostorih NUK
Author
Hrga, Timotej
Other authors
Povh, Janez, 1973- |
Wiegele, Angelika
Topics
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
Library | Call number – location, accession no. ... | Copy status |
---|---|---|
National and University Library, Ljubljana | GS II 746415 glavno skladišče | available - reading room |
FMF, Mathematical Library, Lj. | Skladišče-Jadranska 21 14521/43 |
available - reading room |
Shelf entry
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 |
---|---|
Hrga, Timotej | 50783 |
Povh, Janez, 1973- | 22649 |
Wiegele, Angelika |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.