Uzasadnienie metody węgierskiej (Kuhn-Munkres)

Napisałem implementację algorytmu Kuhna-Munkresa dla problemu dwustronnego idealnego dopasowania minimalnej wagi w oparciu o notatki z wykładu, które znalazłem tu i tam w Internecie. Działa naprawdę dobrze, nawet na tysiącach wierzchołków. I zgadzam się, że teoria jest naprawdę piękna. A jednak wciąż zastanawiam się, dlaczego musiałem tak bardzo się starać. Uważam, że te notatki z wykładu nie wyjaśniają, dlaczego nie możemy po prostu wziąć pierwotnego programu liniowego i przekazać go do metody simpleks. Oczywiście podejrzewam, że jest to kwestia przewidywalnej wydajności, ale ponieważ nie widziałem tego wyraźnie stwierdzonego, nie jestem zbyt pewien. Udowodniono, że ekstremalne punkty pierwotne polytopu mają wartość 0-1, więc wydaje się, że możemy je zasilić bezpośrednio do implementacji simpleks bez formułowania dualności. A może jestem uproszczony?

(Przeniesiono z komentarza.)

Oczywiście możesz rozwiązać dowolny LP za pomocą uniwersalnego solwera LP, ale wyspecjalizowane algorytmy zazwyczaj mają znacznie lepszą wydajność.

Nie chodzi tylko o teoretyczne gwarancje asymptotycznych osiągów, ale także o praktyczne osiągi w świecie rzeczywistym. Algorytmy, takie jak metoda węgierska, mogą być bardzo usprawnione i są stosunkowo łatwe do prawidłowego i wydajnego wdrożenia.

Często można również uniknąć problemów, takich jak używanie dokładnych liczb wymiernych vs. liczb zmiennoprzecinkowych; wszystko można łatwo zrobić za pomocą liczb całkowitych.

Chociaż odpowiedź ta jest poprawna w ogólnym sensie, pomocne jest również dokładne zrozumienie, co się dzieje, gdy stosuje się pierwotny simpleks do problemu przypisania. Rozważ problem przypisania NxN z macierzą kosztu kwadratowego c_ij. Odpowiedni LP ma do rozwiązania zmienne N ^ 2 x_ij. Myśląc o tych x_ij jako macierzy kwadratowej X, wykonalne rozwiązanie wymaga, aby X był macierzą permutacji, która jest wymuszona przez ograniczenia 2N-1 w naszym LP (może się wydawać na pierwszy rzut oka, że ​​istnieją ograniczenia 2N, po jednym dla każdego wiersza i jeden na każdą kolumnę, ale nie wszystkie są niezależne i upuszczamy jedną z nich). Wiązania LP tworzą zatem macierz A (2N-1) x (N ^ 2) A.

Teraz powstaje podstawowe rozwiązanie z wyboru zestawu podstawowych zmiennych (2N-1). Jednak, aby to podstawowe rozwiązanie było również wykonalne, tylko N z tych zmiennych może mieć wartość 1, a inne (N-1) mają wartość 0. Zatem każde możliwe rozwiązanie jest zdegenerowane. Problem z tą degeneracją polega na tym, że dowolną z podstawowych zmiennych (N-1), które są 0, można zamienić na dowolną z podstawowych zmiennych (N ^ 2-2N + 1), tzw. „Zdegenerowaną oś obrotu”, bez wpływ na wartość funkcji celu [zamieniasz tylko jedną zmienną 0 na inną]. Gdy N jest duże, pierwotny algorytm simpleks marnuje dużo czasu na tworzenie zdegenerowanych osi, które nie poprawiają rozwiązania. To jest sedno tego, dlaczego naiwny pierwotny algorytm simpleksowy nie jest wykorzystywany bezpośrednio do rozwiązania problemu przypisania.