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

Hrga, Timotej (author), Povh, Janez (mentor), Wiegele, Angelika (comentor)

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 way.

• Language: English
• Keywords: combinatorial optimization, Max-Cut problem, semidefinite programming, alternating direction method of multipliers, branch-and-bound, high-performance computing
• Work type: Doctoral dissertation
• Typology: 2.08 - Doctoral Dissertation
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2022
• PID: 20.500.12556/RUL-137850
• UDC: 519.8
• COBISS.SI-ID: 113758467
• Publication date in RUL: 03.07.2022

Secondary language

• Language: Slovenian
• Title: Uporaba semidefinitnega programiranja in visokozmogljivega računalništva v diskretni optimizaciji

Abstract

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.

• Keywords: kombinatorična optimizacija, problem maksimalnega prereza grafa, semidefinitno programiranje, metoda multiplikatorjev alternirajočih smeri, razveji in omeji, visokozmogljivo računalništvo