Home > Research > Publications & Outputs > Primal and dual multi-objective linear programm...

Electronic data

  • 20150317

    Rights statement: This is an Accepted Manuscript of an article published by Taylor & Francis Group in Optimization on 13/07/2015, available online:http://www.tandfonline.com/10.1080/02331934.2015.1051534

    Accepted author manuscript, 197 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

View graph of relations

Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes

Research output: Contribution to journalJournal article

Published
<mark>Journal publication date</mark>02/2016
<mark>Journal</mark>Optimization
Issue number2
Volume65
Number of pages17
Pages (from-to)415-431
Publication statusPublished
Early online date13/07/15
Original languageEnglish

Abstract

Multiplicative programming problems (MPPs) are global optimization problems known to be NP-hard. In this paper, we employ algorithms developed to compute the entire set of nondominated points of multi-objective linear programmes (MOLPs) to solve linear MPPs. First, we improve our own objective space cut and bound algorithm for convex MPPs in the special case of linear MPPs by only solving one linear programme in each iteration, instead of two as the previous version indicates. We call this algorithm, which is based on Benson’s outer approximation algorithm for MOLPs, the primal objective space algorithm. Then, based on the dual variant of Benson’s algorithm, we propose a dual objective space algorithm for solving linear MPPs. The dual algorithm also requires solving only one linear programme in each iteration. We prove the correctness of the dual algorithm and use computational experiments comparing our algorithms to a recent global optimization algorithm for linear MPPs from the literature as well as two general global optimization solvers to demonstrate the superiority of the new algorithms in terms of computation time. Thus, we demonstrate that the use of multi-objective optimization techniques can be beneficial to solve difficult single objective global optimization problems.

Bibliographic note

This is an Accepted Manuscript of an article published by Taylor & Francis Group in Optimization on 13/07/2015, available online: http://www.tandfonline.com/10.1080/02331934.2015.1051534