Multi-objective linear programming: Difference between revisions

Revision as of 18:46, 21 August 2017

Revision as of 18:48, 21 August 2017

Line 15:

Efficient points are frequently called ''efficient solutions''. This term is misleading because a single efficient point can be already obtained by solving one linear program, such as the linear program with the same feasible set and the objective function being the sum of the objectives of MOLP<ref name="Ehrgott2015">{{cite journal|last1=Ehrgott|first1=M.|title=Multicriteria Optimization|journal=Springer|year=2005|doi=10.1007/3-540-27659-9}}</ref>.

More recent references consider ''outcome set based'' solution concepts<ref name="HeydeLöhne2011">{{cite journal|last1=Heyde|first1=Frank|last2=Löhne|first2=Andreas|title=Solution concepts in vector optimization: a fresh look at an old story|journal=Optimization|volume=60|issue=12|year=2011|pages=1421–1440|issn=0233-1934|doi=10.1080/02331931003665108}}</ref> and corresponding algorithms<ref name="DauerSaleh1990">{{cite journal|last1=Dauer|first1=J.P.|last2=Saleh|first2=O.A.|title=Constructing the set of efficient objective values in multiple objective linear programs|journal=European Journal of Operational Research|volume=46|issue=3|year=1990|pages=358–365|issn=03772217|doi=10.1016/0377-2217(90)90011-Y}}</ref><ref name="Benson1998"></ref>. Assume MOLP is bounded, i.e. there is some <math>y \in \mathbb{R}^q</math> such that <math>y \leq Px</math> for all feasible <math>x</math>. A solution of MOLP is defined to be a finite subset <math>\bar S</math> of efficient points that carries a sufficient amount of information in order to describe the ''upper image'' of MOLP. Denoting by <math>S</math> the feasible set of MOLP by <math>S</math>, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in \mathbb{R}^n: y \geq Px,\;x\in S \}</math>. A formal definition of a solution <ref name="HeydeLöhne2011"></ref><ref name="Löhne2011">{{cite book|title=Vector Optimization with Infimum and Supremum|last1=Löhne|first1=Andreas|year=2011|issn=1867-8971|doi=10.1007/978-3-642-18351-5}}</ref> is as follows:

A finite set <math>\bar S</math> of efficient points is called ''solution'' to MOLP if