Wie schnell können wir ein völlig unimodulares ganzzahliges lineares Programm lösen?

(Dies ist ein Follow-up zu dieser Frage und ihrer Antwort .)

Ich habe das folgende völlig unimodulare (TU) ganzzahlige lineare Programm (ILP). Hier sind alle positive ganze Zahlen, die als gegeben sind Teil der Eingabe. Eine angegebene Teilmenge der Variablen wird auf Null gesetzt, und der Rest kann positive Integralwerte annehmen:x i $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$$x_{ij}$

Minimieren

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

Vorbehaltlich:

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

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

Die Koeffizientenmatrix der Standardform ist eine Matrix mit Einträgen von .$(2\ell+m)\times \ell m$${-1,0,1}$

Meine Frage ist:

Was sind die besten bekannten Obergrenzen für die Laufzeit von Polynomial-Time-Algorithmen, die eine solche ILP lösen? Können Sie mich auf einige Referenzen hinweisen?

Ich habe ein bisschen gesucht, aber an den meisten Stellen hört man damit auf zu sagen, dass ein TU ILP in Polynomialzeit mit Polynomialzeit-Algorithmen für LP gelöst werden kann. Vielversprechend erschien 1986 eine Arbeit von Tardos [1], in der sie nachweist, dass solche Probleme in der Größe der Koeffizientenmatrix zeitpolynomiell gelöst werden können. Soweit ich dem Artikel entnehmen konnte, hängt die Laufzeit dieses Algorithmus jedoch wiederum von der Laufzeit eines Polynom-Zeit-Algorithmus zum Lösen von LP ab.

Kennen wir Algorithmen, die diesen Sonderfall (der TU ILP) deutlich schneller lösen als die allgemeinen Algorithmen, die das LP-Problem lösen?

Wenn nicht,

Welcher Algorithmus für LP würde eine solche ILP am schnellsten (im asymptotischen Sinne) lösen?

[1] Ein stark polynomieller Algorithmus zur Lösung kombinatorischer linearer Programme, Eva Tardos, Operations Research 34 (2), 1986

Ich glaube , Yannakakis gibt auf On a class of total unimodular matrices eine Antwort auf Ihre Frage zu einem speziellen Fall der TU ILP (wenn es keine ungeraden Zyklen in einem zweigeteilten Graphen gibt, der durch Betrachten der Koeffizientenmatrix als Adjazenzmatrix erhalten wird).

In diesem Artikel wird auf Polynomalgorithmen für eine Klasse von linearen Programmen verwiesen , die anscheinend alle völlig unimodularen Matrizen verarbeiten. Ich bin mir jedoch nicht sicher, wie viel effizienter sie im Vergleich zu generischen Algorithmen für LPs sind.

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

Es hat sich gezeigt, dass eine vollständig unimodulare LP in stark polynomieller Zeit unter einer "Degenerationsannahme" lösbar ist (wenn der ILP also eine vollständig unimodulare (TU) Formulierung mit denselben Annahmen hat, würde dieser Algorithmus einen TU ILP lösen, in Starke Polynomzeit Dies ist eine Entwicklung aus Tardos 'Methoden und impliziert engere Grenzen für eine TU (Totally Unimodular) ILP-Formulierung.