ベンソンのアルゴリズム

ハロルド・ベンソンにちなんで名付けられたベンソンのアルゴリズムは、多目的線形計画問題とベクトル線形計画を解くための手法です。これは、「結果セット内の効率的な極値点」を見つけることで機能します。 ^{[1]ベンソンのアルゴリズムの主な概念は、}平面を切断してベクトル最適化問題 の上部画像を評価することです。^[2]

ベクトル線形計画法を考える

${\displaystyle \min _{C}Px\;{\text{ ただし }}Ax\geq b}$

、、および内部が空でなく直線を含まない多面体凸順序円錐に対して成り立つ。実現可能集合は である。特に、ベンソンのアルゴリズムは集合 の極値点（上図と呼ばれる）を見つける。[ ^2]${\displaystyle P\in \mathbb {R} ^{q\times n}}$${\displaystyle A\in \mathbb {R} ^{m\times n}}$${\displaystyle b\in \mathbb {R} ^{m}}$${\displaystyle C}$${\displaystyle S=\{x\in \mathbb {R} ^{n}:\;Ax\geq b\}}$${\displaystyle P[S]+C}$

の場合、多目的線形計画法（多目的最適化）の特殊​​なケースが得られます。 ${\displaystyle C=\mathbb {R} _{+}^{q}:=\{y\in \mathbb {R} ^{q}:y_{1}\geq 0,\dots ,y_{q}\geq 0\}}$

ベンソンのアルゴリズムには双対型があり^[3] 、これは多目的線形計画法の 幾何学的双対性^[4]に基づいています。

Bensolve - 無料の VLP ソルバー

• ベンソルブ

内側

• githubへのリンク