Synergistic parallel multi-objective integer programming

William Pettersson, Melih Ozlen

Published 2017-05-08Version 1

Exactly solving multi-objective integer programming problems is often a very time consuming process. This paper presents a new way of developing parallel multi-objective algorithms. We develop theory that utilises elements of the symmetric group to apply a permutation to the objective functions to assign different workloads. This theory applies to algorithms that order the objective functions lexicographically. Each permutation can be solved in parallel, and we describe how each worker on a given permutation may communicate with other workers to reduce the overall running time. By allowing workers to share data in real-time, rather than only at completion of a task, we are able to take advantage of the synergy between these different tasks. We implement these ideas into a practical parallel MOIP solver, and analyse the running time of various problems, with various parallelisation techniques. Results show remarkable performance improvements, with running times decreased by a factor of three with the use of four threads across all problem types and sizes. This differs from existing techniques which often have start-up costs that dominate their running times on smaller problems. Even with all larger problems tested, our algorithm outperforms state of the art parallel algorithms. We also note some interesting performance patterns based on the distribution of permutations that may warrant further study. This new algorithm, and the implementation we provide, allows users to solve MOIP problems with many more variables or objective functions.