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
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes
AU - Shao, Lizhen
AU - Ehrgott, Matthias
N1 - 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
PY - 2016/2
Y1 - 2016/2
N2 - 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.
AB - 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.
KW - linear multiplicative programming
KW - multi-objective optimization
KW - approximation algorithm
KW - nondominated point
U2 - 10.1080/02331934.2015.1051534
DO - 10.1080/02331934.2015.1051534
M3 - Journal article
VL - 65
SP - 415
EP - 431
JO - Optimization
JF - Optimization
SN - 0233-1934
IS - 2
ER -