¿Qué programas lineales enteros son fáciles?

Mientras intentaba resolver un problema, terminé expresando parte de él como el siguiente programa lineal entero. Aquí son todos enteros positivos dados como parte de la entrada. Un subconjunto especificado de las variables 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$

Me gustaría saber si este programa entero es solucionable en tiempo polinómico; mi problema original se resuelve si es así, y tengo que intentarlo de otra manera si no es así. Entonces mi pregunta es:

¿Cómo puedo determinar si un determinado programa lineal entero se puede resolver en tiempo polinómico? ¿Qué programas lineales enteros se sabe que son fáciles? En particular, ¿se puede resolver el programa anterior en tiempo polinómico? ¿Podría señalarme algunas referencias sobre esto?

reference-request linear-programming polynomial-time integer-programming integrality-gap gphilip
fuente

Respuestas:

Es un caso especial del problema de transporte (o el problema de flujo de costo mínimo), por lo que se puede resolver en tiempo polinómico. La matriz de coeficientes es totalmente unimodular ya que es la matriz de incidencia de un gráfico bipartito.

Los siguientes artículos de Wikipedia podrían ser útiles.

Yoshio Okamoto
fuente

@Yoshio: Gracias, eso responde a mi instancia de problema particular (una vez que lo he verificado por mí mismo). ¿Conoce otras condiciones además de la unimodularidad total que garanticen una solución de tiempo polinomial?

gphilip

@gphilip: Resumiría estas preguntas por el término "integralidad de los poliedros" y la literatura sobre este tema es enorme. El libro "Optimización combinatoria: embalaje y cobertura" de Gerard Cornuejols (publicado en 2001) describe varios resultados en esta línea.

Yoshio Okamoto

@Yoshio: ¿Podría decirme por qué cree que la matriz de coeficientes es la matriz de incidencia de un gráfico bipartito? Disculpe mi ignorancia, pero para hablar de una matriz de coeficientes, ¿no tenemos que convertir primero todas las restricciones a la forma estándar (

)? Una vez que hagamos eso, la matriz tendrá -1 entradas, y luego no coincidirá con la definición de una matriz de incidencia (AFAIK). ¿O es el caso de que podemos hablar de la matriz de coeficientes sin convertir primero las restricciones a la forma estándar?

A x \leq b

$Ax\le b$

gphilip

@gphilip: Disculpe. Hice un atajo implícito y estaba hablando de la matriz de coeficientes sin convertir a la forma estándar. Usé los siguientes atajos. (1) Si

es totalmente unimodular (TU, para abreviar), entonces

también es TU, lo que significa que no tenemos que preocuparnos por la dirección de las desigualdades. (2) Si

es TU, entonces

también es TU, lo que significa que no tenemos que preocuparnos por las restricciones de igualdad. (3) Cada submatriz de una matriz TU es TU. La aplicación de estas reglas a la matriz de incidencia de un gráfico bipartito debería demostrar la propiedad de la forma estándar.

A

$A$

- A

$-A$

A

$A$

[A ∣ - A]

$[A \mid -A]$

Yoshio Okamoto

Permítanme cambiar mis reglas de acceso directo de la siguiente manera. (1) La duplicación de una fila mantiene la unimodularidad total. (2) La inversión del signo de una fila mantiene la unimodularidad total. Deberían hacer el trabajo.

Yoshio Okamoto

En general, es difícil de decir. Pero una condición suficiente es que su matriz de restricción es totalmente unimodular y el lado derecho siempre es entero (en este caso, el lado derecho es entero, pero aún debe verificar la unimodularidad)

Debes echar un vistazo a esto: http://en.wikipedia.org/wiki/Linear_program#Integer_unknowns

Vinicius dos Santos
fuente

Estaba pensando en tu matriz y se ve totalmente inimodular.

Vinicius dos Santos

@Vinicius: ¿Podrías decirme por qué la matriz te parece totalmente inimodular? No pude resolver esto, a pesar del comentario de Yoshio (vea mi respuesta allí).

gphilip

@gphilip: en en.wikipedia.org/wiki/Unimodular_matrix en la sección "Matrices comunes totalmente unimodulares", el primer elemento enumera 4 condiciones suficientes para que una matriz sea unimodular. Creo que estas condiciones, junto con los atajos que comentó Yoshio, son suficientes para mostrar que el problema se puede resolver en tiempo polinómico.

Vinicius dos Santos

@gphilip: ¿Cuál es la motivación para este programa lineal?

Vinicius dos Santos

@Vinicius: Estamos tratando de resolver un problema expresado en términos de modificación de una matriz de entrada de una determinada manera para obtener otra matriz con algunas buenas propiedades. Este LP surgió de un subproblema durante el proceso.

gphilip

Un programa entero con solo igualdades puede resolverse mediante un programa lineal.

T ....
fuente

Esto parecía importante por sí mismo.

T ....

No llamaría a eso un programa entero. Es un sistema de ecuaciones lineales sobre los enteros, que se puede resolver de manera eficiente al calcular la forma normal de Hermite.

Sasho Nikolov

@SashoNikolov es un caso degenerado pero definitivamente válido.

T ....

¿Por qué voto negativo?

T ....