Benson's algorithm

Not to be confused with Benson's algorithm (Go), a method to find the unconditionally alive stones in the game Go.

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

↑ 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. Retrieved September 21, 2013.
1 2 Andreas Löhne (2011). Vector Optimization with Infimum and Supremum. Springer. pp. 162–169. ISBN 9783642183508.

This article is issued from Wikipedia - version of the 9/3/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.