Jak szybko możemy rozwiązać całkowicie nieimodularny program liniowy liczb całkowitych?

(Jest to kontynuacja tego pytania i odpowiedzi ).

Mam następujący całkowicie nieimodularny (TU) całkowity program liniowy (ILP). Tutaj są dodatnimi liczbami całkowitymi podanymi jako część danych wejściowych. Określony podzbiór zmiennych x i j jest ustawiony na zero, a reszta może przyjmować dodatnie wartości całkowite:$\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$

Macierz współczynników formy standardowej to macierz z wpisami od - 1 , 0 , 1 .$(2\ell+m)\times \ell m$${-1,0,1}$

Moje pytanie brzmi:

Jakie są najlepsze górne granice znane z czasu działania algorytmów wielomianowych, które rozwiązują taki ILP? Czy mógłbyś wskazać mi jakieś odniesienia na ten temat?

Przeprowadziłem pewne wyszukiwanie, ale w większości miejsc przestają mówić, że TU ILP można rozwiązać w czasie wielomianowym za pomocą algorytmów czasu wielomianowego dla LP. Jedną rzeczą, która wyglądała obiecująco, jest praca Tardosa z 1986 r. [1], w której udowadnia ona, że ​​takie problemy można rozwiązać w wielomianach czasowych o wielkości macierzy współczynników. O ile mogłem zrozumieć na podstawie artykułu, czas działania tego algorytmu zależy z kolei od czasu działania algorytmu wielomianowego do rozwiązywania LP.

Czy znamy algorytmy, które rozwiązują ten szczególny przypadek (TU ILP) znacznie szybciej niż ogólne algorytmy rozwiązujące problem LP?

Jeśli nie,

Który algorytm LP rozwiązałby taki ILP najszybciej (w sensie asymptotycznym)?

[1] Silnie wielomianowy algorytm do rozwiązywania kombinatorycznych programów liniowych, Eva Tardos, Operations Research 34 (2), 1986

Wierzę, że w klasie całkowicie niemodularnych macierzy , autorstwa Yannakakisa, daje odpowiedź na twoje pytanie dotyczące szczególnego przypadku ILU TU (za każdym razem, gdy na grafie dwudzielnym nie ma cykli nieparzystych uzyskanych przez widzenie macierzy współczynników jako macierzy przylegania).

W tym artykule jest odniesienie do algorytmów wielomianowych dla klasy programów liniowych , które wydają się obsługiwać wszystkie całkowicie niemodularne macierze, ale nie jestem pewien, o ile bardziej wydajne w porównaniu do algorytmów ogólnych dla LP.

$O([n^3/\ln n]L)$

Wykazano, że całkowicie niemodularna LP jest możliwa do rozwiązania w silnie wielomianowym czasie przy „założeniu degeneracji” - link tutaj (zatem jeśli ILP ma sformułowanie Totally Unimodular (TU) o takich samych założeniach, to ten algorytm rozwiązałby IL TU, w silny czas wielomianowy. Jest to rozwinięcie metod Tardosa i implikuje ściślejsze wiązania z formułą ILP TU (Totally Unimodular).