Implementation of Paralllel Branch and Bound algorithm for combinatorial optimization

Project reference: 2020

Over the past decades a vast number of algorithms have been proposed to solve problems in combinatorial optimization either approximately or up to optimality. But despite the availability of high-performance infrastructure in recent years only a small number of these algorithms have been considered from the standpoint of parallel computation. We will review the most important aspects of the branch and bound algorithm and develop a method for finding exact solutions of NP-hard combinatorial optimization problem and produce efficient implementation using high performance computing. We will use parallel branch and bound algorithm that efficiently approximates original problem using semidefinite relaxations. Sequential algorithms search dynamically built enumeration tree one node at the time, whereas parallel algorithms can independently evaluate multiple nodes. The aim of the project is to develop and implement different distributed parallel schemes of Branch and bound algorithm using message-passing interface (MPI) for multi-node parallelization and considerably reduce the running time of the exact solver.

Project Mentor: MSc. Timotej Hrga

Project Co-mentor: Prof.  Janez Povh, PhD

Site Co-ordinator: Dr. Pavel Tomšič

Participants: İrem Naz Çoçan, Carlos Alejandro Munar Raimundo

Learning Outcomes:
The student will learn and improve their skills to analyse and design the scalability of parallel programming.

The student will learn how to implement parallel branch and bound method using different schemes.

Student Prerequisites (compulsory):
Programming skills, C/C++, knowledge in OOP, parallel algorithm design

Student Prerequisites (desirable):
Knowledge in combinatorial optimization and semidefinite programming. Familiar with Linux and HPC.

Training Materials:

OpenMPI documentation:
https://www.open-mpi.org/doc
https://computing.llnl.gov/tutorials/mpi

Semidefinite programming:
https://neos-guide.org/content/semidefinite-programming

Branch and Bound:
https://optimization.mccormick.northwestern.edu/index.php/Branch_and_bound_(BB)

Workplan:

• W1: Introductory week
• W2-7: Implementing the parallel schemes in the code (creating, running cases, analysing the results).
• W8: Final report and video recording.

Final Product Description:

• Implementation of different parallel approaches to distributed branch and bound algorithm
• Reduce the running time of sequential branch and bound algorithms.
• Analysing the results.

Adapting the Project: Increasing the Difficulty:
We can increase the size of data instances or add additional parallel scheme to be implemented.

Adapting the Project: Decreasing the Difficulty:
We can decrease the size of data instances.

Resources:
HPC cluster at University of Ljubljana, Faculty of Mechanical Engineering, and other available HPCs.

Organisation:
University of Ljubljana