Złożoność algorytmu simpleks

Jaka jest górna granica algorytmu simpleks dla znalezienia rozwiązania dla programu liniowego?

Jak mam znaleźć dowód na taką sprawę? Wydaje się, że najgorszym przypadkiem jest konieczność odwiedzenia każdego wierzchołka, czyli . Jednak w praktyce algorytm simpleks będzie działał znacznie szybciej niż w przypadku bardziej standardowych problemów.$O(2^n)$

Jak mogę uzasadnić średnią złożoność problemu rozwiązywanego za pomocą tej metody?

Wszelkie informacje lub referencje są mile widziane!

Algorytm simpleks rzeczywiście odwiedza wszystkie $2^n$ wierzchołków w najgorszym przypadku ( Klee i Minty 1972 ), i okazuje się, że jest to prawdą dla każdej deterministycznej reguły obrotu. Jednak w przełomowym artykule wykorzystującym wygładzoną analizę Spielman i Teng (2001) udowodnili, że gdy dane wejściowe do algorytmu są nieco przypadkowo zaburzone, oczekiwany czas działania algorytmu simpleks jest wielomianowy dla wszystkich danych wejściowych - to w zasadzie mówi, że dla każdy problem istnieje „w pobliżu”, który metoda simplex skutecznie rozwiąże, i w zasadzie obejmuje każdy rzeczywisty program liniowy, który chcesz rozwiązać. Następnie Kelner i Szpilman (2006) wprowadził algorytm simpleksowy z randomizowanym czasem wielomianowym, który truley działa na dowolnych wejściach, nawet tych złych dla oryginalnego algorytmu simpleks.

Jak powiedział Lev, w najgorszym przypadku algorytm odwiedza wszystkie $2^d$ wierzchołki, gdzie $d$ jest liczbą zmiennych. Jednak wydajność algorytmu simpleks może również w dużym stopniu zależeć od konkretnej zastosowanej reguły przestawnej. O ile mi wiadomo, wciąż pozostaje otwarte pytanie, czy istnieje konkretna deterministyczna reguła obrotu z sub wykładniczym czasem najgorszego przypadku. Wielu kandydatów zostało wykluczonych z dolnej granicy wyników. Niedawno Friedmann, Hansen i Zwick pokazali również pierwsze nie-wielomianowe dolne granice dla niektórych naturalnych losowych reguł obrotu, z pewnymi poprawkami przedstawionymi później .

Jednak, dodając do wygładzonego wyniku analizy wspomnianego przez Leva: Po tym, jak Spielman i Tengs w swoim artykule wprowadzającym wygładzoną analizę, Vershynin jeszcze bardziej poprawił swoje granice w 2006 roku. Pokazał, że oczekiwany czas działania w lekko zakłóconych instancjach jest tylko pollogarytmiczny w liczbie ograniczenia $n$ , w dół od $n^{86}$ .

Aby uzyskać wgląd w analizę najprostszych i średnich przypadków metody simpleks, należy przeczytać „Analiza wygładzona: dlaczego algorytm simpleks zwykle zajmuje czas wielomianowy”. przez Spielman i Teng.

Dobrym odniesieniem do tego, dlaczego simplex nie działa w czasie wielomianowym, a nie dlaczego jest wykładniczy, jest Optymalizacja kombinatoryczna Papadimitriou & Steiglitz, rozdział 8.6, w którym wykazano, że Simplex nie jest algorytmem wielomianowym.

$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

Czy ktoś może zasugerować inne sposoby konstruowania trudnych problemów dla metody simpleks, powolnych, ale niezwiązanych z pamięcią?

Dodano: Łacińskie kwadraty, czyli matryce 3d-permutacji, wydają się mieć wiele wierzchołków - ile?
_{Teoria i praktyka są bliższe teorii niż w praktyce.}

Oryginalny algorytm Simplex mogą być różne; cyklicznie w niektórych przypadkach. Dlatego nie ma ogólnego ograniczenia. Inne odpowiedzi dostarczają odpowiedzi na różne modyfikacje algorytmu Simplex.