Benson's algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 1 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". The primary concept in Benson's algorithm is to evaluate the upper image of the vector optimization problem by cutting planes.

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". The primary concept in Benson's algorithm is to evaluate the upper image of the vector optimization problem by cutting planes. 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. 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).

Text derived from https://en.wikipedia.org/w/index.php?oldid=881154281 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-000881154281 · captured 1548961384.0 · version history

Cite this page as: encyclopegia.org, “Benson's algorithm”, snapshot enwiki-000881154281. https://encyclopegia.org/a/benson-s-algorithm

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.