Benson's algorithm

Benson's algorithm, named after Harold Benson, is a method for solving multi-objective linear programming problems and vector linear programs. 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).

Dual algorithm

There is a dual variant of Benson's algorithm,[3] which is based on geometric duality[4] for multi-objective linear programs.

Implementations

Bensolve - a free VLP solver

www.bensolve.org

Inner

Link to github

gollark: Nanofurlongs.

gollark: I'm also the dictator, but my role is highly antimemetic.

gollark: I kind of want to join for non-evil* reasons.

gollark: Wow, an amazing 2 people.

gollark: What problems have cults here *ever* caused?

References

Harold P. Benson (1998). "An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem". Journal of Global Optimization. 13 (1): 1–24. doi:10.1023/A:1008215702611.
Andreas Löhne (2011). Vector Optimization with Infimum and Supremum. Springer. pp. 162–169. ISBN 9783642183508.
Ehrgott, Matthias; Löhne, Andreas; Shao, Lizhen (2011). "A dual variant of Benson's "outer approximation algorithm" for multiple objective linear programming". Journal of Global Optimization. 52 (4): 757–778. doi:10.1007/s10898-011-9709-y. ISSN 0925-5001.
Heyde, Frank; Löhne, Andreas (2008). "Geometric Duality in Multiple Objective Linear Programming" (PDF). SIAM Journal on Optimization. 19 (2): 836–845. doi:10.1137/060674831. ISSN 1052-6234.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Benson-1] Harold P. Benson (1998). "An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem". Journal of Global Optimization. 13 (1): 1–24. doi:10.1023/A:1008215702611.

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

[EhrgottLöhne2011-3] Ehrgott, Matthias; Löhne, Andreas; Shao, Lizhen (2011). "A dual variant of Benson's "outer approximation algorithm" for multiple objective linear programming". Journal of Global Optimization. 52 (4): 757–778. doi:10.1007/s10898-011-9709-y. ISSN 0925-5001.

[HeydeLöhne2008-4] Heyde, Frank; Löhne, Andreas (2008). "Geometric Duality in Multiple Objective Linear Programming" (PDF). SIAM Journal on Optimization. 19 (2): 836–845. doi:10.1137/060674831. ISSN 1052-6234.