A parallel approach to bi-objective integer programming

Abstract

The real world applications of optimisation algorithms often are only interested in the running time of an algorithm, which can frequently be significantly reduced through parallelisation. We present two methods of parallelising the recursive algorithm presented by Ozlen, Burton and MacRae [J. Optimization Theory and Applications; 160:470--482, 2014]. Both new methods utilise two threads and improve running times. One of the new methods, the Meeting algorithm, halves running time to achieve near-perfect parallelisation, allowing users to solve bi-objective integer problems with more variables. References

• M. Abbas and D. Chaabane. Optimizing a linear function over an integer efficient set. European Journal of Operational Research, 174:1140–1161, 2006. doi:10.1016/j.ejor.2005.02.072
• H. P. Benson. An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem. Journal of Global Optimization, 13:1–24, 1998. doi:10.1023/A:1008215702611
• N. Boland, H. Charkhgard and M. Savelsbergh. The triangle splitting method for biobjective mixed integer programming. In J. Lee and J. Vygen editors Integer Programming and Combinatorial Optimization 2014, Lecture Notes in Computer Science, 8494. Springer, Cham, 2014, pp. 162–173. doi:10.1007/978-3-319-07557-0_14
• C. Dhaenens, J. Lemesre and E. G. Talbi. K-PPM: A new exact method to solve multi-objective combinatorial optimization problems. European Journal of Operational Research, 200:45–53, 2010. doi:10.1016/j.ejor.2008.12.034
• M. Ehrgott. Multicriteria Optimization, Lecture notes in economics and mathematical systems, Springer, 2005. doi:10.1007/3-540-27659-9
• J. M. Jorge. An algorithm for optimizing a linear function over an integer efficient set. European Journal of Operational Research, 195:98–103, 2009. doi:10.1016/j.ejor.2008.02.005
• M. Ozlen, B. A. Burton and C. G. MacRae. Multi-objective integer programming: an improved recursive algorithm. Journal of Optimization Theory and Applications, 160:470–482, 2014. doi:10.1007/s10957-013-0364-y
• C .H. Papadimitriou and K. Steiglitz Combinatorial Optimization: Algorithm and Complexity, Prentice Hall, 1982. doi:10.1109/TASSP.1984.1164450
• K. E. Parsopoulos and M. N. Vrahatis. Particle swarm optimization method in multiobjective problems. In SAC '02: Proceedings of the 2002 ACM Symposium on Applied Computing. ACM, New York, 2002, pp. 603–607. doi:10.1145/508791.508907
• A. Przybylski and X. Gandibleux. Multi-objective branch and bound. European Journal of Operational Research, 260:856–872, 2017. doi:10.1016/j.ejor.2017.01.032