Benson's algorithm, named after Harold Benson, is a method for solving

multi-objective linear programming Multi-objective linear programming is a subarea of mathematical optimization. A multiple objective linear program (MOLP) is a linear program with more than one objective function. An MOLP is a special case of a vector linear program. Multi-objectiv ...

problems and vector linear programs. This works by finding the "efficient extreme points in the outcome set". The primary concept in Benson's algorithm is to evaluate the upper image of the

vector optimization Vector optimization is a subarea of mathematical optimization where optimization problems with a vector-valued objective functions are optimized with respect to a given partial ordering and subject to certain constraints. A multi-objective optim ...

problem by cutting planes.

Idea of algorithm

Consider a vector linear program :

\min_C Px \; \text  A x \geq b

for

P \in \mathbb^

A \in \mathbb^

b \in \mathbb^m

and a polyhedral convex ordering cone

C

having nonempty interior and containing no lines. The feasible set is

S=\

. In particular, Benson's algorithm finds the

extreme point In mathematics, an extreme point of a convex set S in a real or complex vector space is a point in S which does not lie in any open line segment joining two points of S. In linear programming problems, an extreme point is also called vertex ...

s of the set

P + C

, which is called upper image. In case of

C=\mathbb^q_+:=\

, one obtains the special case of a multi-objective linear program (

multiobjective optimization Multi-objective optimization (also known as multi-objective programming, vector optimization, multicriteria optimization, multiattribute optimization or Pareto optimization) is an area of multiple criteria decision making that is concerned with ...

Dual algorithm

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

Implementations

Bensolve - a free VLP solver
www.bensolve.org
Inner
Link to github

References

Linear programming Optimization algorithms and methods {{applied-math-stub