¿Qué tan rápido podemos resolver un programa lineal entero totalmente unimodular?

(Este es un seguimiento de esta pregunta y su respuesta ).

Tengo el siguiente programa lineal entero entero unimodular (TU) (ILP). Aquí son todos enteros positivos dados como parte de la entrada. Un subconjunto especificado de las variables x i j se establece en cero y el resto puede tomar valores integrales positivos:$\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$$x_{ij}$

Minimizar

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

Sujeto a:

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

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

La matriz de coeficientes de la forma estándar es una matriz con entradas de - 1 , 0 , 1 .$(2\ell+m)\times \ell m$${-1,0,1}$

Mi pregunta es:

¿Cuáles son los mejores límites superiores conocidos para el tiempo de ejecución de algoritmos de tiempo polinómico que resuelven tal ILP? ¿Podría señalarme algunas referencias sobre esto?

Hice un poco de búsqueda, pero en la mayoría de los lugares se detienen diciendo que un TU ILP se puede resolver en tiempo polinómico usando algoritmos de tiempo polinómico para LP. Una cosa que parecía prometedora es un artículo de 1986 de Tardos [1] donde demuestra que dichos problemas pueden resolverse en el tiempo polinomial en el tamaño de la matriz de coeficientes. Sin embargo, hasta donde pude deducir del documento, el tiempo de ejecución de ese algoritmo depende a su vez del tiempo de ejecución de un algoritmo de tiempo polinómico para resolver LP.

¿Conocemos algoritmos que resuelvan este caso especial (de TU ILP) significativamente más rápido que los algoritmos generales que resuelven el problema de LP?

Si no,

¿Qué algoritmo para LP resolvería tal ILP más rápido (en un sentido asintótico)?

[1] Un algoritmo fuertemente polinómico para resolver programas combinatorios lineales, Eva Tardos, Operations Research 34 (2), 1986

Creo que en una clase de matrices totalmente unimodulares , por Yannakakis, da una respuesta a su pregunta para un caso especial de TU ILP (siempre que no haya ciclos impares en un gráfico bipartito obtenido al ver la matriz de coeficientes como una matriz de adyacencia).

En ese documento hay una referencia a los algoritmos polinómicos para una clase de programas lineales , que parece manejar todas las matrices totalmente unimodulares, pero no estoy seguro de cuánto más eficiente es en comparación con los algoritmos genéricos para LP.

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

Se ha demostrado que el LP totalmente unimodular se puede resolver en un tiempo fuertemente polinomial bajo un "supuesto de degeneración" - enlace aquí (por lo tanto, si el ILP tiene una formulación Totalmente Unimodular (TU) con los mismos supuestos, entonces este algoritmo resolvería un TU ILP, en tiempo polinomial fuerte. Este es un desarrollo de los métodos de Tardos e implica límites más estrictos para una formulación de ILP TU (totalmente unimodular).