A dual variant of Benson’s outer approximation algorithm for multiple objective linear programming

Management Science

Text available via DOI:

https://doi.org/10.1007/s10898-011-9709-y
Final published version

Keywords

Multiobjective optimization , Vector optimization, Linear programming , Duality , Objective space , Outer approximation

View graph of relations

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

Published

Standard

A dual variant of Benson’s outer approximation algorithm for multiple objective linear programming. / Ehrgott, Matthias; Löhne, Andreas ; Shao, Lizhen.
In: Journal of Global Optimization, Vol. 52, No. 4, 04.2012, p. 757-778 .

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

Bibtex

@article{e04c1b6def074ba3ba8c10a963d3397f,

title = "A dual variant of Benson{\textquoteright}s outer approximation algorithm for multiple objective linear programming",

abstract = "Outcome space methods construct the set of nondominated points in the objective (outcome) space of a multiple objective linear programme. In this paper, we employ results from geometric duality theory for multiple objective linear programmes to derive a dual variant of Benson{\textquoteright}s “outer approximation algorithm” to solve multiobjective linear programmes in objective space. We also suggest some improvements of the original version of the algorithm and prove that solving the dual provides a weight set decomposition. We compare both algorithms on small illustrative and on practically relevant examples.",

keywords = "Multiobjective optimization , Vector optimization, Linear programming , Duality , Objective space , Outer approximation",

author = "Matthias Ehrgott and Andreas L{\"o}hne and Lizhen Shao",

year = "2012",

month = apr,

doi = "10.1007/s10898-011-9709-y",

language = "English",

volume = "52",

pages = "757--778 ",

journal = "Journal of Global Optimization",

issn = "0925-5001",

publisher = "Springer Netherlands",

number = "4",

}

RIS

TY - JOUR

T1 - A dual variant of Benson’s outer approximation algorithm for multiple objective linear programming

AU - Ehrgott, Matthias

AU - Löhne, Andreas

AU - Shao, Lizhen

PY - 2012/4

Y1 - 2012/4

N2 - Outcome space methods construct the set of nondominated points in the objective (outcome) space of a multiple objective linear programme. In this paper, we employ results from geometric duality theory for multiple objective linear programmes to derive a dual variant of Benson’s “outer approximation algorithm” to solve multiobjective linear programmes in objective space. We also suggest some improvements of the original version of the algorithm and prove that solving the dual provides a weight set decomposition. We compare both algorithms on small illustrative and on practically relevant examples.

AB - Outcome space methods construct the set of nondominated points in the objective (outcome) space of a multiple objective linear programme. In this paper, we employ results from geometric duality theory for multiple objective linear programmes to derive a dual variant of Benson’s “outer approximation algorithm” to solve multiobjective linear programmes in objective space. We also suggest some improvements of the original version of the algorithm and prove that solving the dual provides a weight set decomposition. We compare both algorithms on small illustrative and on practically relevant examples.

KW - Multiobjective optimization

KW - Vector optimization

KW - Linear programming

KW - Duality

KW - Objective space

KW - Outer approximation

U2 - 10.1007/s10898-011-9709-y

DO - 10.1007/s10898-011-9709-y

M3 - Journal article

VL - 52

SP - 757

EP - 778

JO - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 4

ER -

Research

Links

Text available via DOI:

Keywords