Benson's algorithm

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]

Consider a vector linear program

${\displaystyle \min _{C}Px\;{\text{ subject to }}Ax\geq b}${\displaystyle \min _{C}Px\;{\text{ subject to }}Ax\geq b}

for ${\displaystyle P\in \mathbb {R} ^{q\times n}}${\displaystyle P\in \mathbb {R} ^{q\times n}}, ${\displaystyle A\in \mathbb {R} ^{m\times n}}${\displaystyle A\in \mathbb {R} ^{m\times n}}, ${\displaystyle b\in \mathbb {R} ^{m}}${\displaystyle b\in \mathbb {R} ^{m}} and a polyhedral convex ordering cone ${\displaystyle C}${\displaystyle C} having nonempty interior and containing no lines. The feasible set is ${\displaystyle S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}}${\displaystyle S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}}. In particular, Benson's algorithm finds the extreme points of the set ${\displaystyle P[S]+C}${\displaystyle P[S]+C}, which is called upper image.^[2]

In case of ${\displaystyle C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}}${\displaystyle C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}}, one obtains the special case of a multi-objective linear program (multiobjective optimization).

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

Bensolve - a free VLP solver

• www.bensolve.org

Inner

• Link to github

• Linear programming
• Optimization algorithms and methods
• Applied mathematics stubs

• All stub articles