Benson's algorithm: Difference between revisions

Revision as of 17:00, 19 May 2012

Latest revision as of 20:03, 31 January 2019

(16 intermediate revisions by 9 users not shown)

Line 1:

{{distinguish2distinguish|text=[[Benson's algorithm (Go)]], a method to find the unconditionally alive stones in the game [[Go (game)|Go]]}}

'''Benson's algorithm''', named after [[Harold Benson]], is a method for solving [[multi-objective linear programming|linear]] [[multi-objectiveproblems optimization]]and problemsvector linear programs. This works by finding the "efficient extreme points in the outcome set".<ref name="Benson">{{cite doijournal | 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 }}</ref> The primary concept in Benson's algorithm is to evaluate the upper image of the [[vector optimization]] problem by [[cutting-plane method|cutting planes]].<ref name="Lohne">{{cite book|title=Vector Optimization with Infimum and Supremum|author=Andreas Löhne|publisher=Springer|year=2011|isbn=9783642183508|pages=162-169162–169}}</ref>

== Idea of algorithm ==

GivenConsider a linear vector optimizationlinear problemprogram

:<math>\minmin_C Px \; \text{ subject to } A x \ingeq Sb</math>

for some <math>P \in \mathbb{R}^{q \times n}</math>, <math>A \in \mathbb{R}^{m \times n}</math>, <math>b \in \mathbb{R}^m</math> and a [[polyhedral convex ordering cone <math>C</math> having nonempty]] [[polyhedron]]interior and containing no lines. The feasible set is <math>S=\{x \subsetin \mathbb{R}^n:\; A x \geq b\}</math>,. thenIn particular, Benson's algorithm will findfinds the [[extreme point]]s of the set <math>P[S] + \mathbb{R}^m_+C</math>, which is called upper image.<ref name="Lohne"/>

In case of <math>C=\mathbb{R}^q_+:=\{y \in \mathbb{R}^q : y_1 \geq 0,\dots, y_q \geq 0\}</math>, one obtains the special case of a multi-objective linear program ([[multiobjective optimization]]).

== References ==

{{Reflist}}

== Dual algorithm ==

There is a dual variant of Benson's algorithm,<ref name="EhrgottLöhne2011">{{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}}</ref> which is based on geometric duality<ref name="HeydeLöhne2008">{{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}}</ref> for multi-objective linear programs.

== Implementations ==

{{applied-math-stub}}

Bensolve - a free VLP solver

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

Inner

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

== References ==

{{Reflist}}

[[Category:Linear programming]]

[[Category:Optimization algorithms and methods]]

{{applied-math-stub}}