Interesuje mnie implementacja SM dla zadania LP, jednak słyszałem o możliwych pułapkach: książka Cormena mówi, że możliwe jest posiadanie danych wejściowych, które sprawią, że naiwna implementacja zachowa się w wykładniczym czasie. Słyszałem również, że naiwna implementacja może zapętlać dane.
Czy istnieje książka / artykuł / źródło wyjaśniające niuanse praktycznego wdrażania SM?
Z góry dziękuję.
Odpowiedzi:
Zdecydowanie polecam artykuł Bixby, „ojca” CPLEX, który analizuje nie tylko aspekty wdrażania (poprawionego) algorytmu simpleksowego: Robert E. Bixby , Rozwiązywanie rzeczywistych programów liniowych: dekada i więcej postępu , operacje Research (50) 2002, 3-15 .
źródło
Algorytmu simpleks nie ma w P. CLRS stwierdza zatem, że chociaż w praktyce działa on „dobrze”, istnieją pewne dane wejściowe powodujące, że algorytm działa w czasie wykładniczym. Jest to ściśle związane z algorytmem, a nie z jego implementacją: staniesz przed nim niezależnie od tego, jak dokładnie zaimplementujesz algorytm. Jednak LP jest w P. Zostało to udowodnione przez Khachiana w 1979 roku, jednak jego algorytm elipsoidy nie jest praktyczny. Obecnie metody punktów wewnętrznych są szeroko stosowane. Pierwszy został odkryty przez Karmarkara w 1984 roku.
Jeśli jesteś zainteresowany praktycznymi wdrożeniami, spójrz na:
GUROBI, darmowy do użytku akademickiego, jest obecnie najlepszym dostępnym optymalizatorem (wersja równoległa dla pamięci sekwencyjnej i współdzielonej):
http://www.gurobi.com
biblioteka GLPK:
http://www.gnu.org/software/glpk/
jest to projekt typu open source, zapewniający wdrożenia dla:
źródło
Książka programowania liniowego Vanderbei zawiera wiele szczegółów niskiego poziomu ... Ale jak sugerują inne odpowiedzi / komentarze, wdrożenie LP Solvera jest trudnym i niewdzięcznym zadaniem. Solver z półki jest prawdopodobnie najlepszą drogą ... (Istnieją również solwery LP typu open source ...)
źródło
To nie tylko naiwne implementacje, które czasem zachowują się wykładniczo. W rzeczywistości uważam, że wszystkie znane reguły deterministyczne i losowe mają wielomianowe najgorsze dane wejściowe. Większość znanych danych wejściowych, które powodują takie zachowanie w najgorszym przypadku, ma wysoce ustrukturyzowane, powiązane pytanie:
Struktura instancji patologicznych dla algorytmów simpleks
Jednak w praktyce SM działa dobrze. Zostało to sformalizowane przez wprowadzenie wygładzonej analizy, która jest w zasadzie analizą najgorszego przypadku z lekko zaburzonymi danymi wejściowymi. Zgodnie z tą analizą SM jest czasem policyjnym, innymi słowy, dla każdego wejścia (nawet patologicznego) występuje niewielkie zaburzenie, które pozwala algorytmowi na dobre działanie. Ten wgląd został przekształcony w losowy algorytm, który działa w czasie rzeczywistym. Jednak, o ile rozumiem, wciąż trwa debata na temat tego, czy ten algorytm kwalifikuje się jako „prawdziwy” algorytm simpleksowy. Nie jestem również świadomy, czy standardowe pakiety implementują coś podobnego do tego, ale powinieneś być w stanie znaleźć implementację, jeśli będziesz szukać, ponieważ wynik ma ponad 5 lat.
źródło
Możesz sprawdzić Luenberger, Ye, Programowanie liniowe i nieliniowe, wydanie 3. Wydaje się to dość wyczerpujące, ale nie dotarłem jeszcze wystarczająco daleko, aby powiedzieć, czy całkowicie odpowiada na twoje pytanie.
źródło