Złożoność algorytmu simpleks

36

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!

— transfer87
źródło

5

Zauważ, że jak mashca powiedziała w odpowiedzi , tak naprawdę nie mamy „algorytmu simpleksowego”. Istnieje wiele różnych algorytmów simpleksowych w zależności od wyboru reguły przestawnej.

— Tsuyoshi Ito

2

Sześcian w wymiarze

ma

wierzchołków, a więc jest to górna granica dowolnego wariantu simpleksowego (np. Klee-Minty). Istnieją jednak wielościany w wymiarze

o

ściankach, takie jak podwójne cykliczne polytopy, z więcej niż

wierzchołkami, więc

nie jest bezpośrednią górną granicą czasu działania metody simpleksowej dla macierzy więzów kwadratowych ogólnie .

n

$n$

2^{n}

$2^n$

n

$n$

2 n

$2n$

2^{n}

$2^n$

2^{n}

$2^n$

— Rahul Savani

72

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.

— Lew Reyzin
źródło

36

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}$ .

— Matthias
źródło

4

i jak zauważył JeffE w innym pytaniu ( cstheory.stackexchange.com/questions/2149/… ), obecnie najlepszą najlepszą metodą podwykładniczą jest rodzaj podwójnego simpleksu.

— Suresh Venkat

Link do papieru Vershynin jest martwy.

— kutschkem

8

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.

— Christina Boucher
źródło

3

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.

— hiperborejskie
źródło

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

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.}

— Denis
źródło

-1

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.

— MdAyq7
źródło