Benson's algorithm: Difference between revisions

Revision as of 14:10, 4 November 2018

Latest revision as of 20:03, 31 January 2019

Line 1:

{{distinguish|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]] problems and vector linear programs. This works by finding the "efficient extreme points in the outcome set".<ref name="Benson">{{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 | url = https://link.springer.com/article/10.1023%2FA%3A1008215702611 | format = | accessdate = September 21, 2013}}</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–169}}</ref>

== Idea of algorithm ==

Line 11:

== 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’sBenson'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 ==