Czy programowanie 0-1 ze stałą liczbą ograniczeń można rozwiązać wielomianowo?

11

W artykule „Programowanie liczb całkowitych ze stałą liczbą zmiennych” wykazano, że programowanie liczb całkowitych o stałej liczbie ograniczeń (lub zmiennych) można rozwiązać wielomianowo.

Czy to dotyczy programowania 0-1?

cc.complexity-theory integer-programming Prawidłowość
źródło

Czy programowanie 0-1 nie jest specjalnym przypadkiem programowania liczb całkowitych?

Nathann Cohen

3

Myślę, że nietrywialna część jest taka: jeśli masz algorytm czarnej skrzynki A, który jest w stanie rozwiązać programy liczb całkowitych ze stałą liczbą ograniczeń (ale dowolnie wiele zmiennych), nie jest oczywiste, jak użyć A do rozwiązania programów 0-1 ze stałą liczbą ograniczeń. Nie można po prostu dodać ograniczeń formy

dla każdej zmiennej

.

0 \leq x_{i} \leq 1

$0 \le x_i \le 1$

x_{i}

$x_i$

Jukka Suomela

3

Co to jest „program 0-1 ze stałą liczbą ograniczeń”? Czy ograniczenia

nie liczą?

0 \leq x_{i} \leq 1

$0\le x_i \le 1$

Jeffε

20

Zakładam, że przez „programowanie 0-1 ze stałą liczbą ograniczeń” masz na myśli następujący problem:

Maksymalizuj niektóre funkcje liniowe (x_1, x_2, ..., x_n) z zastrzeżeniem ograniczeń, że każdy x_i jest w {0,1} i stałej liczby dodatkowych ograniczeń liniowych.

Ten problem jest NP-zupełny nawet z 1 dodatkowym ograniczeniem, ponieważ w tej formie można zapisać plecak 0-1.

Robin Kothari
źródło

1

Również „plecak niezwiązany”, w którym masz tylko ograniczenia nieujemności i ograniczenia integralności bez górnych granic 1, jest wciąż trudny do NP.

daveagp

0

Lenstra pokazał we wspomnianym artykule, że problem wykonalności programu liczb całkowitych

$A_{m,n}$ $b \in \mathbb{Z}^m$
$x \in \mathbb{Z}^n$ $Ax \le b$

jest rozwiązywalny wielomianowo, jeśli n lub m jest stałe. (Zwróć uwagę na brak funkcji celu.) Ten wynik jest powszechnie stosowany w analizie sparametryzowanych problemów, tzn. Może być wykorzystany do udowodnienia możliwości ustalenia stałych parametrów przez redukcję.

muede
źródło

3

Nie jestem pewien, dlaczego to opublikowałeś, ale jeśli sugerujesz, że różnica między wersją wykonalności a wersją optymalizacyjną jest ważna, to nie, nie jest to ważne: algorytm wielomianowy dla wersji wykonalności można rozwiązać wersja optymalizacyjna również w czasie wielomianowym, łącząc ją z wyszukiwaniem binarnym.

Tsuyoshi Ito

-1

Programowanie liczb całkowitych 0-1 lub binarne programowanie liczb całkowitych (BIP) jest szczególnym przypadkiem programowania liczb całkowitych, w którym zmienne muszą mieć wartość 0 lub 1 (zamiast liczb całkowitych arbitralnych). Ten problem jest również klasyfikowany jako trudny do uzyskania przez NP, aw rzeczywistości wersja decyzyjna to NP-Complete.

Karan Sapra
źródło

3

Chociaż zarówno IP, jak i BIP są trudne dla NP, nie mówi to wiele o tym, czy IP i BIP ze stałą liczbą ograniczeń są trudne dla NP. Rzeczywiście, IP ze stałą liczbą ograniczeń jest w P, podczas gdy BIP ze stałą liczbą ograniczeń jest nadal NP-twardy.

Robin Kothari

-1

$k$ $2^k$

użytkownik8477
źródło

Czy programowanie 0-1 ze stałą liczbą ograniczeń można rozwiązać wielomianowo?

Odpowiedzi: