Benson's algorithm: Difference between revisions

Revision as of 06:57, 18 April 2017

Revision as of 21:32, 25 April 2017

Line 1:

{{distinguish2|[[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 [[linear programming|linear]] [[multi-objective optimization]] 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-241–24 | doi = 10.1023/A:1008215702611 | url = http://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-169162–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’s “outer"outer approximation algorithm”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}}</ref> for multi-objective linear programs.

== Implementations ==

Line 21:

== References ==

{{Reflist}}

{{applied-math-stub}}

[[Category:Linear programming]]

[[Category:Optimization algorithms and methods]]

{{applied-math-stub}}