ベンソンのアルゴリズム

ハロルド・ベンソンにちなんで名付けられたベンソンアルゴリズムは、多目的線形計画問題およびベクトル線形計画問題を解く手法です。このアルゴリズムは、「結果集合における効率的な極値点」を見つけることで機能します。 ^{[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ソルバー

• www.bensolve.org

内側

• githubへのリンク

参考文献

1. Harold P. Benson (1998). 「多目的線形計画問題の結果集合におけるすべての効率的な極値点を生成するための外部近似アルゴリズム」. Journal of Global Optimization . 13 (1): 1– 24. doi :10.1023/A:1008215702611.
2. アンドレアス・ローネ (2011)。Infimum および Supremum を使用したベクトル最適化。スプリンガー。162 ～ 169ページ 。ISBN 9783642183508。
3. Ehrgott, Matthias; Löhne, Andreas; Shao, Lizhen (2011). 「多目的線形計画法のためのBensonの「外近似アルゴリズム」の双対変種」. Journal of Global Optimization . 52 (4): 757– 778. doi :10.1007/s10898-011-9709-y. ISSN  0925-5001.
4. Heyde, Frank; Löhne, Andreas (2008). 「多目的線形計画法における幾何学的双対性」(PDF) . SIAM Journal on Optimization . 19 (2): 836– 845. doi :10.1137/060674831. ISSN  1052-6234.