Benson's algorithm

Benson's algorithm, named after Harold Benson, is a method for solving linear vector optimization problems. 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 problem by cutting planes.

Idea of algorithm

Given a linear vector optimization problem

$\min Px\;{\text{ subject to }}x\in S$

for some $P\in \mathbb {R} ^{m\times n}$ and a nonempty polyhedron $S\subset \mathbb {R} ^{n}$, then Benson's algorithm will find the extreme points of the set $P[S]+\mathbb {R} _{+}^{m}$.