Dlaczego komplementarność jest ważna?

Komplementarny luz (CS) jest powszechnie nauczany, gdy mówi się o dualności. Ustanawia ładny związek między pierwotnym a podwójnym ograniczeniem / zmiennymi z matematycznego punktu widzenia.

Dwa główne powody stosowania CS (zgodnie z nauczaniem na kursach dla absolwentów i podręcznikach):

Aby sprawdzić optymalność LP
Aby pomóc rozwiązać problem podwójny

Biorąc pod uwagę dzisiejszą moc obliczeniową i algorytmy wielomianowe do rozwiązywania problemów z LP, czy CS jest nadal istotne z pragmatycznego punktu widzenia? Zawsze możemy po prostu rozwiązać problemy dualne i rozwiązać oba powyższe punkty. Zgadzam się, że „bardziej wydajne” jest rozwiązywanie podwójności przy pomocy CS, ale czy to jest to? A może CS to coś więcej niż na pierwszy rzut oka? Gdzie dokładnie CS jest przydatne poza powyższymi dwoma punktami ? Zwykle widziałem teksty nawiązujące do koncepcji CS, mówiąc o algorytmach aproksymacyjnych, ale nie rozumiem jej roli w tym przypadku.

ds.algorithms approximation-algorithms linear-programming primal-dual Doktorat
źródło

Nie moja specjalizacja, ale brzmi to tak, jakbyś pytał, dlaczego uczymy właściwości X, mimo że decyzja o X jest obliczeniowa z łatwością. Na przykład, dlaczego uczymy charakteryzowania dwuczęściowości „brak nieparzystych cykli = dwustronna”, chociaż mamy algorytmy wielomianowe do sprawdzania dwustronności. Czy w pewnym sensie o to pytasz?

Robin Kothari,

Nie dokładnie. Rozumiem „dlaczego” tego uczysz. Chciałbym dowiedzieć się z praktycznego POV, w jaki sposób jest wykorzystywany podczas rozwiązywania płyt LP i / lub projektowania algorytmów aproksymacyjnych. Jaki uzyskamy wgląd poza matematycznymi zależnościami między zmiennymi a ograniczeniami.

Cóż, myślę, że może to pomóc w uzyskaniu rozwiązań „analitycznych” ... które mogą być trudniejsze w przypadku komputera.

usul

Nie dostaję pytania. Tylko dlatego, że używamy kalkulatorów i komputerów do dodawania i mnożenia liczb, czy nadal musimy znać właściwości liczb?

Chandra Chekuri

@ChandraChekuri - Nie mam tego na myśli. Próbuję tylko dowiedzieć się, co jest takiego wspaniałego w tym twierdzeniu i dlaczego jest to ważne. Nie chcę zaakceptować tego jako „tak jest”, ale chciałbym głębiej zrozumieć jego znaczenie w dualności LP

Odpowiedzi:

Uzupełniające luki są kluczowe w projektowaniu pierwotnych podwójnych algorytmów. Podstawową ideą jest:

Start z wykonalnym podwójnego rozwiązanie . $y$
Próba znalezienia pierwotnej wykonalnej wartości takiej, aby spełniała komplementarność luzu. $x$ $(x, y)$
Jeśli krok 2. się powiedzie, jesteśmy skończeni. W przeciwnym razie przeszkoda w znalezieniu daje możliwość modyfikacji tak, aby wartość funkcji podwójnego celu wzrosła. Powtarzać. $x$ $y$

Klasycznym przykładem jest algorytm węgierski. Algorytm Forda-Fulkersona może być postrzegany jako kolejny przykład. Należy pamiętać, że krok 2. jest problemem wykonalności, który często jest łatwiejszy niż pierwotny problem optymalizacji, a także często można go rozwiązać kombinatorycznie. To jest siła uzupełniającego luzu. Na przykład w przypadku dopasowania dwustronnego minimalnego kosztu krok 2 polega na sprawdzeniu, czy istnieje idealne dopasowanie przy użyciu tylko ciasnych krawędzi. W przypadku maksymalnego przepływu - krok 2 polega na sprawdzeniu, czy nasycone krawędzie oddzielają i . $s$ $t$ $s$ $t$

Algorytmy pierwotne-dualne są dobre z wielu powodów. Filozoficznie zapewniają więcej wglądu niż ogólny algorytm. Zazwyczaj dają silnie wielomianowe algorytmy czasowe, podczas gdy nadal nie mamy silnie wielomianowych solverów LP. Często są one bardziej praktyczne niż ogólne algorytmy. Jest to szczególnie ważne, jeśli nie możemy jednoznacznie zapisać LP, a naszym jedynym wyborem jest algorytm elipsoidalny, co ma miejsce w przypadku dopasowania dwustronnego i algorytmu pierwotnego podwójnego Edmondsa.

Primal-dual jest również bardzo użyteczną strukturą dla algorytmów aproksymacyjnych, wykorzystując zrelaksowane wersje komplementarnego luzu. Jest to przydatne w projektowaniu algorytmów aproksymacyjnych dla problemów trudnych dla NP (patrz np. Rozdział 7 książki Williamson-Shmoys ) oraz w projektowaniu algorytmów online o dobrym współczynniku konkurencyjnym (patrz książka Buchbindera i Naora ). Chodzi o to, że algorytm utrzymuje rozwiązanie podwójnej relaksacji LP trudnego problemu, i na każdym kroku albo znajduje integralną pierwotną wykonalną wartość , że spełniony jest przybliżony komplementarny luz, albo poprawia podwójne rozwiązanie $y$ $x$ $y$ . Przybliżona komplementarna luźność jest warunkiem następującej postaci: jeśli to odpowiednie podwójne wiązanie jest ścisłe, a jeśli , odpowiednie pierwotne ograniczenie byłoby ścisłe, jeśli jest skalowane przez . Daje to współczynnik przybliżenia . Wszystko to bardzo ładnie wyjaśniono w powyższych dwóch źródłach. $x_i > 0$ $y_j > 0$ $x$ $\alpha$ $\alpha$

Sasho Nikolov
źródło