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

english

doktorska dela

2022

alternating direction method of multipliers   branch-and-bound   combinatorial optimization   high-performance computing   mathematics   Max-Cut problem   semidefinite programming

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

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.

12.05.2023