Алгоритм Бенсона - Bensons algorithm

Не путать с Алгоритм Бенсона (Go), способ найти безоговорочно живые камни в игре Идти.

Алгоритм Бенсона, названный в честь Гарольд Бенсон, это метод решения многоцелевое линейное программирование задачи и векторные линейные программы. Это работает путем нахождения «эффективных экстремальных точек в наборе результатов».^[1] Основная идея алгоритма Бенсона - оценить верхнее изображение векторная оптимизация проблема рубки.^[2]

Идея алгоритма

Рассмотрим векторную линейную программу

${\displaystyle \min _{C}Px\;{\text{ subject to }}Ax\geq b}$

за ${\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}$, который называется верхним изображением.^[2]

В случае ${\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. Гарольд П. Бенсон (1998). «Алгоритм внешнего приближения для генерации всех эффективных экстремальных точек в исходном наборе задачи многократного объективного линейного программирования». Журнал глобальной оптимизации. 13 (1): 1–24. Дои:10.1023 / А: 1008215702611.
2. Андреас Лёне (2011). Векторная оптимизация с точками инфимума и супремума. Springer. С. 162–169. ISBN  9783642183508.
3. Эрготт, Матиас; Лёне, Андреас; Шао, Личжэнь (2011). «Двойной вариант« алгоритма внешнего приближения »Бенсона для многоцелевого линейного программирования». Журнал глобальной оптимизации. 52 (4): 757–778. Дои:10.1007 / s10898-011-9709-y. ISSN  0925-5001.
4. Хейде, Франк; Лёне, Андреас (2008). «Геометрическая двойственность в многоцелевом линейном программировании» (PDF). SIAM Journal по оптимизации. 19 (2): 836–845. Дои:10.1137/060674831. ISSN  1052-6234.