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]
Contents
Idea of algorithm[edit]
Consider a vector linear program
for ,
,
and a polyhedral convex ordering cone
having nonempty interior and containing no lines. The feasible set is
. In particular, Benson's algorithm finds the extreme points of the set
, which is called upper image.[2]
In case of , one obtains the special case of a multi-objective linear program (multiobjective optimization).
Implementations[edit]
Bensolve - a free VLP solver (C programming language)[edit]
References[edit]
- ^ 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.
- ^ 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. |
