Benson's algorithm: Difference between revisions

Content deleted Content added

Inline

Revision as of 09:40, 4 October 2014

Benson's algorithm, named after Harold Benson, is a method for solving linear multi-objective optimization problems. This works by finding the "efficient extreme points in the outcome set".^[1] The primary concept in Benson's algorithm is to evaluate the upper image of the vector optimization problem by cutting planes.^[2]

Idea of algorithm

Consider a vector linear program

\min _{C}Px\;{\text{ subject to }}Ax\geq b

for $P\in \mathbb {R} ^{q\times n}$ , $A\in \mathbb {R} ^{m\times n}$ , $b\in \mathbb {R} ^{m}$ and a polyhedral convex ordering cone $C$ having nonempty interior and containing no lines. The feasible set is $S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}$ . In particular, Benson's algorithm finds the extreme points of the set $P[S]+C$ , which is called upper image.^[2]

In case of $C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}$ , one obtains the special case of a multi-objective linear program (multiobjective optimization).

Implementations

Bensolve - a free VLP solver (C programming language)

www.bensolve.org

References

^ Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1023/A:1008215702611, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1023/A:1008215702611 instead.
^ ^a ^b Andreas Löhne (2011). Vector Optimization with Infimum and Supremum. Springer. pp. 162–169. ISBN 9783642183508.

This applied mathematics–related article is a stub. You can help Wikipedia by expanding it.

[Benson-1] Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1023/A:1008215702611, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1023/A:1008215702611 instead.

[Lohne-2] Andreas Löhne (2011). Vector Optimization with Infimum and Supremum. Springer. pp. 162–169. ISBN 9783642183508.

[1]

[2]

@@ Line 6: / Line 6: @@
 Consider a vector linear program
 :<math>\min_C Px \; \text{ subject to }  A x \geq b</math>
-for <math>P \in \mathbb{R}^{q \times n}</math>, <math>A \in \mathbb{R}^{m \times n}</math>, <math>b \in \mathbb{R}^m</math> and a polyhedral convex ordering cone <math>C</math> having nonempty interior and containing no lines. The feasible set is <math>S=\{x \in \mathbb{R}^n:\; A x \geq b\}</math>. In particular, Benson's algorithm finds the [[extreme point]]s of the set <math>P[S] + C</math>.<ref name="Lohne"/>
+for <math>P \in \mathbb{R}^{q \times n}</math>, <math>A \in \mathbb{R}^{m \times n}</math>, <math>b \in \mathbb{R}^m</math> and a polyhedral convex ordering cone <math>C</math> having nonempty interior and containing no lines. The feasible set is <math>S=\{x \in \mathbb{R}^n:\; A x \geq b\}</math>. In particular, Benson's algorithm finds the [[extreme point]]s of the set <math>P[S] + C</math>, which is called upper image.<ref name="Lohne"/>
 In case of <math>C=\mathbb{R}^q_+:=\{y \in \mathbb{R}^q : y_1 \geq 0,\dots, y_q \geq 0\}</math>, one obtains the special case of a multi-objective linear program ([[multiobjective optimization]]).