Home > Research > Publications & Outputs > Approximating the nondominated set of an MOLP b...

Research

Links

Text available via DOI:

Keywords

View graph of relations

Approximating the nondominated set of an MOLP by approximately solving its dual problem

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Approximating the nondominated set of an MOLP by approximately solving its dual problem. / Shao, Lizhen; Ehrgott, Matthias.
In: Mathematical Methods of Operational Research, Vol. 68, No. 3, 12.2008, p. 469-492.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Shao, L & Ehrgott, M 2008, 'Approximating the nondominated set of an MOLP by approximately solving its dual problem', Mathematical Methods of Operational Research, vol. 68, no. 3, pp. 469-492. https://doi.org/10.1007/s00186-007-0194-5

APA

Shao, L., & Ehrgott, M. (2008). Approximating the nondominated set of an MOLP by approximately solving its dual problem. Mathematical Methods of Operational Research, 68(3), 469-492. https://doi.org/10.1007/s00186-007-0194-5

Vancouver

Shao L, Ehrgott M. Approximating the nondominated set of an MOLP by approximately solving its dual problem. Mathematical Methods of Operational Research. 2008 Dec;68(3):469-492. doi: 10.1007/s00186-007-0194-5

Author

Shao, Lizhen ; Ehrgott, Matthias. / Approximating the nondominated set of an MOLP by approximately solving its dual problem. In: Mathematical Methods of Operational Research. 2008 ; Vol. 68, No. 3. pp. 469-492.

Bibtex

@article{4e0dc94e23494d39bdd7466c9445d4e0,
title = "Approximating the nondominated set of an MOLP by approximately solving its dual problem",
abstract = "The geometric duality theory of Heyde and Lohne (2006) defines a dual to a multiple objective linear programme (MOLP). In objective space, the primal problem can be solved by Benson{\textquoteright}s outer approximation method (Benson, 1998a,b) while the dual problem can be solved by a dual variant of Benson{\textquoteright}s algorithm (Ehrgott et al., 2007). Duality theory then assures that it is possible to find the nondominated set of the primal MOLP by solving its dual. In this paper, we propose an algorithm to solve the dual MOLP approximately but within specified tolerance. This approximate solution set can be used to calculate an approximation of the nondominated set of the primal. We show that this set is an ε-nondominated set of the original primal MOLP and provide numerical evidence that this approach can be faster than solving the primal MOLP approximately.",
keywords = "Multiobjective linear programming , Geometric duality , ε-nondominated set , Approximation , Radiotheraphy treatment planning",
author = "Lizhen Shao and Matthias Ehrgott",
year = "2008",
month = dec,
doi = "10.1007/s00186-007-0194-5",
language = "English",
volume = "68",
pages = "469--492",
journal = "Mathematical Methods of Operational Research",
issn = "1432-2994",
publisher = "Physica-Verlag",
number = "3",

}

RIS

TY - JOUR

T1 - Approximating the nondominated set of an MOLP by approximately solving its dual problem

AU - Shao, Lizhen

AU - Ehrgott, Matthias

PY - 2008/12

Y1 - 2008/12

N2 - The geometric duality theory of Heyde and Lohne (2006) defines a dual to a multiple objective linear programme (MOLP). In objective space, the primal problem can be solved by Benson’s outer approximation method (Benson, 1998a,b) while the dual problem can be solved by a dual variant of Benson’s algorithm (Ehrgott et al., 2007). Duality theory then assures that it is possible to find the nondominated set of the primal MOLP by solving its dual. In this paper, we propose an algorithm to solve the dual MOLP approximately but within specified tolerance. This approximate solution set can be used to calculate an approximation of the nondominated set of the primal. We show that this set is an ε-nondominated set of the original primal MOLP and provide numerical evidence that this approach can be faster than solving the primal MOLP approximately.

AB - The geometric duality theory of Heyde and Lohne (2006) defines a dual to a multiple objective linear programme (MOLP). In objective space, the primal problem can be solved by Benson’s outer approximation method (Benson, 1998a,b) while the dual problem can be solved by a dual variant of Benson’s algorithm (Ehrgott et al., 2007). Duality theory then assures that it is possible to find the nondominated set of the primal MOLP by solving its dual. In this paper, we propose an algorithm to solve the dual MOLP approximately but within specified tolerance. This approximate solution set can be used to calculate an approximation of the nondominated set of the primal. We show that this set is an ε-nondominated set of the original primal MOLP and provide numerical evidence that this approach can be faster than solving the primal MOLP approximately.

KW - Multiobjective linear programming

KW - Geometric duality

KW - ε-nondominated set

KW - Approximation

KW - Radiotheraphy treatment planning

U2 - 10.1007/s00186-007-0194-5

DO - 10.1007/s00186-007-0194-5

M3 - Journal article

VL - 68

SP - 469

EP - 492

JO - Mathematical Methods of Operational Research

JF - Mathematical Methods of Operational Research

SN - 1432-2994

IS - 3

ER -