Podstawa Gravera

W matematyce stosowanej podstawy Gravera umożliwiają iteracyjne rozwiązania liniowych i różnych nieliniowych problemów programowania liczb całkowitych w czasie wielomianowym . Zostały one wprowadzone przez Jacka E. Gravera. Ich związek z teorią baz Gröbnera omówił Bernd Sturmfels . Algorytmiczną teorię baz Gravera i jej zastosowanie do programowania liczb całkowitych opisuje Shmuel Onn .

Definicja formalna

Podstawa Gravera macierzy liczb całkowitych m × n jest skończonym zbiorem minimalnych elementów w zestawie $sol$${\ Displaystyle G (A$

${\ Displaystyle \ {x \ w \ mathbb {Z} ^ {n}: Ax = 0, \ x \ neq 0 \} \,}$

pod dobrze częściowym porządkiem na ${\ Displaystyle \ mathbb {Z} ^ {n}}$ zdefiniowany przez ${\ Displaystyle x \ sqsubseteq y}$ kiedy ${\ Displaystyle x_ {i} y_ {i }\geq 0}$ i ${\ Displaystyle | x_ {i} | \ równoważnik | y_ {i} |}$ dla wszystkich ja. Na przykład podstawa Gravera ${\ Displaystyle A = (1,2,1)}$ składa się z wektorów (2, −1,0), (0, −1,2), (1,0, −1), (1, −1, 1) i ich negacje.

Rozwiązywanie programowania całkowitoliczbowego z wykorzystaniem podstaw Gravera

Programowanie całkowitoliczbowe to problem optymalizacji liniowej lub nieliniowej funkcji celu na zbiorze punktów całkowitych spełniających układ nierówności liniowych. Formalnie można to zapisać w standardowej postaci w następujący sposób:

${\ Displaystyle \ min \ {f (x) \: \ x \ w \ mathbb {Z} ^ {n}, \ Ax = b, \ l \ równoważnik x \ równoważnik u \} \.}$

Jest to jeden z najbardziej podstawowych problemów optymalizacji dyskretnej i ma bardzo szeroką moc modelowania oraz liczne zastosowania w różnych obszarach, ale zazwyczaj jest bardzo trudny obliczeniowo, jak wspomniano poniżej. Jednak biorąc pod $uwagę$ podstawę Gravera $wyjaśniono$ problem z liniowymi i różnymi nieliniowymi funkcjami celu można rozwiązać w czasie wielomianowym

Liniowe programowanie całkowitoliczbowe

Najbardziej zbadanym przypadkiem, dokładnie omówionym w, jest przypadek liniowego programowania całkowitoliczbowego ,

${\ Displaystyle \ min \ {wx \: \ x \ in \ mathbb {Z} ^ {n}, \ Ax = b, \ l \ równoważnik x \ równoważnik u \} \ .}$

Można przyjąć, że wszystkie zmienne są ograniczone z dołu iz góry: takie ograniczenia albo pojawiają się naturalnie w danej aplikacji, albo można je wymusić bez utraty optymalnych rozwiązań. Ale nawet przy liniowych funkcjach celu problem jest NP-trudny i dlatego prawdopodobnie nie można go rozwiązać w czasie wielomianowym.

Jednak podstawa $.$$_$ _ Dla każdego możliwego punktu x :

• Albo x jest optymalne (tj. minimalizuje biorąc pod uwagę ograniczenia); ${\ Displaystyle w \ cdot x}$
• Albo istnieje wektor $g$ w , taki, że + g jest i $+ g) <w\cdot x}$ (tj. x można poprawić, dodając do niego element bazy Gravera).

$uwagę$ podstawę Gravera ILP można rozwiązać za pomocą następującego prostego algorytmu iteracyjnego dany jest pewien początkowy możliwy punkt x . Jeśli to $x$ następującą iterację: znajdź dodatnią liczbę całkowitą q i element g w że + qg nie narusza granic i daje najlepszą możliwą poprawę; zaktualizuj x := x + qg i przejdź do następnej iteracji. Ostatni punkt x jest optymalny, a liczba iteracji jest wielomianem.

Aby znaleźć początkowy możliwy punkt, można ustawić i rozwiązać odpowiedni program pomocniczy w podobny sposób.

Nieliniowe programowanie całkowitoliczbowe

Wracając do przypadku ogólnych funkcji celu f , jeśli zmienne są nieograniczone, to problem może być w rzeczywistości nieobliczalny: z rozwiązania 10. problemu Hilberta ( zob . stopień 8 w 58 zmiennych, decyduje, czy minimalna wartość f dla wszystkich 58-wymiarowych wektorów liczb całkowitych wynosi 0. Jednak gdy zmienne są ograniczone, problem

${\ Displaystyle \ min \ {f (x) \: \ x \ w \ mathbb {Z} ^ {n}, \ Ax=b,\ l\równik x\równik u\}}$

można rozwiązać za pomocą podstawy Gravera $,$ czasie wielomianowym dla kilku nieliniowych funkcji celu :

• rozdzielno-wypukłe postaci ${\ Displaystyle f (x) = \ suma _ {i = 1} ^ {n} f_ {i} (x_ {i} (x_ { i})}$ ;
• $_$ szczególności norma _ _ _
• Funkcje złożone-wklęsłe f ( x ) = g ( Wx ), gdzie W jest macierzą liczb całkowitych d × n z ustalonym d i gdzie g jest funkcją wklęsłą o zmiennej d ;
• Pewne (nie)określone funkcje kwadratowe i wielomiany wyższego stopnia .

Niektóre aplikacje

Tabele wielowymiarowe

Rozważ następujący problem optymalizacyjny na trójwymiarowych tabelach z określonymi sumami wierszy,

${\ Displaystyle \ min \ {wx \: \ x \ in {\ mathbb {Z}} _ {+} ^ {l \ razy m \ razy n} \, \ \ suma _ {i} x_{i,j,k}=a_{j,k}\,,\ \suma _{j}x_{i,j,k}=b_{i,k}\,,\ \suma _{k} x_{i,j,k}=c_{i,j}\}\ ,}$

za ${\ Displaystyle a_ {j, k}}$ , ${\ Displaystyle b_ {i, k}}$ , $j}}$ nieujemne liczby całkowite (których maksimum value pośrednio wiąże wszystkie zmienne z góry). $)$ przez ( lm + ln + mn × ( lmn ) definiującą macierz tego systemu. Zauważ, że ta macierz generalnie nie jest całkowicie jednomodułowy . Niemniej $l$ wykazano, że dla każdego ustalonego i m jego podstawę Gravera można obliczyć w czasie, który n . Powyższe wyniki pozwalają zatem na rozwiązanie tego problemu w czasie wielomianowym dla stałych l i m oraz zmiennej n . Zauważ, że jeśli tylko jedna strona l stołu jest stała (nawet przy l = 3), podczas gdy zarówno m , jak i n są zmienne, to problem jest NP trudny, jak pokazano w . Bardziej ogólnie, podobne pozytywne wyniki utrzymują się dla wielowymiarowych problemów stołowych (wprowadzonych w ): dla każdego ustalonego d i m 1 , … , $1 } \ kropki, m_ {d}}$ , (nie) -optymalizacja liniowa nad ${\ Displaystyle m_ {1} \ razy \ cdots \ razy m_ {d} \ razy n}$ tablice ze zmienną n i zadanymi marginesami można wykonać w czasie wielomianowym. Ma to dalsze zastosowania w problemach związanych z bezpieczeństwem wpisów i prywatnością w statystycznych bazach danych.

Przepływy wielu towarów

Rozważ problem przepływu wielu towarów całkowitych polegający na kierowaniu k rodzajów towarów całkowitych od m dostawców do n konsumentów podlegających ograniczeniom podaży, zużycia i wydajności, tak aby zminimalizować sumę kosztów wypukłych liniowych lub zależnych od zatorów na łukach. Następnie dla każdego ustalonego k i m można obliczyć podstawę Gravera systemu definiującego, a wynikową funkcję celu rozdzielnie wypukłą zminimalizować w czasie, który jest wielomianem w zmiennej o liczbie n konsumentów oraz w pozostałych danych.

Inne aplikacje

Wiele zastosowań algorytmicznej teorii baz Gravera obejmuje również:

• stochastyczne programowanie całkowitoliczbowe,
• N -krotne programowanie całkowitoliczbowe,
• N -krotne 4-blokowe programowanie całkowitoliczbowe rozkładalne,
• grupowanie,
• kontrola jawności w bazach statystycznych,
• i sprawiedliwy podział niepodzielnych przedmiotów.

W niektórych z tych aplikacji odpowiednia podstawa Gravera nie może być obliczona w czasie wielomianowym, ale można uzyskać do niej dostęp w sposób pośredni, który pozwala na użycie jej w czasie wielomianowym.

Uniwersalność i parametryzacja

Wykazano, że każdy (ograniczony) problem programowania liczb całkowitych jest dokładnie równoważny omówionemu powyżej problemowi tablicowemu 3 × m × n dla pewnych m i n oraz pewnych sum wierszy. Zatem takie problemy tablicowe 3 × m × n są uniwersalne dla programowania liczb całkowitych. Ponadto dla każdego ustalonego m wynikową klasę programów całkowitoliczbowych można rozwiązać w czasie wielomianowym za pomocą opisanej powyżej iteracyjnej metody bazowej Gravera. Tak więc szerokość tabeli m zapewnia parametryzację wszystkich problemów programowania całkowitoliczbowego.

Hierarchia przybliżeń dla programowania całkowitoliczbowego

$n$ przez $podstawę$ macierzy uniwersalny 3 × m × powyżej Elementy ${\ Displaystyle G (m, n)}$ to tabele 3 × m × n ze wszystkimi sumami wierszy równymi 0. Typ takiej tabeli to liczba jej niezerowych 3 × m warstw . Okazuje się, że istnieje skończona $funkcja$ Gravera ( m ) taka, że ​​dla dowolnego dowolnego elementu podstawy Gravera najwyżej g ( m ). Wynika z tego, że podstawa Gravera $, n ) {\ Displaystyle G (m$ sumą ${\ Displaystyle {n \ wybierz g (m)}}$ odpowiednio osadzone kopie podstawy Gravera sol $\ Displaystyle G (m, g (m))}$ . Aby w przybliżeniu rozwiązać w praktyce dowolny problem programowania liczb całkowitych, wykonaj następujące czynności. Najpierw umieść go w odpowiednim problemie stołowym 3 × m × n , na co pozwala wspomniana powyżej uniwersalność. Teraz zastosuj następującą hierarchię przybliżeń: ${\ Displaystyle G (m, n)}$ . Na poziomie $}$ tej hierarchii niech podzbiorem składającym się tylko z $, n )$ ) tych elementów typu co najwyżej k ; użyj tego przybliżenia ${\ Displaystyle G_ {k} (m, n)}$ w algorytmie iteracyjnym tak długo, jak to możliwe, aby uzyskać jak najlepszy możliwy punkt dla problemu programowania całkowitoliczbowego zawartego w problemie tablicowym 3 × m × n ; jeśli wartość funkcji celu tego punktu jest zadowalająca (powiedzmy w porównaniu z wartością relaksacji programowania liniowego ), to użyj tego punktu; w przeciwnym razie zwiększ k i przejdź do następnego poziomu hierarchii. Można pokazać, że dla dowolnego ustalonego poziomu k przybliżenie ${\ Displaystyle G_ {k} (m, n)}$ podstawa Gravera ma liczność wielomianową ${\ Displaystyle O \ lewo (m ^ {g (k)} n ^ {k} \right)}$ i można je obliczyć w tak długim czasie.

Stała plastyczność parametrów: od złożoności wielomianowej do sześciennej złożoności czasowej

Złożoność czasowa rozwiązywania niektórych z omówionych powyżej aplikacji, takich jak wielowymiarowe problemy z tablicami, problemy z przepływem wielu towarów i problemy z programowaniem N -krotnych liczb całkowitych, jest zdominowana przez liczność odpowiedniej podstawy Gravera, która jest wielomianem ${\ Displaystyle O \ lewo (n ^ {g} \ prawej)}$ z zazwyczaj dużym stopniem g , który jest odpowiednią złożonością Gravera systemu. Przedstawiono znacznie szybszy algorytm, który w każdej iteracji znajduje najlepsze ulepszenie x + qg z q dodatnia liczba całkowita i element g w ${\ Displaystyle G (A)}$ bez jawnego konstruowania podstawy Gravera w czasie sześciennym ${\ Displaystyle O \ lewo (n ^ {3} \ prawej)}$ niezależnie od systemu. W terminologii złożoności sparametryzowanej oznacza to, że wszystkie te problemy są odpowiednio sparametryzowane, aw szczególności problemy tablicowe l × m × n sparametryzowane przez l i m , są stałymi parametrami możliwymi do zastosowania .

Zobacz też

• Lemat Gordana - kolejne narzędzie związane z zerowymi zbiorami macierzy liczb całkowitych.