Które całkowite programy liniowe są łatwe?

Próbując rozwiązać problem, ostatecznie wyraziłem jego część jako następujący program liczbowy całkowity. Tutaj są dodatnimi liczbami całkowitymi podanymi jako część danych wejściowych. Określony podzbiór zmiennych jest ustawiony na zero, a reszta może przyjmować dodatnie wartości całki: $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ $x_{ij}$

Zminimalizować

$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$

Z zastrzeżeniem:

$\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$

$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$

Chciałbym wiedzieć, czy ten program liczb całkowitych można rozwiązać w czasie wielomianowym; mój pierwotny problem został rozwiązany, jeśli tak, i muszę spróbować w inny sposób, jeśli tak nie jest. Więc moje pytanie brzmi:

Jak dowiedzieć się, czy dany program liniowy może być rozwiązany w czasie wielomianowym? Które całkowite programy liniowe są znane jako łatwe? W szczególności, czy powyższy program można rozwiązać w czasie wielomianowym? Czy mógłbyś wskazać mi jakieś odniesienia na ten temat?

reference-request linear-programming polynomial-time integer-programming integrality-gap gphilip
źródło

Odpowiedzi:

Jest to szczególny przypadek problemu z transportem (lub problemu z minimalnymi kosztami przepływu), dlatego można go rozwiązać w czasie wielomianowym. Macierz współczynników jest całkowicie niemodularna, ponieważ jest macierzą częstości grafu dwustronnego.

Przydatne mogą być następujące artykuły z Wikipedii.

Yoshio Okamoto
źródło

@Yoshio: Dziękuję, że odpowiada na mój konkretny problem (po tym, jak sam to zweryfikowałem). Czy znasz warunki inne niż całkowita niejednoznaczność, które gwarantują rozwiązanie wielomianowe?

gphilip 20.01.11

@ gphilip: Chciałbym streścić te pytania terminem „integralność wielościanów”, a literatura na ten temat jest ogromna. Książka „Optymalizacja kombinatoryczna: pakowanie i przykrycie” Gerarda Cornuejolsa (opublikowana w 2001 r.) Opisuje kilka wyników w tym zakresie.

Yoshio Okamoto,

@Yoshio: Czy możesz mi powiedzieć, dlaczego uważasz, że macierz współczynników jest macierzą częstości grafu dwustronnego? Przepraszam za moją ignorancję, ale mówiąc o matrycy współczynników, czy nie musimy najpierw przekonwertować wszystkich ograniczeń na formę standardową ( )? Gdy to zrobimy, macierz będzie miała -1 pozycji, a następnie nie będzie zgodna z definicją macierzy częstości (AFAIK). Czy też jest tak, że możemy mówić o macierzy współczynników bez uprzedniej konwersji ograniczeń do postaci standardowej?

A x \leq b

$Ax\le b$

gphilip

@gphilip: Przepraszam. Zrobiłem domyślny skrót i mówiłem o macierzy współczynników bez konwersji do postaci standardowej. Użyłem następujących skrótów. (1) Jeśli jest całkowicie niemodularny (w skrócie TU), to jest również TU, co oznacza, że nie musimy przejmować się kierunkiem nierówności. (2) Jeśli to TU, to to także TU, co oznacza, że nie musimy przejmować się ograniczeniami równości. (3) Każda podmacierz macierzy TU jest TU. Zastosowanie tych reguł do macierzy częstości grafu dwustronnego powinno udowodnić właściwość formy standardowej.

A

$A$

- A

$-A$

A

$A$

[A ∣ - A]

$[A \mid -A]$

Yoshio Okamoto,

Pozwól mi zmienić moje zasady skrótów w następujący sposób. (1) Duplikacja rzędu zachowuje całkowitą jednomodowość. (2) Odwrócenie znaku wiersza zachowuje całkowitą jednomodowość. Powinni wykonać pracę.

Yoshio Okamoto,

Ogólnie trudno powiedzieć. Ale wystarczającym warunkiem jest to, że macierz ograniczeń jest całkowicie niemodularna, a prawa strona jest zawsze liczbą całkowitą (w tym przypadku prawa strona jest liczbą całkowitą, ale nadal musisz sprawdzić brak jednomodliwości)

Powinieneś spojrzeć na to: http://en.wikipedia.org/wiki/Linear_program#Integer_unknowns

Vinicius dos Santos
źródło

Myślałem o twojej matrycy i wygląda ona całkowicie niemodularnie.

Vinicius dos Santos

@Vinicius: Czy możesz mi powiedzieć, dlaczego matryca wygląda dla ciebie zupełnie niejednoznacznie? Nie mogłem tego rozgryźć, pomimo komentarza Yoshio (proszę zobaczyć moją odpowiedź tam).

gphilip

@gphilip: Na stronie en.wikipedia.org/wiki/Unimodular_matrix w sekcji „Wspólne całkowicie niemodularne macierze”, pierwszy element zawiera 4 warunki wystarczające do tego, aby matryca była jednomodalna. Myślę, że te warunki, wraz ze skrótami skomentowanymi przez Yoshio, wystarczą, aby pokazać, że problem można rozwiązać w czasie wielomianowym.

Vinicius dos Santos

@gphilip: Jaka jest motywacja tego programu liniowego?

Vinicius dos Santos

@ Vinicius: Staramy się rozwiązać problem wyrażony w kategoriach modyfikujących macierz wejściową w określony sposób, aby uzyskać kolejną macierz o pewnych dobrych właściwościach. Ta płyta wyszła z jednego pod-problemu podczas procesu.

gphilip 21.01.11

Program liczb całkowitych o tylko równościach można rozwiązać za pomocą programu liniowego.

T ....
źródło

wydawało się to ważne dla samej siebie.

T ....

Nie nazwałbym tego programem całkowitym. Jest to układ równań liniowych nad liczbami całkowitymi, który można rozwiązać skutecznie, obliczając postać normalną Hermite.

Sasho Nikolov

@SashoNikolov zdegenerowany przypadek, ale zdecydowanie ważny.

T ....

dlaczego głosowanie negatywne?

T ....