Сложность симплексного алгоритма

36

Какова верхняя граница симплексного алгоритма для поиска решения линейной программы?

Как мне найти доказательства для такого случая? Кажется, что наихудший случай - посещение каждой вершины, то есть . Однако на практике симплексный алгоритм будет работать значительно быстрее, чем этот, для более стандартных задач.О(2N)

Как я могу рассуждать о средней сложности проблемы, решаемой с помощью этого метода?

Любая информация или ссылки с благодарностью!

shuttle87
источник
5
Обратите внимание, что, как сказал Машка в ответе , у нас на самом деле нет «симплексного алгоритма». Существует много разных симплексных алгоритмов в зависимости от выбора правила поворота.
Цуёси Ито
2
Куб в размерности имеет 2 n вершин, и это так, если верхняя граница для любого симплексного варианта на (например, Klee-Minty) кубах. Тем не менее, существуют многогранники в измерении n с 2 n гранями, такие как двойные циклические многогранники, с более чем 2 n вершинами, поэтому 2 n не является непосредственной верхней границей времени выполнения симплекс-метода для матриц квадратного ограничения в целом , N2NN2N2N2N
Рахул Савани

Ответы:

72

Симплексный алгоритм действительно посещает все 2N вершин в худшем случае ( Klee & Minty 1972 ), и это оказывается верным для любого детерминистического правила поворота. Тем не менее, в историческом документе, использующем сглаженный анализ, Spielman и Teng (2001) доказали, что, когда входные данные алгоритма слегка случайным образом возмущены, ожидаемое время работы симплексного алгоритма является полиномиальным для любых входных данных - это в основном говорит, что для любая проблема есть «рядом», которую симплекс-метод будет эффективно решать, и она в значительной степени охватывает все реальные линейные программы, которые вы хотели бы решить. Впоследствии Келнер и Спилман (2006) представили рандомизированный симплекс-алгоритм за полиномиальное время, который работает на любых входах, даже на плохих для исходного симплекс-алгоритма

Лев Рейзин
источник
36

Как сказал Лев, в худшем случае алгоритм посещает все 2d вершины, где d - количество переменных. Однако производительность симплексного алгоритма также может сильно зависеть от конкретного используемого правила поворота. Насколько мне известно, остается открытым вопрос, существует ли конкретное детерминированное правило поворота с субэкспоненциальным временем наихудшего случая. Многие кандидаты были исключены из нижних оценок результатов. Недавно Фридман, Хансен и Цвик также показали первые неполиномиальные нижние оценки для некоторых естественных рандомизированных правил разворота с некоторыми исправлениями, представленными позже .

Тем не менее, добавив к сглаженному результату анализа, упомянутому Левом: После того, как в оригинальной работе Спилмана и Тенгса был представлен сглаженный анализ, Вершинин еще больше улучшил свои границы в 2006 году. Он показал, что ожидаемое время работы в слегка возмущенных случаях является лишь полилогарифмическим по числу ограничения N , а не N86 .

Матиас
источник
4
и, как указал Джефф в другом вопросе ( cstheory.stackexchange.com/questions/2149/… ), лучший на сегодняшний день субэкспоненциальный метод является своего рода двойным симплексом.
Суреш Венкат
Ссылка на статью Вершинина мертва.
Кучкем
8

Чтобы получить представление о анализе симплексного метода в наихудшем и среднем случае, вы должны прочитать «Сглаженный анализ: почему симплексный алгоритм обычно занимает полиномиальное время». Спилман и Тен.

Кристина Баучер
источник
3

Хорошая ссылка на то, почему симплекс не работает за полиномиальное время, а не на то, почему он экспоненциальный, - это комбинаторная оптимизация Papadimitriou & Steiglitz, раздел 8.6, в которой они демонстрируют, что Simplex не является алгоритмом полиномиального времени.

hyperboreean
источник
1

Dзнак равно200

GLPK Simplex Optimizer, v4.65
200 rows, 200 columns, 20100 non-zeros
Preprocessing...
199 rows, 200 columns, 20099 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.607e+60  ratio =  1.607e+60
...
Constructing initial basis...
Size of triangular part is 199
*     0: obj =   0.000000000e+00 inf =   0.000e+00 (200)
*     1: obj = -6.223015278e+139 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Time used:   0.0 secs
Memory used: 3.4 Mb

Кто-нибудь может предложить другие способы построения сложных задач для симплекс-метода, медленный, но не связанный с памятью?

Добавлено: латинские квадраты или 3d-перестановочные матрицы имеют много вершин - сколько?
Теория и практика ближе в теории, чем на практике.

Денис
источник
-1

Оригинальный алгоритм симплекс могут расходиться; это циклы в определенных случаях. Следовательно, нет общей границы. Другие ответы дают вам ответы на различные модификации алгоритма Simplex.

MdAyq7
источник