Benson's algorithm

From Wikipedia, the free encyclopedia

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".[1] The primary concept in Benson's algorithm is to evaluate the upper image of the vector optimization problem by cutting planes.[2]

Idea of algorithm

Summarize
Perspective

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).

Dual algorithm

There is a dual variant of Benson's algorithm,[3] which is based on geometric duality[4] for multi-objective linear programs.

Implementations

Bensolve - a free VLP solver

Inner

References

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.