Benson's algorithm
Benson's algorithm, named after Harold Benson, is a method for solving multi-objective linear programming problems and vector linear programs.
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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
edit edit sourceConsider a vector linear program
- minCPx subject to Ax≥b
for P∈ℝq×n, A∈ℝm×n, b∈ℝm and a polyhedral convex ordering cone C having nonempty interior and containing no lines. The feasible set is S={x∈ℝn:Ax≥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=ℝ+q:={y∈ℝq:y1≥0,…,yq≥0}, one obtains the special case of a multi-objective linear program (multiobjective optimization).
Dual algorithm
edit edit sourceThere is a dual variant of Benson's algorithm,[3] which is based on geometric duality[4] for multi-objective linear programs.
Implementations
edit edit sourceBensolve - a free VLP solver
Inner
References
edit edit source- ^ 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. Wikipedia revision 881154281, retrieved 2026-11-18
- ^ a b Andreas Löhne (2011). Vector Optimization with Infimum and Supremum. Springer. pp. 162–169. ISBN 9783642183508. Wikipedia revision 881154281, retrieved 2026-11-18
- ^ 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. Wikipedia revision 881154281, retrieved 2026-11-18
- ^ Heyde, Frank; Löhne, Andreas (2008). "Geometric Duality in Multiple Objective Linear Programming" (PDF). SIAM Journal on Optimization. 19 (2): 836–845. doi:10.1137/060674831. ISSN 1052-6234. Wikipedia revision 881154281, retrieved 2026-11-18
Text derived from https://en.wikipedia.org/w/index.php?oldid=881154281 under CC BY-SA 4.0; modifications have been made.