Benson's algorithm

From Wikipedia, the free encyclopedia

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

Given a linear vector optimization problem

$\min Px\;{\text{ subject to }}x\in S$

for some $P\in {\mathbb {R}}^{{m\times n}}$ and a nonempty polyhedron $S\subset {\mathbb {R}}^{n}$ , then Benson's algorithm will find the extreme points of the set $P[S]+{\mathbb {R}}_{+}^{m}$ .^[2]

Implementations

Matlab

Bensolve

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.
↑ 2.0 2.1 Andreas Löhne (2011). Vector Optimization with Infimum and Supremum. Springer. pp. 162–169. ISBN 9783642183508.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.