Rights statement: This is the author’s version of a work that was accepted for publication in European Journal of Operational Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published inEuropean Journal of Operational Research, 255, 3, 2016 DOI: 10.1016/j.ejor.2016.05.001
Accepted author manuscript, 375 KB, PDF document
Available under license: CC BY-NC-ND: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Discrete representation of non-dominated sets in multi-objective linear programming
AU - Shao, Lizhen
AU - Ehrgott, Matthias
N1 - This is the author’s version of a work that was accepted for publication in European Journal of Operational Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published inEuropean Journal of Operational Research, 255, 3, 2016 DOI: 10.1016/j.ejor.2016.05.001
PY - 2016/12/16
Y1 - 2016/12/16
N2 - In this paper we address the problem of representing the continuous but non-convex set of nondominated points of a multi-objective linear programme by a finite subset of such points. We prove that a related decision problem is NP-complete. Moreover, we illustrate the drawbacks of the known global shooting, normal boundary intersection and normal constraint methods concerning the coverage error and uniformity level of the representation by examples. We propose a method which combines the global shooting and normal boundary intersection methods. By doing so, we overcome their limitations, but preserve their advantages. We prove that our method computesa set of evenly distributed non-dominated points for which the coverage error and the uniformity level can be guaranteed. We apply this method to an optimisation problem in radiation therapy and present illustrative results for some clinical cases. Finally, we present numerical results on randomly generated examples.
AB - In this paper we address the problem of representing the continuous but non-convex set of nondominated points of a multi-objective linear programme by a finite subset of such points. We prove that a related decision problem is NP-complete. Moreover, we illustrate the drawbacks of the known global shooting, normal boundary intersection and normal constraint methods concerning the coverage error and uniformity level of the representation by examples. We propose a method which combines the global shooting and normal boundary intersection methods. By doing so, we overcome their limitations, but preserve their advantages. We prove that our method computesa set of evenly distributed non-dominated points for which the coverage error and the uniformity level can be guaranteed. We apply this method to an optimisation problem in radiation therapy and present illustrative results for some clinical cases. Finally, we present numerical results on randomly generated examples.
KW - Multi-objective optimisation
KW - linear programming
KW - non-dominated set
KW - discrete representation
U2 - 10.1016/j.ejor.2016.05.001
DO - 10.1016/j.ejor.2016.05.001
M3 - Journal article
VL - 255
SP - 687
EP - 698
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 3
ER -