Programación entera con un número fijo de variables.

El famoso artículo de 1983 de H. Lenstra Integer Programming With A Fixed Number Of Variables establece que los programas enteros con un número fijo de variables pueden resolverse en el tiempo polinomial en la longitud de los datos.

Lo interpreto de la siguiente manera.

La programación de enteros en general todavía es NP completa, pero si el tamaño de mi problema típico en cuestión (por ejemplo, alrededor de 10.000 variables, un número arbitrario de restricciones) es factible en la práctica, entonces podría construir un algoritmo que escale polinomialmente en el número de restricciones, pero no en El número de variables y restricciones.
El resultado también es aplicable para la programación binaria, ya que puedo forzar cualquier número entero a 0-1 agregando una restricción apropiada.

¿Es correcta mi interpretación?

¿Este resultado tiene alguna implicación práctica? Es decir, ¿hay una implementación disponible o se usa en solucionadores populares como CPLEX, Gurobi o Mosek?

Algunas citas del periódico:

Esta longitud puede, para nuestros propósitos, definirse como n · m · log (a + 2), donde a denota el máximo de los valores absolutos de los coeficientes de A y b. De hecho, no es probable que exista tal algoritmo polinómico, ya que el problema en cuestión es NP-completo

[...]

Se conjeturó [5], [10] que para cualquier valor fijo de n existe un algoritmo polinómico para la solución del problema de programación lineal de enteros. En el presente trabajo demostramos esta conjetura exhibiendo dicho algoritmo. El grado del polinomio por el cual se puede limitar el tiempo de ejecución de nuestro algoritmo es una función exponencial de n.

co.combinatorics linear-programming integer-programming Bernhard Kausler
fuente

"Podría construir un algoritmo que escale polinomialmente en el número de restricciones o variables, pero no en el número de variables y restricciones". Punto / pregunta interesante: hasta ahora hemos visto que esto es cierto para las restricciones (manteniendo fijo el número de variables), pero tal vez sería interesante preguntar si también podría ser cierto para las variables (manteniendo fijo el número de variables) ? Intuitivamente, parece que no debería ser cierto, de lo contrario, IP sería polytime en general, pero no estoy seguro.

usul

En la sección 4 del artículo, Lenstra afirma que "el problema de la programación lineal entera con un valor fijo de m es polinomialmente solucionable". (m es el número de restricciones) Esto sigue como un corolario del resultado principal. Esta sección no está clara para mí. Pensándolo mejor, tal vez asume nYm fijos; lo que significa que es polinomial en "a" (el máximo de los valores absolutos de los coeficientes de A y b). (Como consecuencia, eliminé la parte "o variables" de mi pregunta anterior).

Bernhard Kausler

@ usul: es cierto y no implica que IP sea polytime. solo significa que hay un algoritmo que toma tiempo exponencial en y polinomio en otro que toma tiempo exponencial en polinomio en

n

$n$

m

$m$

m

$m$

n

$n$

Sasho Nikolov

Respuestas:

El algoritmo más rápido actual es en realidad lineal en la longitud del programa lineal entero para cada valor fijo de . En su tesis doctoral, Lokshtanov (2009) resume muy bien los resultados de Lenstra (1983), Kannan (1987) y Frank y Tardos (1987) según el siguiente teorema. $n$

Programación lineal entera se puede resolver utilizando operaciones aritméticas y polinomio espacio en . Aquí es el número de bits en la entrada el número de variables en el programa lineal entero. $O(n^{2.5n+o(n)} \cdot L)$ $L$ $L$ $n$

Por lo tanto, el problema es el parámetro lineal lineal parametrizado por el número de variables.

1) Sí, la programación lineal entera está "todavía" completada por NP. El tiempo de ejecución del resultado teórico anterior depende solo linealmente del número de restricciones, por lo que se ajusta muy bien en el número de restricciones. Sin embargo, no conozco ninguna implementación real de este algoritmo.

2) Sí, hacer que las variables tomen valores binarios es sencillo como lo observó.

Actualizar. La dependencia de realidad se puede mejorar en el tiempo de ejecución para la programación lineal entera. Basado en Clarkson (1995) y Eisenbrand (2003) (ver los comentarios a continuación) se puede obtener un algoritmo con tiempo de ejecución donde es el número de restricciones y es el número máximo de bits necesarios para codificar una restricción o la función objetivo. $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
fuente

Ah, gracias por el término "parámetro fijo lineal". De eso se trata el artículo de Lenstra. Ver también: en.wikipedia.org/wiki/Parameterized_complexity

Bernhard Kausler

solo una observación obvia: para variables binarias, los algoritmos de fuerza bruta toman tiempo , por lo que ese caso es trivial.

n

$n$

O (n 2^{n} m)

$O(n2^n m)$

Sasho Nikolov

Para la versión de optimización de ILP: si se necesita tiempo para resolver un problema con coeficientes racionales y con variables, restricciones y bits por restricción, entonces ILP se puede hacer en operaciones en racionales de -bit, donde es (creo) en el peor de los casos ; esto se basa en el documento de Eisenbrand: 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

Esto no cambia los hechos básicos de su respuesta, pero otra referencia relevante es KL Clarkson. Algoritmos de Las Vegas para programación lineal y entera cuando la dimensión es pequeña. J. ACM 42 (2): 488-499, 1995, doi: 10.1145 / 201019.201036.

David Eppstein

Mi artículo tiene errores para ILP: en casos básicos para "pequeño" , me referí a los algoritmos de ILP para la viabilidad, cuando debería haberme referido a algoritmos para resolver la optimización. El artículo de Eisenbrand señala esto y da resultados para el caso base; sin embargo, no pude averiguar la dependencia exacta de en su artículo. Simplemente puede conectar el resultado en la parte de lo que reclamé, donde , y entonces . (Lo siento, estaba confundido acerca de lo que debería ser). El resultado, ignorando ese término medio, es algo como operaciones.

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

Aquí hay un par de puntos con respecto a las implicaciones prácticas de los resultados de tipo Lenstra, y las posibles implementaciones en CPLEX, Gurobi, etc. Uno de los pasos clave en la mayoría de tales algos para IP es ramificarse en direcciones "buenas" o "delgadas", es decir, hiperplanos a lo largo de los cuales el ancho del politopo no es demasiado grande (polinomio en variables y tamaño de datos). Pero Mahajan y Ralphs (preimpresión aquí ) mostraron que el problema de seleccionar una disyunción óptima es NP-completo. Por lo tanto, parecería difícil crear implementaciones prácticamente eficientes de esta clase de algos.

La mayoría de los algos implementados en paquetes como CPLEX podrían clasificarse como métodos de ramificación y corte. Esta familia de técnicas generalmente funciona bien en instancias de IP que son factibles, y a menudo son capaces de encontrar soluciones casi óptimas. Pero el foco de los algos tipo Lenstra está en las peores instancias de IP que no son factibles para comenzar, y el objetivo es demostrar su inviabilidad entera (y estudian la complejidad de esta tarea). AFAIK, no hay una clase de problemas con relevancia práctica que se ajuste a esta descripción. Entonces, la gente de CPLEX / Gurobi probablemente no implementaría algos tipo Lenstra en el corto plazo.

kbala
fuente