¿La complejidad más rápida conocida para el algoritmo combinatorio de ILP?

Me pregunto, ¿cuál es el algoritmo más conocido, en términos de notación Big- , para resolver la programación lineal entera? $O$

Sé que el problema es completo, por lo que no espero nada polinomial. Y sé que hay muchas heurísticas y otras que se usan en aplicaciones prácticas como CPLEX, pero estoy más interesado en la complejidad formal, en el peor de los casos, de un algoritmo exacto. $NP$

Algunos completos de tienen algoritmos en el tiempo donde y es un polinomio. La cubierta de Vértice, el conjunto independiente y el 3SAT entran en esta categoría, pero en general SAT y TSP no (hasta donde sabemos). $NP$ $O(b^n p(n))$ $1 < b < 2$ $p$

¿Se pueden hacer tales declaraciones sobre la programación de enteros o subinstancias particulares?

Si alguien tiene una referencia para el problema relacionado de la aritmética de presburger gratuita de cuantificador, también me interesaría mucho.

algorithms complexity-theory reference-request np-complete integer-programming jmite
fuente

Aardal, Karen, Robert Weismantel y Laurence A. Wolsey. "Enfoques no estándar para la programación de enteros". Matemática Aplicada Discreta 123.1 (2002): 5-74. da muchas referencias Tal vez pueda encontrar la respuesta al mirar esto, o al rastrear qué documentos más nuevos citan este. Mire la Sección 2 en particular.

Juho

¿Cuál es la diferencia entre y ?

O ({1.1}^{n})

$O(1.1^{n})$

O (99^{n})

$O(99^{n})$

barba gris

@greybeard, no mucho para P vs NP, pero mucho en términos de capacidad de seguimiento de la vida real, dependiendo de las constantes, hace una gran diferencia.

jmite

Desearía haber estado esperando un recordatorio inicial de que dado y , una diferencia en da como resultado un conjunto diferente de funciones, mientras que uno en no lo hace y, en consecuencia, se abstrae .

O (b^{n})

$O(b^n)$

O (c n)

$O(cn)$

b

$b$

c

$c$

barba gris

@jmite Hecho. ¿Le sirvió de referencia o pudo encontrar alguna información nueva?

Juho

Respuestas:

Por lo que puedo decir al buscar, la encuesta definitiva parece ser:

Aardal, Karen, Robert Weismantel y Laurence A. Wolsey. "Enfoques no estándar para la programación de enteros". Matemática Aplicada Discreta 123.1 (2002): 5-74.

En particular, la Sección 2.1 analiza la programación de enteros en una dimensión acotada y presenta algoritmos debidos a diferentes autores. De hecho, la encuesta enumera muchas referencias y discute algunas implementaciones prácticas.

Para un número fijo de variables, la programación lineal entera es un tiempo polinómico que el algoritmo de Lenstra puede resolver.

Juho
fuente

bien, pero ¿cuál es el algoritmo más rápido conocido?

vzn

@vzn No lo sé, esta es a lo sumo una respuesta que cubre "subinstancias particulares".

Juho