Parallelization of Branch-and-Bound Optimization Procedures

Tutor: Bho Matthiesen
Type of Thesis: Project (MSc), Master's thesis (MSc)
date of issue: -
Student: -
Status: available

Optimization theory is an essential tool in the design of communication systems and signal processing algorithms. While convex optimization problems can be solved efficiently even for a very large number of variables, nonconvex programs are often NP-hard and have exponential computational complexity. However, efficient algorithms can be designed that are able to solve small and medium scale problems with guaranteed optimality. Given that many engineering problems are inherently nonconvex, global optimization theory is an important tool to verify heuristic algorithms and to obtain authoritative performance assessments.

A widely employed algorithmic approach to solve such problems is known as branch-and-bound (BB). In such an algorithm, an important subproblem is the computation of bounds on the objective value. In many instances, e.g., for optimal beamforming design in wireless interference networks, this bounding step is the main performance bottleneck. The goal of this thesis is to evaluate different parallelization strategies for BB, to incorporate such a strategy in an existing C++ implementation using MPI, and to evaluate the performance gain on a high performance computer.

This thesis requires proficiency in C++ and math. Prior exposition to optimization theory and parallel programming is desirable. The thesis can be written in English or German.

Last change on 16.11.2020 by B. Matthiesen
AIT ieee GOC tzi ith Fachbereich 1
© Department of Communications Engineering - University of BremenImprint / Contact