Co wiadomo na temat rozwiązań rzadkich problemów z programowaniem liniowym?

Jeśli mam zestaw ograniczeń liniowych, w których każde ograniczenie ma co najwyżej (powiedzmy) 4 zmienne (wszystkie nieujemne i o współczynnikach {0,1}, z wyjątkiem jednej zmiennej, która może mieć współczynnik -1), co wiadomo o rozwiązaniu przestrzeń? Nie interesuje mnie wydajne rozwiązanie (choć proszę wskazać, czy jedno jest znane) niż wiedza o tym, jak małe może być minimum funkcji celu, w zależności od liczby zmiennych i liczby ograniczeń oraz liczby zmiennych na przymus.

Mówiąc konkretniej, program jest podobny

minimalizuj t
  podlega
dla wszystkich i, x_i jest dodatnią liczbą całkowitą
x1 + x2 + x3 - t <0
x1 + x4 + x5 - t <0
...
x3 + x6 - t ≥ 0
x1 + x2 + x7 - t ≥ 0
...

Jeśli potrzebne jest konkretne pytanie, to czy przypadek minimalnego rozwiązania spełnia t <= O (max {# zmiennych, # ograniczeń}), przy czym stała w O () zależy od rzadkości? Ale nawet jeśli odpowiedź brzmi „nie”, bardziej interesuje mnie wiedza na temat tego, jaki podręcznik lub artykuł powinienem studiować w celu omówienia takich kwestii, i czy istnieje pewien obszar nauki poświęcony tego rodzaju rzeczom, ale po prostu nie wiem warunki do wyszukania. Dziękuję Ci.

Aktualizacja: Po dalszym zastanowieniu (i przemyśleniu dość prostej redukcji 3SAT do ILP, która wykorzystuje ograniczenia z trzema zmiennymi), zdaję sobie sprawę, że kwestia współczynników jest krytyczna (jeśli będzie skuteczny algorytm). Mówiąc dokładniej, wszystkie zmienne x_i mają 0 lub 1 współczynniki (co najwyżej trzy 1 współczynniki w jednym ograniczeniu), a wszystkie zmienne t mają -1 współczynniki, a wszystkie porównania mają zmienne po lewej i 0 po prawej. Zaktualizowałem powyższy przykład, aby wyjaśnić.

Odpowiedź na to pytanie (przynajmniej na konkretne pytanie dotyczące liniowego ograniczenia rozwiązania) brzmi „nie”. Jest to część następującego artykułu: http://arxiv.org/abs/1011.3493 . Twierdzenie 5.1 było motywacją do tego pytania.

Kontrprzykład to:

skrzynka podstawowa:

a_1 „+ b_1” - t ≥ 0
a_1 '' + b_1 '' - t ≥ 0
a_1 + b_1 '- t ≤ -1
a_1 „+ b_1” ”- t ≤ -1

przypadek rekurencyjny:

a_n '+ b_n' + a_ {n-1} - t ≥ 0
a_n '' + b_n '' + a_ {n-1} - t ≥ 0
a_n + b_n '+ a_ {n-1}' '- t ≤ -1
a_n '+ b_n' + a_ {n-1} '' - t ≤ -1

wraz z wymaganiem, aby wszystkie były nieujemne.

Można udowodnić przez indukcję, że każde rzeczywiste rozwiązanie musi spełniać a_n ''> = a_n + 2 ^ n. Zmieniamy nierówności „<0” na „≤ -1”, ponieważ każde rozwiązanie liczb całkowitych spełnia „≤ -1” wtedy i tylko wtedy, gdy spełnia „<0”.

Morał jest taki, że n nierówności w tej formie mogą mieć właściwość polegającą na tym, że wszystkie rozwiązania liczb całkowitych mają co najmniej jedną liczbę całkowitą co najmniej wykładniczą in, z pewnością nie ograniczoną liniowo, jak pierwotnie podejrzewaliśmy.

Jeśli macierz współczynników jest całkowicie niemodularna , wówczas istnieje skuteczne rozwiązanie za pomocą zwykłego programowania liniowego. Dotyczy to każdej ILP, nie tylko rzadkiej - chociaż istnieje większe prawdopodobieństwo, że będziesz w stanie wykorzystać tę właściwość do rzadkiej ILP, takiej jak Twoja.

Podejrzewam, że już o tym wiesz, więc pozwól, że spróbuję dać ci lepszą odpowiedź. Zanim zbyt głęboko zastanowimy się nad szczegółami, odpowiedź na konkretne pytanie brzmi „tak”, istnieje granica. Przecięcie n nierówności w m zmiennych definiuje polytop. Ponieważ współczynniki są tak dobrze zachowane, przy pomocy małej arytmetyki możemy obliczyć górną granicę wymiaru współrzędnych jej wierzchołków. Daje to bardzo łatwą górną granicę wymiaru dowolnego punktu liczb całkowitych w obrębie wielopola, a tym samym rozwiązania twojego programu liczb całkowitych. Próbowałeś już tego?

W szczególności twój problem ma dość strukturę (jestem ciekawy, skąd on pochodzi?), Więc jestem pewien, że możemy być bardziej precyzyjni, jeśli omówimy go dalej.

Teraz, aby uzyskać bardziej ogólne pytanie o znalezienie informacji na ten temat. Jest to rodzaj problemu, który tradycyjnie mieści się w teorii programowania liniowego i liczb całkowitych, podzbioru programowania matematycznego.

Jest to dość aktywny obszar badań, ale większość prac odbywa się w działach badań operacyjnych pod hasłami „optymalizacja” i „programowanie matematyczne” zamiast informatyki. Dostępnych jest wiele podręczników na ten temat. Możesz wziąć pod uwagę ten autorstwa Wolseya , którego używamy w Berkeley. Oto niewykorzystana lista mitów i kontrprzykładów Greenberga, w tym programowanie liczb całkowitych i liniowych, które mogą dać ci wyobrażenie o tym, co ludzie biorą pod uwagę przy analizie takich problemów. Wolsey jest gęsta, ale dość dobre miejsce na rozpoczęcie - istnieje szereg technik analizy ILP i poprawy formułowania problemów do punktu wydajności.

Pozwól, że dodam, że jeśli zastosujesz podejście naiwne, sugeruję, analizując geometrię polytopu, wyszukiwane terminy dotyczyłyby ograniczenia rozmiaru współrzędnych wierzchołków polytopu. Terminy te pojawiają się częściej w literaturze matematycznej na temat polytopów.

To konto może Cię zainteresować:

http://en.wikipedia.org/wiki/Polyhedral_combinatorics

w szczególności artykuł G. Zieglera:

Wykłady na politytopach 0-1

w:

Kalai, Gil; Ziegler, Günter M. (2000), Polytopes: Combinatorics and Computation, DMV Seminar, 29, Birkhäuser, ISBN 9783764363512.