1512 KB0 KB0 KB2022Hrga, TimotejPovh, JanezWiegele, Angelika158 str., 30 cmCOBISSID:113758467PID:https://repozitorij.uni-lj.si/IzpisGradiva.php?id=137850URN:URN:NBN:SI:doc-RCF0FXQLenT. Hrgavisokošolska delaalternating direction method of multipliersbranch-and-boundcombinatorial optimizationhigh-performance computingkombinatoricˇna optimizacijamatematikamathematicsMax-Cut problemmetoda multiplikatorjev alternirajocˇih smeriproblem maksimalnega prereza grafarazveji in omejisemidefinite programmingsemidefinitno programiranjevisokozmogljivo racˇunalnisˇtvoApplication of semidefinite programming and high-performance computing in discrete optimization| doctoral thesis|We study semidefinite programming relaxations of Max-Cut, the problem of finding the cut with the maximum weight in a given graph, and investigate the potential of the resulting bounds within the branch-and-bound framework in order to solve the problem to optimality. We present BiqBin and MADAM, parallel semidefinite-based exact solvers that utilize new semidefinite relaxations obtained by strengthening the basic relaxation with a subset of hypermetric inequalities, and then apply the bundle method and the alternating direction method of multipliers, respectively, in the bounding routines. In the case of MADAM, the benefit of the new approach is a less computationally expensive update rule for the dual variable with respect to the inequality constraints. This results in a small computational complexity per iteration, since it essentially consists of solving a sparse system of linear equations and a projection onto the nonnegative orthant and the positive semidefinite cone. Furthermore, we also provide a theoretical convergence proof of the algorithm. Moreover, new strategies for faster exploration of the branch-and-bound tree are used and a new heuristic procedure for separating violated hypermetric inequalities is presented. We demonstrate how the solvers can be extended to solve two other classes of optimization problems, namely unconstrained and linearly constrained binary quadratic problems. For the latter problems, the approach is based on an exact penalty method to first efficiently transform the original problem into an instance of Max-Cut, and then to solve the Max-Cut problem by the branch-and-bound algorithm. Additionally, an efficient implementation of a sequential and a parallel branch-and-bound algorithm is presented. The latter is based on a load coordinator-worker scheme using MPI for multi-node parallelization and is evaluated on a high-performance computer. The solvers are benchmarked against BiqCrunch, Gurobi and SCIP on four families of binary quadratic problems. Extensive computational experiments demonstrate that MADAM and BiqBin are highly competitive and state-of-the-art solvers. The reason is that in our case we have a better balance between the time needed to solve the semidefinite relaxation and the quality of the solution when compared to other solvers. We also evaluate the parallel solver by showing its good scaling properties. It greatly reduces the time needed to solve the Max-Cut and linearly constrained binary quadratic problems to optimality and increases the size of instances that can be solved in a routine wayPri 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 optimalnostiTEXTvisokošolska delatheses and dissertationsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza v Ljubljani, Fakulteta za matematiko in fiziko