Multi-objective linear programming - Revision history

John of Reading: /* Solution concepts */Typo fixing, replaced: can seen → can be seen

2024-01-11T10:09:09Z

Solution concepts: Typo fixing, replaced: can seen → can be seen

← Previous revision		Revision as of 10:09, 11 January 2024
Line 9:		Line 9:
	A feasible point <math>x</math> is called ''efficient'' if there is no feasible point <math>y</math> with <math>Px \leq Py</math>, <math>Px \neq Py</math>, where <math>\leq</math> denotes the component-wise ordering.		A feasible point <math>x</math> is called ''efficient'' if there is no feasible point <math>y</math> with <math>Px \leq Py</math>, <math>Px \neq Py</math>, where <math>\leq</math> denotes the component-wise ordering.

	Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points.....<ref name="EckerKouada1978">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Kouada\|first2=I. A.\|title=Finding all efficient extreme points for multiple objective linear programs\|journal=Mathematical Programming\|volume=14\|issue=1\|year=1978\|pages=249–261\|issn=0025-5610\|doi=10.1007/BF01588968\|s2cid=42726689}}</ref> There are also algorithms to determine the set of all maximal efficient faces.<ref name="EckerHegner1980">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Hegner\|first2=N. S.\|last3=Kouada\|first3=I. A.\|title=Generating all maximal efficient faces for multiple objective linear programs\|journal=Journal of Optimization Theory and Applications\|volume=30\|issue=3\|year=1980\|pages=353–381\|issn=0022-3239\|doi=10.1007/BF00935493\|s2cid=120455645}}</ref> Based on these goals, the set of all efficient (extreme) points can seen to be the solution of MOLP. This type of solution concept is called ''decision set based''.<ref name="Benson1998">{{cite journal\|title=An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem\|last1=Benson\|first1=Harold P.\|journal=Journal of Global Optimization\|volume=13\|issue=1\|year=1998\|pages=1–24\|issn=0925-5001\|doi=10.1023/A:1008215702611\|s2cid=45440728}}</ref> It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).		Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points.....<ref name="EckerKouada1978">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Kouada\|first2=I. A.\|title=Finding all efficient extreme points for multiple objective linear programs\|journal=Mathematical Programming\|volume=14\|issue=1\|year=1978\|pages=249–261\|issn=0025-5610\|doi=10.1007/BF01588968\|s2cid=42726689}}</ref> There are also algorithms to determine the set of all maximal efficient faces.<ref name="EckerHegner1980">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Hegner\|first2=N. S.\|last3=Kouada\|first3=I. A.\|title=Generating all maximal efficient faces for multiple objective linear programs\|journal=Journal of Optimization Theory and Applications\|volume=30\|issue=3\|year=1980\|pages=353–381\|issn=0022-3239\|doi=10.1007/BF00935493\|s2cid=120455645}}</ref> Based on these goals, the set of all efficient (extreme) points can be seen to be the solution of MOLP. This type of solution concept is called ''decision set based''.<ref name="Benson1998">{{cite journal\|title=An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem\|last1=Benson\|first1=Harold P.\|journal=Journal of Global Optimization\|volume=13\|issue=1\|year=1998\|pages=1–24\|issn=0925-5001\|doi=10.1023/A:1008215702611\|s2cid=45440728}}</ref> It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).

	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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|publisher=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</ref>		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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|publisher=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</ref>

Citation bot: Add: s2cid. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 101/162

2021-06-27T22:42:42Z

Add: s2cid. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 101/162

← Previous revision		Revision as of 22:42, 27 June 2021
Line 9:		Line 9:
	A feasible point <math>x</math> is called ''efficient'' if there is no feasible point <math>y</math> with <math>Px \leq Py</math>, <math>Px \neq Py</math>, where <math>\leq</math> denotes the component-wise ordering.		A feasible point <math>x</math> is called ''efficient'' if there is no feasible point <math>y</math> with <math>Px \leq Py</math>, <math>Px \neq Py</math>, where <math>\leq</math> denotes the component-wise ordering.

	Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points.....<ref name="EckerKouada1978">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Kouada\|first2=I. A.\|title=Finding all efficient extreme points for multiple objective linear programs\|journal=Mathematical Programming\|volume=14\|issue=1\|year=1978\|pages=249–261\|issn=0025-5610\|doi=10.1007/BF01588968}}</ref> There are also algorithms to determine the set of all maximal efficient faces.<ref name="EckerHegner1980">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Hegner\|first2=N. S.\|last3=Kouada\|first3=I. A.\|title=Generating all maximal efficient faces for multiple objective linear programs\|journal=Journal of Optimization Theory and Applications\|volume=30\|issue=3\|year=1980\|pages=353–381\|issn=0022-3239\|doi=10.1007/BF00935493}}</ref> Based on these goals, the set of all efficient (extreme) points can seen to be the solution of MOLP. This type of solution concept is called ''decision set based''.<ref name="Benson1998">{{cite journal\|title=An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem\|last1=Benson\|first1=Harold P.\|journal=Journal of Global Optimization\|volume=13\|issue=1\|year=1998\|pages=1–24\|issn=0925-5001\|doi=10.1023/A:1008215702611}}</ref> It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).		Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points.....<ref name="EckerKouada1978">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Kouada\|first2=I. A.\|title=Finding all efficient extreme points for multiple objective linear programs\|journal=Mathematical Programming\|volume=14\|issue=1\|year=1978\|pages=249–261\|issn=0025-5610\|doi=10.1007/BF01588968\|s2cid=42726689}}</ref> There are also algorithms to determine the set of all maximal efficient faces.<ref name="EckerHegner1980">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Hegner\|first2=N. S.\|last3=Kouada\|first3=I. A.\|title=Generating all maximal efficient faces for multiple objective linear programs\|journal=Journal of Optimization Theory and Applications\|volume=30\|issue=3\|year=1980\|pages=353–381\|issn=0022-3239\|doi=10.1007/BF00935493\|s2cid=120455645}}</ref> Based on these goals, the set of all efficient (extreme) points can seen to be the solution of MOLP. This type of solution concept is called ''decision set based''.<ref name="Benson1998">{{cite journal\|title=An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem\|last1=Benson\|first1=Harold P.\|journal=Journal of Global Optimization\|volume=13\|issue=1\|year=1998\|pages=1–24\|issn=0925-5001\|doi=10.1023/A:1008215702611\|s2cid=45440728}}</ref> It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).

	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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|publisher=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</ref>		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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|publisher=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</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\|url=http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/08-19report.pdf}}</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=0377-2217\|doi=10.1016/0377-2217(90)90011-Y}}</ref><ref name="Benson1998" /> 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, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in S: y \geq Px \}</math>. A formal definition of a solution <ref name="HeydeLöhne2011" /><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\|series=Vector Optimization\|isbn=978-3-642-18350-8}}</ref> is as follows:		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\|s2cid=54519405\|url=http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/08-19report.pdf}}</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=0377-2217\|doi=10.1016/0377-2217(90)90011-Y}}</ref><ref name="Benson1998" /> 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, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in S: y \geq Px \}</math>. A formal definition of a solution <ref name="HeydeLöhne2011" /><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\|series=Vector Optimization\|isbn=978-3-642-18350-8}}</ref> is as follows:

	A finite set <math>\bar S</math> of efficient points is called ''solution'' to MOLP if		A finite set <math>\bar S</math> of efficient points is called ''solution'' to MOLP if
Line 22:		Line 22:
	== Solution methods ==		== Solution methods ==

	Multiobjective variants of the [[simplex algorithm]] are used to compute decision set based solutions<ref name="EckerKouada1978" /><ref name="EckerHegner1980" /><ref name="ArmandMalivert1991">{{cite journal\|last1=Armand\|first1=P.\|last2=Malivert\|first2=C.\|title=Determination of the efficient set in multiobjective linear programming\|journal=Journal of Optimization Theory and Applications\|volume=70\|issue=3\|year=1991\|pages=467–489\|issn=0022-3239\|doi=10.1007/BF00941298\|citeseerx=10.1.1.161.9730}}</ref> and objective set based solutions.<ref name="RudloffUlus2016">{{cite journal\|last1=Rudloff\|first1=Birgit\|last2=Ulus\|first2=Firdevs\|last3=Vanderbei\|first3=Robert\|title=A parametric simplex algorithm for linear vector optimization problems\|journal=Mathematical Programming\|volume=163\|issue=1–2\|year=2016\|pages=213–242\|issn=0025-5610\|doi=10.1007/s10107-016-1061-z\|arxiv=1507.01895}}</ref>		Multiobjective variants of the [[simplex algorithm]] are used to compute decision set based solutions<ref name="EckerKouada1978" /><ref name="EckerHegner1980" /><ref name="ArmandMalivert1991">{{cite journal\|last1=Armand\|first1=P.\|last2=Malivert\|first2=C.\|title=Determination of the efficient set in multiobjective linear programming\|journal=Journal of Optimization Theory and Applications\|volume=70\|issue=3\|year=1991\|pages=467–489\|issn=0022-3239\|doi=10.1007/BF00941298\|citeseerx=10.1.1.161.9730\|s2cid=18407847}}</ref> and objective set based solutions.<ref name="RudloffUlus2016">{{cite journal\|last1=Rudloff\|first1=Birgit\|last2=Ulus\|first2=Firdevs\|last3=Vanderbei\|first3=Robert\|title=A parametric simplex algorithm for linear vector optimization problems\|journal=Mathematical Programming\|volume=163\|issue=1–2\|year=2016\|pages=213–242\|issn=0025-5610\|doi=10.1007/s10107-016-1061-z\|arxiv=1507.01895\|s2cid=13844342}}</ref>

	Objective set based solutions can be obtained by [[Benson's algorithm]].<ref name="Benson1998" /><ref name="LöhneWeißing2017">{{cite journal\|last1=Löhne\|first1=Andreas\|last2=Weißing\|first2=Benjamin\|title=The vector linear program solver Bensolve – notes on theoretical background\|journal=European Journal of Operational Research\|volume=260\|issue=3\|year=2017\|pages=807–813\|issn=0377-2217\|doi=10.1016/j.ejor.2016.02.039\|arxiv=1510.04823}}</ref>		Objective set based solutions can be obtained by [[Benson's algorithm]].<ref name="Benson1998" /><ref name="LöhneWeißing2017">{{cite journal\|last1=Löhne\|first1=Andreas\|last2=Weißing\|first2=Benjamin\|title=The vector linear program solver Bensolve – notes on theoretical background\|journal=European Journal of Operational Research\|volume=260\|issue=3\|year=2017\|pages=807–813\|issn=0377-2217\|doi=10.1016/j.ejor.2016.02.039\|arxiv=1510.04823\|s2cid=17267946}}</ref>

	== Related problem classes ==		== Related problem classes ==

	Multiobjective linear programming is equivalent to [[Polyhedral combinatorics\|polyhedral]] projection.<ref name="LöhneWeißing2016">{{cite journal\|last1=Löhne\|first1=Andreas\|last2=Weißing\|first2=Benjamin\|title=Equivalence between polyhedral projection, multiple objective linear programming and vector linear programming\|journal=Mathematical Methods of Operations Research\|volume=84\|issue=2\|year=2016\|pages=411–426\|issn=1432-2994\|doi=10.1007/s00186-016-0554-0\|arxiv=1507.00228}}</ref>		Multiobjective linear programming is equivalent to [[Polyhedral combinatorics\|polyhedral]] projection.<ref name="LöhneWeißing2016">{{cite journal\|last1=Löhne\|first1=Andreas\|last2=Weißing\|first2=Benjamin\|title=Equivalence between polyhedral projection, multiple objective linear programming and vector linear programming\|journal=Mathematical Methods of Operations Research\|volume=84\|issue=2\|year=2016\|pages=411–426\|issn=1432-2994\|doi=10.1007/s00186-016-0554-0\|arxiv=1507.00228\|s2cid=26137201}}</ref>

	== References ==		== References ==

Headbomb: /* Solution concepts */clean up, replaced: |journal=Springer → |publisher=Springer

2021-06-27T19:38:35Z

Solution concepts: clean up, replaced: |journal=Springer → |publisher=Springer

← Previous revision		Revision as of 19:38, 27 June 2021
Line 11:		Line 11:
	Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points.....<ref name="EckerKouada1978">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Kouada\|first2=I. A.\|title=Finding all efficient extreme points for multiple objective linear programs\|journal=Mathematical Programming\|volume=14\|issue=1\|year=1978\|pages=249–261\|issn=0025-5610\|doi=10.1007/BF01588968}}</ref> There are also algorithms to determine the set of all maximal efficient faces.<ref name="EckerHegner1980">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Hegner\|first2=N. S.\|last3=Kouada\|first3=I. A.\|title=Generating all maximal efficient faces for multiple objective linear programs\|journal=Journal of Optimization Theory and Applications\|volume=30\|issue=3\|year=1980\|pages=353–381\|issn=0022-3239\|doi=10.1007/BF00935493}}</ref> Based on these goals, the set of all efficient (extreme) points can seen to be the solution of MOLP. This type of solution concept is called ''decision set based''.<ref name="Benson1998">{{cite journal\|title=An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem\|last1=Benson\|first1=Harold P.\|journal=Journal of Global Optimization\|volume=13\|issue=1\|year=1998\|pages=1–24\|issn=0925-5001\|doi=10.1023/A:1008215702611}}</ref> It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).		Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points.....<ref name="EckerKouada1978">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Kouada\|first2=I. A.\|title=Finding all efficient extreme points for multiple objective linear programs\|journal=Mathematical Programming\|volume=14\|issue=1\|year=1978\|pages=249–261\|issn=0025-5610\|doi=10.1007/BF01588968}}</ref> There are also algorithms to determine the set of all maximal efficient faces.<ref name="EckerHegner1980">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Hegner\|first2=N. S.\|last3=Kouada\|first3=I. A.\|title=Generating all maximal efficient faces for multiple objective linear programs\|journal=Journal of Optimization Theory and Applications\|volume=30\|issue=3\|year=1980\|pages=353–381\|issn=0022-3239\|doi=10.1007/BF00935493}}</ref> Based on these goals, the set of all efficient (extreme) points can seen to be the solution of MOLP. This type of solution concept is called ''decision set based''.<ref name="Benson1998">{{cite journal\|title=An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem\|last1=Benson\|first1=Harold P.\|journal=Journal of Global Optimization\|volume=13\|issue=1\|year=1998\|pages=1–24\|issn=0925-5001\|doi=10.1023/A:1008215702611}}</ref> It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).

	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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|~~journal~~=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</ref>		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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|publisher=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</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\|url=http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/08-19report.pdf}}</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=0377-2217\|doi=10.1016/0377-2217(90)90011-Y}}</ref><ref name="Benson1998" /> 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, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in S: y \geq Px \}</math>. A formal definition of a solution <ref name="HeydeLöhne2011" /><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\|series=Vector Optimization\|isbn=978-3-642-18350-8}}</ref> is as follows:		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\|url=http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/08-19report.pdf}}</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=0377-2217\|doi=10.1016/0377-2217(90)90011-Y}}</ref><ref name="Benson1998" /> 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, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in S: y \geq Px \}</math>. A formal definition of a solution <ref name="HeydeLöhne2011" /><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\|series=Vector Optimization\|isbn=978-3-642-18350-8}}</ref> is as follows:

Yobot: Fix REFPUNCT + other minor fixes

2021-01-14T15:23:23Z

Fix REFPUNCT + other minor fixes

← Previous revision		Revision as of 15:23, 14 January 2021
Line 9:		Line 9:
	A feasible point <math>x</math> is called ''efficient'' if there is no feasible point <math>y</math> with <math>Px \leq Py</math>, <math>Px \neq Py</math>, where <math>\leq</math> denotes the component-wise ordering.		A feasible point <math>x</math> is called ''efficient'' if there is no feasible point <math>y</math> with <math>Px \leq Py</math>, <math>Px \neq Py</math>, where <math>\leq</math> denotes the component-wise ordering.

	Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points....<ref name="EckerKouada1978">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Kouada\|first2=I. A.\|title=Finding all efficient extreme points for multiple objective linear programs\|journal=Mathematical Programming\|volume=14\|issue=1\|year=1978\|pages=249–261\|issn=0025-5610\|doi=10.1007/BF01588968}}</ref>. There are also algorithms to determine the set of all maximal efficient faces.<ref name="EckerHegner1980">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Hegner\|first2=N. S.\|last3=Kouada\|first3=I. A.\|title=Generating all maximal efficient faces for multiple objective linear programs\|journal=Journal of Optimization Theory and Applications\|volume=30\|issue=3\|year=1980\|pages=353–381\|issn=0022-3239\|doi=10.1007/BF00935493}}</ref> Based on these goals, the set of all efficient (extreme) points can seen to be the solution of MOLP. This type of solution concept is called ''decision set based''.<ref name="Benson1998">{{cite journal\|title=An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem\|last1=Benson\|first1=Harold P.\|journal=Journal of Global Optimization\|volume=13\|issue=1\|year=1998\|pages=1–24\|issn=~~09255001~~\|doi=10.1023/A:1008215702611}}</ref> It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).		Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points.....<ref name="EckerKouada1978">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Kouada\|first2=I. A.\|title=Finding all efficient extreme points for multiple objective linear programs\|journal=Mathematical Programming\|volume=14\|issue=1\|year=1978\|pages=249–261\|issn=0025-5610\|doi=10.1007/BF01588968}}</ref> There are also algorithms to determine the set of all maximal efficient faces.<ref name="EckerHegner1980">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Hegner\|first2=N. S.\|last3=Kouada\|first3=I. A.\|title=Generating all maximal efficient faces for multiple objective linear programs\|journal=Journal of Optimization Theory and Applications\|volume=30\|issue=3\|year=1980\|pages=353–381\|issn=0022-3239\|doi=10.1007/BF00935493}}</ref> Based on these goals, the set of all efficient (extreme) points can seen to be the solution of MOLP. This type of solution concept is called ''decision set based''.<ref name="Benson1998">{{cite journal\|title=An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem\|last1=Benson\|first1=Harold P.\|journal=Journal of Global Optimization\|volume=13\|issue=1\|year=1998\|pages=1–24\|issn=0925-5001\|doi=10.1023/A:1008215702611}}</ref> It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).

	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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|journal=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</ref>		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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|journal=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</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\|url=http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/08-19report.pdf}}</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, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in S: y \geq Px \}</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\|series=Vector Optimization\|isbn=978-3-642-18350-8}}</ref> is as follows:		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\|url=http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/08-19report.pdf}}</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=0377-2217\|doi=10.1016/0377-2217(90)90011-Y}}</ref><ref name="Benson1998" /> 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, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in S: y \geq Px \}</math>. A formal definition of a solution <ref name="HeydeLöhne2011" /><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\|series=Vector Optimization\|isbn=978-3-642-18350-8}}</ref> is as follows:

	A finite set <math>\bar S</math> of efficient points is called ''solution'' to MOLP if		A finite set <math>\bar S</math> of efficient points is called ''solution'' to MOLP if
	<math>\operatorname{conv} P[\bar S] + \mathbb{R}^q_+ = \mathcal{P}</math> ("conv" denotes the convex hull).		<math>\operatorname{conv} P[\bar S] + \mathbb{R}^q_+ = \mathcal{P}</math> ("conv" denotes the convex hull).

	If MOLP is not bounded, a solution consists not only of points but of points and directions <ref name="Löhne2011"></~~ref~~><ref name="LöhneWeißing2017"></~~ref~~>		If MOLP is not bounded, a solution consists not only of points but of points and directions <ref name="Löhne2011" /><ref name="LöhneWeißing2017" />

	== Solution methods ==		== Solution methods ==

	Multiobjective variants of the [[simplex algorithm]] are used to compute decision set based solutions<ref name="EckerKouada1978"></~~ref~~><ref name="EckerHegner1980"></~~ref~~><ref name="ArmandMalivert1991">{{cite journal\|last1=Armand\|first1=P.\|last2=Malivert\|first2=C.\|title=Determination of the efficient set in multiobjective linear programming\|journal=Journal of Optimization Theory and Applications\|volume=70\|issue=3\|year=1991\|pages=467–489\|issn=0022-3239\|doi=10.1007/BF00941298\|citeseerx=10.1.1.161.9730}}</ref> and objective set based solutions.<ref name="RudloffUlus2016">{{cite journal\|last1=Rudloff\|first1=Birgit\|last2=Ulus\|first2=Firdevs\|last3=Vanderbei\|first3=Robert\|title=A parametric simplex algorithm for linear vector optimization problems\|journal=Mathematical Programming\|volume=163\|issue=1–2\|year=2016\|pages=213–242\|issn=0025-5610\|doi=10.1007/s10107-016-1061-z\|arxiv=1507.01895}}</ref>		Multiobjective variants of the [[simplex algorithm]] are used to compute decision set based solutions<ref name="EckerKouada1978" /><ref name="EckerHegner1980" /><ref name="ArmandMalivert1991">{{cite journal\|last1=Armand\|first1=P.\|last2=Malivert\|first2=C.\|title=Determination of the efficient set in multiobjective linear programming\|journal=Journal of Optimization Theory and Applications\|volume=70\|issue=3\|year=1991\|pages=467–489\|issn=0022-3239\|doi=10.1007/BF00941298\|citeseerx=10.1.1.161.9730}}</ref> and objective set based solutions.<ref name="RudloffUlus2016">{{cite journal\|last1=Rudloff\|first1=Birgit\|last2=Ulus\|first2=Firdevs\|last3=Vanderbei\|first3=Robert\|title=A parametric simplex algorithm for linear vector optimization problems\|journal=Mathematical Programming\|volume=163\|issue=1–2\|year=2016\|pages=213–242\|issn=0025-5610\|doi=10.1007/s10107-016-1061-z\|arxiv=1507.01895}}</ref>

	Objective set based solutions can be obtained by [[Benson's algorithm]].<ref name="Benson1998"></~~ref~~><ref name="LöhneWeißing2017">{{cite journal\|last1=Löhne\|first1=Andreas\|last2=Weißing\|first2=Benjamin\|title=The vector linear program solver Bensolve – notes on theoretical background\|journal=European Journal of Operational Research\|volume=260\|issue=3\|year=2017\|pages=807–813\|issn=~~03772217~~\|doi=10.1016/j.ejor.2016.02.039\|arxiv=1510.04823}}</ref>		Objective set based solutions can be obtained by [[Benson's algorithm]].<ref name="Benson1998" /><ref name="LöhneWeißing2017">{{cite journal\|last1=Löhne\|first1=Andreas\|last2=Weißing\|first2=Benjamin\|title=The vector linear program solver Bensolve – notes on theoretical background\|journal=European Journal of Operational Research\|volume=260\|issue=3\|year=2017\|pages=807–813\|issn=0377-2217\|doi=10.1016/j.ejor.2016.02.039\|arxiv=1510.04823}}</ref>

	== Related problem classes ==		== Related problem classes ==

WikiCleanerBot: v2.04b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

2020-12-18T11:53:44Z

v2.04b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

← Previous revision		Revision as of 11:53, 18 December 2020
Line 9:		Line 9:
	A feasible point <math>x</math> is called ''efficient'' if there is no feasible point <math>y</math> with <math>Px \leq Py</math>, <math>Px \neq Py</math>, where <math>\leq</math> denotes the component-wise ordering.		A feasible point <math>x</math> is called ''efficient'' if there is no feasible point <math>y</math> with <math>Px \leq Py</math>, <math>Px \neq Py</math>, where <math>\leq</math> denotes the component-wise ordering.

	Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points....<ref name="EckerKouada1978">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Kouada\|first2=I. A.\|title=Finding all efficient extreme points for multiple objective linear programs\|journal=Mathematical Programming\|volume=14\|issue=1\|year=1978\|pages=249–261\|issn=0025-5610\|doi=10.1007/BF01588968}}</ref>. There are also algorithms to determine the set of all maximal efficient faces <ref name="EckerHegner1980">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Hegner\|first2=N. S.\|last3=Kouada\|first3=I. A.\|title=Generating all maximal efficient faces for multiple objective linear programs\|journal=Journal of Optimization Theory and Applications\|volume=30\|issue=3\|year=1980\|pages=353–381\|issn=0022-3239\|doi=10.1007/BF00935493}}</ref>. Based on these goals, the set of all efficient (extreme) points can seen to be the solution of MOLP. This type of solution concept is called ''decision set based''<ref name="Benson1998">{{cite journal\|title=An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem\|last1=Benson\|first1=Harold P.\|journal=Journal of Global Optimization\|volume=13\|issue=1\|year=1998\|pages=1–24\|issn=09255001\|doi=10.1023/A:1008215702611}}</ref>. It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).		Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points....<ref name="EckerKouada1978">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Kouada\|first2=I. A.\|title=Finding all efficient extreme points for multiple objective linear programs\|journal=Mathematical Programming\|volume=14\|issue=1\|year=1978\|pages=249–261\|issn=0025-5610\|doi=10.1007/BF01588968}}</ref>. There are also algorithms to determine the set of all maximal efficient faces.<ref name="EckerHegner1980">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Hegner\|first2=N. S.\|last3=Kouada\|first3=I. A.\|title=Generating all maximal efficient faces for multiple objective linear programs\|journal=Journal of Optimization Theory and Applications\|volume=30\|issue=3\|year=1980\|pages=353–381\|issn=0022-3239\|doi=10.1007/BF00935493}}</ref> Based on these goals, the set of all efficient (extreme) points can seen to be the solution of MOLP. This type of solution concept is called ''decision set based''.<ref name="Benson1998">{{cite journal\|title=An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem\|last1=Benson\|first1=Harold P.\|journal=Journal of Global Optimization\|volume=13\|issue=1\|year=1998\|pages=1–24\|issn=09255001\|doi=10.1023/A:1008215702611}}</ref> It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).

	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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|journal=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</ref>.		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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|journal=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</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\|url=http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/08-19report.pdf}}</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, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in S: y \geq Px \}</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\|series=Vector Optimization\|isbn=978-3-642-18350-8}}</ref> is as follows:		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\|url=http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/08-19report.pdf}}</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, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in S: y \geq Px \}</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\|series=Vector Optimization\|isbn=978-3-642-18350-8}}</ref> is as follows:

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

4.53.61.66: fix wrong word

2020-02-22T00:17:29Z

fix wrong word

← Previous revision		Revision as of 00:17, 22 February 2020
Line 1:		Line 1:
	'''Multi-objective linear programming''' is a subarea of [[mathematical optimization]]. A multiple objective linear program (MOLP) is a [[linear program]] with more than one objective function. An MOLP is a special case of a [[vector linear program]]. Multi-~~objection~~ linear programming is also a subarea of [[Multi-objective optimization]].		'''Multi-objective linear programming''' is a subarea of [[mathematical optimization]]. A multiple objective linear program (MOLP) is a [[linear program]] with more than one objective function. An MOLP is a special case of a [[vector linear program]]. Multi-objective linear programming is also a subarea of [[Multi-objective optimization]].

	== Problem formulation ==		== Problem formulation ==

MrOllie: Reverted 1 edit by 129.15.133.239 (talk): Spammer (TW)

2019-10-26T16:32:26Z

Reverted 1 edit by 129.15.133.239 (talk): Spammer (TW)

← Previous revision		Revision as of 16:32, 26 October 2019
Line 1:		Line 1:
	'''Multi-objective linear programming''' <ref name="GOLBO16">{{Cite book \|url=http://cdn.intechopen.com/pdfs-wm/53332.pdf \|doi=10.5772/66.399\| isbn=9781466557529\|title=Beamforming in Wireless Networks\|year=2016\|last1=Golbon-Haghighi\|first1=M.H. \|journal=InTech Open\| pages=163-199}}</ref>is a subarea of [[mathematical optimization]]. A multiple objective linear program (MOLP) is a [[linear program]] with more than one objective function. An MOLP is a special case of a [[vector linear program]]. Multi-objection linear programming is also a subarea of [[Multi-objective optimization]].		'''Multi-objective linear programming''' is a subarea of [[mathematical optimization]]. A multiple objective linear program (MOLP) is a [[linear program]] with more than one objective function. An MOLP is a special case of a [[vector linear program]]. Multi-objection linear programming is also a subarea of [[Multi-objective optimization]].

	== Problem formulation ==		== Problem formulation ==

129.15.133.239 at 16:25, 26 October 2019

2019-10-26T16:25:04Z

← Previous revision		Revision as of 16:25, 26 October 2019
Line 1:		Line 1:
	'''Multi-objective linear programming''' is a subarea of [[mathematical optimization]]. A multiple objective linear program (MOLP) is a [[linear program]] with more than one objective function. An MOLP is a special case of a [[vector linear program]]. Multi-objection linear programming is also a subarea of [[Multi-objective optimization]].		'''Multi-objective linear programming''' <ref name="GOLBO16">{{Cite book \|url=http://cdn.intechopen.com/pdfs-wm/53332.pdf \|doi=10.5772/66.399\| isbn=9781466557529\|title=Beamforming in Wireless Networks\|year=2016\|last1=Golbon-Haghighi\|first1=M.H. \|journal=InTech Open\| pages=163-199}}</ref>is a subarea of [[mathematical optimization]]. A multiple objective linear program (MOLP) is a [[linear program]] with more than one objective function. An MOLP is a special case of a [[vector linear program]]. Multi-objection linear programming is also a subarea of [[Multi-objective optimization]].

	== Problem formulation ==		== Problem formulation ==

Marnie Hawes: Added free to read link in citations with OAbot #oabot

2019-09-18T06:28:34Z

Added free to read link in citations with OAbot #oabot

← Previous revision		Revision as of 06:28, 18 September 2019
Line 13:		Line 13:
	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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|journal=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</ref>.		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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|journal=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</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, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in S: y \geq Px \}</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\|series=Vector Optimization\|isbn=978-3-642-18350-8}}</ref> is as follows:		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\|url=http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/08-19report.pdf}}</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, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in S: y \geq Px \}</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\|series=Vector Optimization\|isbn=978-3-642-18350-8}}</ref> is as follows:

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

Citation bot: Alter: template type, issue. Add: series, citeseerx, isbn. Formatted dashes. | You can use this bot yourself. Report bugs here. | User-activated.

2019-02-15T08:24:41Z

Alter: template type, issue. Add: series, citeseerx, isbn. Formatted dashes. | You can use this bot yourself. Report bugs here. | User-activated.

← Previous revision		Revision as of 08:24, 15 February 2019
Line 11:		Line 11:
	Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points....<ref name="EckerKouada1978">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Kouada\|first2=I. A.\|title=Finding all efficient extreme points for multiple objective linear programs\|journal=Mathematical Programming\|volume=14\|issue=1\|year=1978\|pages=249–261\|issn=0025-5610\|doi=10.1007/BF01588968}}</ref>. There are also algorithms to determine the set of all maximal efficient faces <ref name="EckerHegner1980">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Hegner\|first2=N. S.\|last3=Kouada\|first3=I. A.\|title=Generating all maximal efficient faces for multiple objective linear programs\|journal=Journal of Optimization Theory and Applications\|volume=30\|issue=3\|year=1980\|pages=353–381\|issn=0022-3239\|doi=10.1007/BF00935493}}</ref>. Based on these goals, the set of all efficient (extreme) points can seen to be the solution of MOLP. This type of solution concept is called ''decision set based''<ref name="Benson1998">{{cite journal\|title=An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem\|last1=Benson\|first1=Harold P.\|journal=Journal of Global Optimization\|volume=13\|issue=1\|year=1998\|pages=1–24\|issn=09255001\|doi=10.1023/A:1008215702611}}</ref>. It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).		Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points....<ref name="EckerKouada1978">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Kouada\|first2=I. A.\|title=Finding all efficient extreme points for multiple objective linear programs\|journal=Mathematical Programming\|volume=14\|issue=1\|year=1978\|pages=249–261\|issn=0025-5610\|doi=10.1007/BF01588968}}</ref>. There are also algorithms to determine the set of all maximal efficient faces <ref name="EckerHegner1980">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Hegner\|first2=N. S.\|last3=Kouada\|first3=I. A.\|title=Generating all maximal efficient faces for multiple objective linear programs\|journal=Journal of Optimization Theory and Applications\|volume=30\|issue=3\|year=1980\|pages=353–381\|issn=0022-3239\|doi=10.1007/BF00935493}}</ref>. Based on these goals, the set of all efficient (extreme) points can seen to be the solution of MOLP. This type of solution concept is called ''decision set based''<ref name="Benson1998">{{cite journal\|title=An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem\|last1=Benson\|first1=Harold P.\|journal=Journal of Global Optimization\|volume=13\|issue=1\|year=1998\|pages=1–24\|issn=09255001\|doi=10.1023/A:1008215702611}}</ref>. It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).

	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>.		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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|journal=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</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, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in S: y \geq Px \}</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:		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, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in S: y \geq Px \}</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\|series=Vector Optimization\|isbn=978-3-642-18350-8}}</ref> is as follows:

	A finite set <math>\bar S</math> of efficient points is called ''solution'' to MOLP if		A finite set <math>\bar S</math> of efficient points is called ''solution'' to MOLP if
Line 22:		Line 22:
	== Solution methods ==		== Solution methods ==

	Multiobjective variants of the [[simplex algorithm]] are used to compute decision set based solutions<ref name="EckerKouada1978"></ref><ref name="EckerHegner1980"></ref><ref name="ArmandMalivert1991">{{cite journal\|last1=Armand\|first1=P.\|last2=Malivert\|first2=C.\|title=Determination of the efficient set in multiobjective linear programming\|journal=Journal of Optimization Theory and Applications\|volume=70\|issue=3\|year=1991\|pages=467–489\|issn=0022-3239\|doi=10.1007/BF00941298}}</ref> and objective set based solutions.<ref name="RudloffUlus2016">{{cite journal\|last1=Rudloff\|first1=Birgit\|last2=Ulus\|first2=Firdevs\|last3=Vanderbei\|first3=Robert\|title=A parametric simplex algorithm for linear vector optimization problems\|journal=Mathematical Programming\|volume=163\|issue=~~1-2~~\|year=2016\|pages=213–242\|issn=0025-5610\|doi=10.1007/s10107-016-1061-z\|arxiv=1507.01895}}</ref>		Multiobjective variants of the [[simplex algorithm]] are used to compute decision set based solutions<ref name="EckerKouada1978"></ref><ref name="EckerHegner1980"></ref><ref name="ArmandMalivert1991">{{cite journal\|last1=Armand\|first1=P.\|last2=Malivert\|first2=C.\|title=Determination of the efficient set in multiobjective linear programming\|journal=Journal of Optimization Theory and Applications\|volume=70\|issue=3\|year=1991\|pages=467–489\|issn=0022-3239\|doi=10.1007/BF00941298\|citeseerx=10.1.1.161.9730}}</ref> and objective set based solutions.<ref name="RudloffUlus2016">{{cite journal\|last1=Rudloff\|first1=Birgit\|last2=Ulus\|first2=Firdevs\|last3=Vanderbei\|first3=Robert\|title=A parametric simplex algorithm for linear vector optimization problems\|journal=Mathematical Programming\|volume=163\|issue=1–2\|year=2016\|pages=213–242\|issn=0025-5610\|doi=10.1007/s10107-016-1061-z\|arxiv=1507.01895}}</ref>

	Objective set based solutions can be obtained by [[Benson's algorithm]].<ref name="Benson1998"></ref><ref name="LöhneWeißing2017">{{cite journal\|last1=Löhne\|first1=Andreas\|last2=Weißing\|first2=Benjamin\|title=The vector linear program solver Bensolve – notes on theoretical background\|journal=European Journal of Operational Research\|volume=260\|issue=3\|year=2017\|pages=807–813\|issn=03772217\|doi=10.1016/j.ejor.2016.02.039\|arxiv=1510.04823}}</ref>		Objective set based solutions can be obtained by [[Benson's algorithm]].<ref name="Benson1998"></ref><ref name="LöhneWeißing2017">{{cite journal\|last1=Löhne\|first1=Andreas\|last2=Weißing\|first2=Benjamin\|title=The vector linear program solver Bensolve – notes on theoretical background\|journal=European Journal of Operational Research\|volume=260\|issue=3\|year=2017\|pages=807–813\|issn=03772217\|doi=10.1016/j.ejor.2016.02.039\|arxiv=1510.04823}}</ref>

← Previous revision		Revision as of 19:38, 27 June 2021
Line 11:		Line 11:
	Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points.....<ref name="EckerKouada1978">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Kouada\|first2=I. A.\|title=Finding all efficient extreme points for multiple objective linear programs\|journal=Mathematical Programming\|volume=14\|issue=1\|year=1978\|pages=249–261\|issn=0025-5610\|doi=10.1007/BF01588968}}</ref> There are also algorithms to determine the set of all maximal efficient faces.<ref name="EckerHegner1980">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Hegner\|first2=N. S.\|last3=Kouada\|first3=I. A.\|title=Generating all maximal efficient faces for multiple objective linear programs\|journal=Journal of Optimization Theory and Applications\|volume=30\|issue=3\|year=1980\|pages=353–381\|issn=0022-3239\|doi=10.1007/BF00935493}}</ref> Based on these goals, the set of all efficient (extreme) points can seen to be the solution of MOLP. This type of solution concept is called ''decision set based''.<ref name="Benson1998">{{cite journal\|title=An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem\|last1=Benson\|first1=Harold P.\|journal=Journal of Global Optimization\|volume=13\|issue=1\|year=1998\|pages=1–24\|issn=0925-5001\|doi=10.1023/A:1008215702611}}</ref> It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).		Often in the literature, the aim in multiple objective linear programming is to compute the set of all efficient extremal points.....<ref name="EckerKouada1978">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Kouada\|first2=I. A.\|title=Finding all efficient extreme points for multiple objective linear programs\|journal=Mathematical Programming\|volume=14\|issue=1\|year=1978\|pages=249–261\|issn=0025-5610\|doi=10.1007/BF01588968}}</ref> There are also algorithms to determine the set of all maximal efficient faces.<ref name="EckerHegner1980">{{cite journal\|last1=Ecker\|first1=J. G.\|last2=Hegner\|first2=N. S.\|last3=Kouada\|first3=I. A.\|title=Generating all maximal efficient faces for multiple objective linear programs\|journal=Journal of Optimization Theory and Applications\|volume=30\|issue=3\|year=1980\|pages=353–381\|issn=0022-3239\|doi=10.1007/BF00935493}}</ref> Based on these goals, the set of all efficient (extreme) points can seen to be the solution of MOLP. This type of solution concept is called ''decision set based''.<ref name="Benson1998">{{cite journal\|title=An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem\|last1=Benson\|first1=Harold P.\|journal=Journal of Global Optimization\|volume=13\|issue=1\|year=1998\|pages=1–24\|issn=0925-5001\|doi=10.1023/A:1008215702611}}</ref> It is not compatible with an optimal solution of a linear program but rather parallels the set of all optimal solutions of a linear program (which is more difficult to determine).

	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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|~~journal~~=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</ref>		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 book\|last1=Ehrgott\|first1=M.\|title=Multicriteria Optimization\|publisher=Springer\|year=2005\|doi=10.1007/3-540-27659-9\|isbn=978-3-540-21398-7\|citeseerx=10.1.1.360.5223}}</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\|url=http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/08-19report.pdf}}</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=0377-2217\|doi=10.1016/0377-2217(90)90011-Y}}</ref><ref name="Benson1998" /> 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, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in S: y \geq Px \}</math>. A formal definition of a solution <ref name="HeydeLöhne2011" /><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\|series=Vector Optimization\|isbn=978-3-642-18350-8}}</ref> is as follows:		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\|url=http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/08-19report.pdf}}</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=0377-2217\|doi=10.1016/0377-2217(90)90011-Y}}</ref><ref name="Benson1998" /> 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, the ''upper image'' of MOLP is the set <math>\mathcal{P}:=P[ S] + \mathbb{R}^q_+ := \{ y \in \mathbb{R}^q:\; \exists x \in S: y \geq Px \}</math>. A formal definition of a solution <ref name="HeydeLöhne2011" /><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\|series=Vector Optimization\|isbn=978-3-642-18350-8}}</ref> is as follows: