Parallel Multi-Objective Branch and Bound
Wei Zhang · 2008
This thesis presents sequential and parallel implementation of MOBB(Multi-Objective-Branch-and-Bound) algorithm, a novel algorithm that solves MOMIP(Multi-Objective-Mixed-Integer-Programming)problem. While SOMIP(Single-Objective-Mixed-Integer-Programming)is notoriously hard to solve, MOMIP is even harder. No efficient algorithms to solve MOMIP has been known before. MOBB is based on tradtional SOBB(Single-Objective-Branch-and-Bound) algorithm, with several major modifications of bounding feasible region and of how to prune Branch-and-Bound tree. Parallelization is implemented with the hope of speeding up calculation as much as possible. The combination of a novel algorithm and its parallelization is the highlight of this thesis project. All classes, methods, data structures and algorithms in this thesis are implemented in C++, while certain data analysis and visualization are implemented in Matlab and Python. The result of this project shows that our MOBB algorithm is much better than the traditional brute and force algorithm. Further, our parallelization of MOBB algorithm has achieved super linear speedup, which