Programowanie liczb całkowitych ze stałą liczbą zmiennych

Słynny artykuł H. Lenstry Integer Programowanie z ustaloną liczbą zmiennych z 1983 r. Stwierdza, że programy liczb całkowitych o ustalonej liczbie zmiennych można rozwiązać wielomianem czasowym długości danych.

Interpretuję to w następujący sposób.

Programowanie liczb całkowitych ogólnie jest nadal NP-kompletne, ale jeśli mój typowy rozmiar problemu (powiedzmy około 10.000 zmiennych, dowolna liczba ograniczeń) jest wykonalny w praktyce, to mógłbym zbudować algorytm, który skaluje się wielomianowo pod względem liczby ograniczeń, ale nie w liczba zmiennych i ograniczeń.
Wynik ma również zastosowanie do programowania binarnego, ponieważ mogę wymusić dowolną liczbę całkowitą na 0-1, dodając odpowiednie ograniczenie.

Czy moja interpretacja jest poprawna?

Czy ten wynik ma jakieś praktyczne implikacje? To znaczy, czy jest dostępna implementacja, czy jest stosowana w popularnych rozwiązaniach takich jak CPLEX, Gurobi lub Mosek?

Niektóre cytaty z pracy:

Dla naszych celów długość ta może być zdefiniowana jako n · m · log (a + 2), gdzie a oznacza maksimum wartości bezwzględnych współczynników A i b. Rzeczywiście, prawdopodobnie nie istnieje żaden algorytm wielomianowy, ponieważ problem, o którym mowa, jest NP-zupełny

[...]

Przypuszczano [5], [10], że dla dowolnej stałej wartości n istnieje algorytm wielomianowy do rozwiązania problemu programowania liniowego liczb całkowitych. W niniejszym artykule dowodzimy tego przypuszczenia, przedstawiając taki algorytm. Stopień wielomianu, przez który można ograniczyć czas działania naszego algorytmu, jest funkcją wykładniczą n.

co.combinatorics linear-programming integer-programming

— Bernhard Kausler
źródło

„Mógłbym zbudować algorytm, który skaluje się wielomianowo pod względem liczby ograniczeń lub zmiennych, ale nie liczby zmiennych i ograniczeń”. Interesujący punkt / pytanie - do tej pory widzieliśmy, że jest to prawdą w przypadku ograniczeń (utrzymywanie liczby zmiennych ustalonych), ale być może byłoby interesujące zapytać, czy może to dotyczyć zmiennych (utrzymywanie liczby ustalonych ograniczeń) ? Intuicyjnie wydaje się, że to nie powinno być prawdą, w przeciwnym razie IP byłby ogólnie polityką, ale nie jestem pewien.

— usul

W części 4 artykułu Lenstra stwierdza, że „problem programowania liniowego liczb całkowitych o stałej wartości m jest rozwiązany wielomianowo”. (m jest liczbą przeciwwskazań) Wynika to z następstwa głównego wyniku. Ta sekcja nie jest dla mnie jasna. Z drugiej strony może zakłada stałe n AND m; co oznacza, że jest wielomianem w „a” (maksimum wartości bezwzględnych współczynników A i b). (W konsekwencji usunąłem część „lub zmienną” z powyższego pytania).

— Bernhard Kausler

@usul: to prawda i nie oznacza to, że IP to czas polytime. oznacza to tylko jeden jest algorytmem, który trwa w czasie gwałtownego a wielomianem względem a drugi odbywa wykładniczy czas w i wielomian

n

$n$

m

$m$

m

$m$

n

$n$

— Sasho Nikołow

Odpowiedzi:

Bieżący najszybszy algorytm ma w rzeczywistości długość liniową programu liczb całkowitych dla każdej stałej wartości . W swojej rozprawie doktorskiej Lokshtanov (2009) ładnie podsumowuje wyniki Lenstry (1983), Kannana (1987) i Franka i Tardosa (1987) według następującego twierdzenia. $n$

Programowanie całkowitą liniowa może być rozwiązany za pomocą operacje arytmetyczne i przestrzeń wielomianem . Tutaj jest liczbą bitów na wejściu, a liczbą zmiennych w całkowitym programie liniowym. $O(n^{2.5n+o(n)} \cdot L)$ $L$ $L$ $n$

Zatem problemem jest liniowy parametr o stałym parametrze sparametryzowany liczbą zmiennych.

1) Tak, całkowite programowanie liniowe jest „nadal” NP-kompletne. Czas działania powyższego wyniku teoretycznego zależy tylko liniowo od liczby wiązań, więc ładnie skaluje się pod względem liczby wiązań. Jednak nie znam faktycznej implementacji tego algorytmu.

2) Tak, obserwowanie, jak zmienne przyjmują wartości binarne.

Aktualizacja. Zależność od można faktycznie poprawić w czasie wykonywania Integer Linear Programming. Na podstawie Clarkson (1995) i Eisenbrand (2003) (patrz komentarze poniżej) można uzyskać algorytm z czasem działania gdzie to liczba ograniczeń, a to maksymalna liczba bitów wymagana do zakodowania ograniczenia lub funkcji celu. $L$

O (2^{n} n m + 8^{n} n \sqrt{m \log m} \log m + n^{2.5 n + o (n)} s \log m)

$O(2^nnm + 8^n n \sqrt{m \log m} \log m + n^{2.5n+o(n)}s\log m)$

m

$m$

s

$s$

— Serge Gaspers
źródło

Ach, dzięki za termin „liniowy parametr o ustalonych parametrach”. Na tym właśnie polega praca Lenstry. Zobacz także: en.wikipedia.org/wiki/Parameterized_complexity

— Bernhard Kausler

oczywista obserwacja: dla zmiennych binarnych algorytmy bruteforce zajmują czas , więc przypadek jest trywialny.

n

$n$

O (n 2^{n} m)

$O(n2^n m)$

— Sasho Nikolov

Dla wersji optymalizacyjnej ILP: jeśli potrzeba czasu aby rozwiązać problem ze współczynnikami wymiernymi i ze zmiennymi , ograniczeniami i bitami na ograniczenie, wówczas ILP można wykonać w operacje na -bit, gdzie jest (myślę) w najgorszym przypadku ; to jest oparty na pracy Eisenbranda : www2.math.uni-paderborn.de/fileadmin/Mathematik/AG-Eisenbrand/… .

T (n, m, s)

$T(n,m,s)$

n

$n$

m

$m$

s

$s$

O (2^{n} m + (\log m) T (n, f (n), s)

$O(2^n m + (\log m)T(n, f(n),s)$

O (s)

$O(s)$

f (n)

$f(n)$

n^{O (n)}

$n^{O(n)}$

— Ken Clarkson

Nie zmienia to podstawowych faktów twojej odpowiedzi, ale innym istotnym odniesieniem jest KL Clarkson. Algorytmy Las Vegas do programowania liniowego i liczb całkowitych, gdy wymiar jest mały. J. ACM 42 (2): 488–499, 1995, doi: 10.1145 / 201019.201036.

— David Eppstein,

Mój artykuł jest wadliwy dla ILP: w podstawowych przypadkach dla „małego” odniosłem się do algorytmów ILP dla wykonalności, kiedy powinienem był odwołać się do algorytmów rozwiązujących optymalizację. Dokument Eisenbranda odnotowuje to i podaje wyniki dla przypadku podstawowego; nie mogłem jednak znaleźć dokładnej zależności od w jego pracy. Możesz po prostu podłączyć wynik do części tego, co twierdziłem, gdzie , i tak . (Przepraszam, byłem zdezorientowany co do tego, jakie powinno być .) Wynik, ignorując ten średni termin, jest czymś w rodzaju operacji.

m

$m$

n

$n$

O (n^{2.5 n + o (n)} L)

$O(n^{2.5n+o(n)} L)$

T (n, f (n), s)

$T(n,f(n),s)$

f (n) = 4^{n}

$f(n)=4^n$

L = 4^{n} s

$L=4^n s$

f (n)

$f(n)$

O (2^{n} n m + n^{2.5 n + o (n)} (\log m) s)

$O(2^nnm+n^{2.5n+o(n)}(\log m) s)$

— Ken Clarkson

Oto kilka punktów dotyczących praktycznych implikacji wyników typu Lenstra oraz możliwych implementacji w CPLEX, Gurobi itp. Jednym z kluczowych kroków w większości takich algos dla IP jest rozgałęzienie w „dobrych” lub „cienkich” kierunkach, tj. hiperpłaszczyzny, wzdłuż których szerokość polytopu nie jest zbyt duża (wielomian w zmiennych i rozmiarze danych). Ale Mahajan i Ralphs ( tutaj przedruk ) pokazali, że problem wyboru optymalnego rozłączenia jest NP-zupełny. Trudno więc stworzyć praktycznie wydajne implementacje tej klasy alg.

Większość algorytmów zaimplementowanych w pakietach takich jak CPLEX można zaklasyfikować jako metody rozgałęziające. Ta rodzina technik zazwyczaj działa dobrze na instancjach IP, które są wykonalne i często są w stanie znaleźć prawie optymalne rozwiązania. Ale algos typu Lenstra koncentrują się na najgorszych przypadkach instancji IP, które na początku są niewykonalne, a celem jest udowodnienie ich całkowitej nieczytelności (i badają złożoność tego zadania). AFAIK, nie ma klasy problemów o praktycznym znaczeniu, które pasowałyby do tego opisu. Tak więc ludzie CPLEX / Gurobi prawdopodobnie nie wdrożą wkrótce algos typu Lenstra.

— kbala
źródło