Benson's algorithm

Benson's algorithm, named after Harold Benson, is a method for solving linear multi-objective optimization problems. 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

Consider a vector linear program

$\min_C Px \; \text{ subject to } A x \geq b$

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

In case of $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).

Implementations

Bensolve - a free VLP solver (C programming language)

• www.bensolve.org

References

1. Harold P. Benson (1998). "An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple Objective Linear Programming Problem". Journal of Global Optimization 13 (1): 1–24. doi:10.1023/A:1008215702611. Retrieved September 21, 2013.
2. Andreas Löhne (2011). Vector Optimization with Infimum and Supremum. Springer. pp. 162–169. ISBN 9783642183508.