Znalezienie dokładnych rozwiązań narożnych dla programowania liniowego przy użyciu metod punktów wewnętrznych

Algorytm simpleks chciwie chodzi po rogach wielopola, aby znaleźć optymalne rozwiązanie problemu programowania liniowego. W rezultacie odpowiedź jest zawsze rogiem polytopa. Metody punktowe wewnętrzne chodzą po polytopie. W rezultacie, gdy cała płaszczyzna polytopu jest optymalna (jeśli funkcja celu jest dokładnie równoległa do płaszczyzny), możemy uzyskać rozwiązanie w środku tej płaszczyzny.

Załóżmy, że zamiast tego chcemy znaleźć narożnik polytopa. Na przykład, jeśli chcemy wykonać maksymalne dopasowanie, redukując je do programowania liniowego, nie chcemy uzyskać odpowiedzi składającej się z: „dopasowanie zawiera 0,34% krawędzi XY i 0,89% krawędzi AB i ...”. Chcemy uzyskać odpowiedź z zerami i jedynymi (które dałby nam simplex, ponieważ wszystkie rogi składają się z zer i jedynek). Czy można to zrobić za pomocą metody punktu wewnętrznego, która gwarantuje znalezienie dokładnych rozwiązań narożników w czasie wielomianowym? (na przykład być może możemy zmodyfikować funkcję celu, aby faworyzować rogi)

Możesz przeczytać artykuł:

Sanjay Mehrotra, Po znalezieniu rozwiązania wierzchołka przy użyciu metod punktu wewnętrznego, Algebra liniowa i jej zastosowania, tom 152, 1 lipca 1991 r., Strony 233-253, ISSN 0024-3795, 10.1016 / 0024-3795 (91) 90277-4. link do artykułu sciencedirect

Chociaż pytanie ma sens, to dziwne, że jako przykład wybrano maksymalne dopasowanie, ponieważ istnieje wiele algorytmów (maksymalne przepływy dla maksymalnego dwustronnego dopasowania kardynalności, algorytm Edmondsa dla dwustronnego dopasowania i węgierski algorytm dla dwustronnego dopasowania maksymalnej wagi) to da rozwiązania problemu dla wierzchołków całkowitych.

Ze względu na brak szczegółów jest to tylko dłuższy komentarz:

Wielomianowy algorytm czasu Karmarkara porusza się tylko w pobliżu krawędzi. Na koniec znajduje odpowiednie podstawowe rozwiązanie (np. Narożnik), które jest optymalne przy użyciu schematu oczyszczania ¹. Możesz użyć tej lub podobnej techniki, aby przejść do rogu z samolotu.

¹ Nie mogę tego dostrzec w oryginalnej pracy Karmarkara . Odnoszę się do „Lineare Optimierung und Netzwerkoptimierung” (w języku angielskim: Optymalizacja liniowa i sieciowa) autorstwa Hamachera i Klamrotha, który ma tekst niemiecki i angielski obok siebie.

Tak, istnieje prosta metoda i zaimplementowałem ją w C ++, aby połączyć szybkość metod punktów wewnętrznych z dokładnością metod simpleksowych (używając iteracyjnego udoskonalenia odwrotności macierzy podstawowej mogę uzyskać dokładność 1 części na 10 ^ 15 i lepiej na gęstych macierzach więzów z ponad 1000 zmiennych i wiązań).

Kluczem jest używana metoda simpleks. Załóżmy, że metoda simpleks ma mechanizm refaktoryzacji podstawy (np. Po skumulowanym błędzie zaokrąglenia czyni to koniecznym) i że ta metoda refaktoryzacji po prostu odtwarza macierz odwrotną dla podstawy, która zawiera całą pożądaną listę podstawowych zmiennych. Ponadto załóżmy, że nawet jeśli żądanej podstawy nie można odtworzyć w całości, że algorytm simpleks jest w stanie kontynuować od podstawy zawierającej 95% podstawy docelowej, odpowiedź jest bardzo prosta.

Wszystko, co musisz zrobić, to wziąć rozwiązanie z metody punktu wewnętrznego, wyeliminować zmienną, której pierwotne wartości rozwiązania są implikowane jako zero przez komplementarny luz, i biorąc pod uwagę rozmiar podstawy w problemie simpleksowym b, weź zmienne b do wnętrza rozwiązanie punktowe o największych wartościach (lub tyle, ile wartości niezerowe, jeśli jest to mniej niż b), i refaktoryzuj bazę simpleks, aby zawierała te zmienne b. Następnie kontynuuj metodę simpleks, aż się rozwiąże. Ponieważ zaczynasz problem simpleks blisko końca, zwykle jest to bardzo szybkie.