A parallel approach to bi-objective integer programming

William Pettersson, Melih Ozlen

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

Keywords


integer programming, multi objective programming, parallel computing

Full Text:

PDF BibTeX


DOI: http://dx.doi.org/10.21914/anziamj.v58i0.11724



Remember, for most actions you have to record/upload into this online system
and then inform the editor/author via clicking on an email icon or Completion button.
ANZIAM Journal, ISSN 1446-8735, copyright Australian Mathematical Society.