Benson's algorithm

{{distinguish|text=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 multi-objective linear programming problems and vector linear programs. This works by finding the "efficient extreme points in the outcome set".{{cite journal | author = Harold P. Benson | year = 1998 | title = An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem | journal = Journal of Global Optimization | volume = 13 | issue = 1 | pages = 1–24 | doi = 10.1023/A:1008215702611 }} The primary concept in Benson's algorithm is to evaluate the upper image of the vector optimization problem by cutting planes.{{cite book|title=Vector Optimization with Infimum and Supremum|author=Andreas Löhne|publisher=Springer|year=2011|isbn=9783642183508|pages=162–169}}

Idea of algorithm

Consider a vector linear program

: $\min_C Px \; \text{ subject to } A x \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:\; A x \geq b\}$ . In particular, Benson's algorithm finds the extreme points of the set $P[S] + C$ , which is called upper image.

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,{{cite journal|last1=Ehrgott|first1=Matthias|last2=Löhne|first2=Andreas|last3=Shao|first3=Lizhen|title=A dual variant of Benson's "outer approximation algorithm" for multiple objective linear programming|journal=Journal of Global Optimization|volume=52|issue=4|year=2011|pages=757–778|issn=0925-5001|doi=10.1007/s10898-011-9709-y}} which is based on geometric duality{{cite journal|last1=Heyde|first1=Frank|last2=Löhne|first2=Andreas|title=Geometric Duality in Multiple Objective Linear Programming|journal=SIAM Journal on Optimization|volume=19|issue=2|year=2008|pages=836–845|issn=1052-6234|doi=10.1137/060674831|url=http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/06-15report.pdf}} for multi-objective linear programs.

Implementations

Bensolve - a free VLP solver

[http://bensolve.org www.bensolve.org]

Inner

[https://github.com/lcsirmaz/inner Link to github]

References

Category:Linear programming

Category:Optimization algorithms and methods