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]
Idea of algorithm
Consider a vector linear program
- [math]\displaystyle{ \min_C Px \; \text{ subject to } A x \geq b }[/math]
for [math]\displaystyle{ P \in \mathbb{R}^{q \times n} }[/math], [math]\displaystyle{ A \in \mathbb{R}^{m \times n} }[/math], [math]\displaystyle{ b \in \mathbb{R}^m }[/math] and a polyhedral convex ordering cone [math]\displaystyle{ C }[/math] having nonempty interior and containing no lines. The feasible set is [math]\displaystyle{ S=\{x \in \mathbb{R}^n:\; A x \geq b\} }[/math]. In particular, Benson's algorithm finds the extreme points of the set [math]\displaystyle{ P[S] + C }[/math], which is called upper image.[2]
In case of [math]\displaystyle{ C=\mathbb{R}^q_+:=\{y \in \mathbb{R}^q : y_1 \geq 0,\dots, y_q \geq 0\} }[/math], 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
- ↑ 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.
- ↑ 2.0 2.1 Andreas Löhne (2011). Vector Optimization with Infimum and Supremum. Springer. pp. 162–169. ISBN 9783642183508.
- ↑ Ehrgott, Matthias; Löhne, Andreas; Shao, Lizhen (2011). "A dual variant of Benson's "outer approximation algorithm" for multiple objective linear programming". Journal of Global Optimization 52 (4): 757–778. doi:10.1007/s10898-011-9709-y. ISSN 0925-5001.
- ↑ Heyde, Frank; Löhne, Andreas (2008). "Geometric Duality in Multiple Objective Linear Programming". SIAM Journal on Optimization 19 (2): 836–845. doi:10.1137/060674831. ISSN 1052-6234. http://webdoc.sub.gwdg.de/ebook/serien/e/reports_Halle-Wittenberg_math/06-15report.pdf.
 |  |
