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: Well, presumably you'll want to be able to define separate 3D objects, you see.

gollark: You could do it, it would just be very bad.

gollark: Look, if you want to know how to use a thing *read the docs* at https://wiki.computercraft.cc.

gollark: Brain level 10000.

gollark: You also clearly don't know of the FS API (which is understandable), but the more problematic problem is that you apparently can't actually documentation.

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.