¿La brecha de integralidad cero implica brecha de dualidad cero para ciertos problemas?

Sabemos que si la brecha entre los valores de un programa entero y su dual (la "brecha de dualidad") es cero, entonces las relajaciones de programación lineal del programa entero y la dual de la relajación, ambos admiten soluciones integrales (integralidad "cero" brecha"). Quiero saber si lo contrario es válido, al menos en algunos casos.

$P: \max\{1^Tx: Ax \leq 1, x\in \{0,1\}^n\}$ $A$ $0-1$ $P'$ $P$ $P'$

Agradecería cualquier contraejemplo o punteros ...

ds.algorithms optimization linear-programming integrality-gap Ankur
fuente

@Kaveh no está seguro de que los algoritmos de aproximación sean la etiqueta correcta aquí. o incluso ds.algorithms

Suresh Venkat

En el primer párrafo, ¿qué quieres decir con dual de un programa entero? Es útil mirar el libro de Schrijver sobre programación lineal y entera para comprender los conceptos básicos de la teoría poliédrica y, en particular, cuando las relajaciones de programación lineal tienen vértices enteros. Las matrices TUM y los sistemas de desigualdades TDI son relevantes para su pregunta.

Chandra Chekuri

@Suresh, ¿la programación lineal y la optimización no caen en los algoritmos?

Kaveh

@ChandraChekuri Estoy hablando de programas lineales enteros; entonces el dual es el dual estándar de un ILP para el cual se sostiene la dualidad débil. La dificultad aquí es que las condiciones suficientes para la integralidad de las soluciones LP (primarias) (como TUM / balanceado, etc.) parecen pasar por el concepto aparentemente más fuerte de integralidad de las soluciones de la LP primaria y su LP dual. Esto me hizo preguntarme si la integralidad de la solución primaria implica la integralidad de la solución dual, al menos para los coeficientes integrales. PD: ¡Podría caminar hasta Siebel y podríamos hablar allí! ¡Estuve en tu clase hace algunos años!

Ankur

Esta pregunta en particular está más cerca de las etiquetas que tiene actualmente.

Suresh Venkat

Respuestas:

Aquí hay una instancia que podría estar cerca de un contraejemplo del reclamo.

Considere LP y su doble para la matriz $P = \max \{ 1^T x \,|\, Ax \leq 1, x \leq 1, x \geq 0\}$ $P' = \min \{1^Ty + 1^Tz ~|~ A^Ty + z \geq 1, ~y \geq 0, z \geq 0 \}$ $12 \times 6$

$A = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 1 & 0 & 0 \end{bmatrix}\,.$

Una solución óptima de está dada por (todas las otras variables son cero), con el valor de la función objetivo del . La solución óptima de viene dado por el vector . Si resuelve como un programa entero, el valor óptimo de la función objetivo es solo , y es una solución óptima. $P'$ $y_1=y_2=y_{12}=1$ $3$ $P$ $x = [0.5~0.5~0~1~0.5~0.5]^T$ $P$ $2$ $x = [1~0~0~1~0~0]$

En resumen, el LP tiene una solución óptima integral, pero su doble no tiene una solución óptima integral. Los roles primarios-duales se invierten de la configuración que Ankur quería. Pero dada la naturaleza de la dualidad LP, esta instancia aún podría considerarse un contraejemplo de la declaración general de la reclamación original. $P'$ $P$

kbala
fuente

¡Gracias! Eso funciona! ¿Cómo se te ocurrió este ejemplo? ¿Hay una clase de problemas de los que se extrae?

Ankur

La matriz es una modificación de la matriz límite de una tira de Mobius, dada en nuestro artículo sobre ciclos homólogos óptimos. He estado jugando con tales matrices de límites recientemente y, por lo tanto, comencé naturalmente con esta matriz para crear el ejemplo que di.

kbala