Técnicas para probar los límites en la brecha de integralidad en LP (SDP)

Se necesita una referencia a las técnicas para demostrar que el tamaño de una brecha de integralidad está limitado por alguna expresión para un LP particular (o SDP, pero menos importante). También sería bueno tener una referencia a un lugar donde se describan técnicas para minimizar las brechas de integralidad. Soy nuevo en el área de las brechas de integralidad, que parece bastante grande, por lo que la descripción de los resultados clásicos es más preferible que la de algo interesante.

ds.algorithms reference-request linear-programming semidefinite-programming integrality-gap Grigory Yaroslavtsev
fuente

Su título "Brechas de integralidad en LP (SDP)" es demasiado general, es mejor ser más específico con el título de su pregunta. El título no es una etiqueta, debe indicar su pregunta, algo así como: "técnicas para probar los límites en la brecha de integralidad en LP (SDP)".

Kaveh

Respuestas:

En aras de la discusión, considere el problema de minimización con la función objetivo . No puedo pensar en ninguna técnica dominante para probar las lagunas de integralidad. Por lo general, el esquema de la prueba es la forma implícita en la definición de brecha de integralidad y los detalles son específicos del problema. $f(x)$

Para demostrar que la brecha de integralidad es pequeña (es decir, LP es buena) es habitual el siguiente esquema de prueba. Use algún tipo de redondeo (a menudo aleatorio) para construir una solución integral con para cada factible por LP (y para cada instancia de problema). Se deduce que la brecha de integralidad es como máximo . $x'$ $f(x') \le c\cdot f(x)$ $x$ $c$

Para demostrar que la brecha de integralidad es grande, es habitual el siguiente esquema. Exhiba una instancia problemática con una solución factible de LP barata y pruebe que no hay una buena solución integral.

Warren Schudy
fuente

Parece que debería ser , ¿verdad?

f (x^{'}) \leq c f (x)

$f(x') \le c f(x)$

Grigory Yaroslavtsev

Gracias, el enfoque que describió para probar el límite superior en el tamaño de la brecha es exactamente lo que estoy haciendo. Construir no es un problema en mi caso, y luego necesito demostrar la desigualdad . Esto ahora se hace de una manera específica del problema, que apenas se generaliza a problemas similares de la misma clase, por lo que tenía curiosidad de saber si existe alguna maquinaria general para esto.

x^{'}

$x'$

f (x^{'}) \leq c f (x)

$f(x') \le c f(x)$

Grigory Yaroslavtsev

@Grigory: arreglé el error que informaste con respecto a que debería ser .

x^{'}

$x'$

f (x^{'})

$f(x')$

Warren Schudy

Para agregar a las notas de Warren, hay esquemas de redondeo cada vez más sofisticados (e incluso dependientes), e incluso esquemas para empacar / cubrir problemas en los que el redondeo podría romper la viabilidad de una mala manera. Dependiendo de cuál sea su problema, hay referencias más avanzadas disponibles.

Suresh Venkat

Esta es una maquinaria algo pesada para lo que desea, pero ha habido un gran trabajo sobre técnicas para diseñar LP cada vez más refinados (SDP) que se acercan cada vez más al programa entero deseado. Una buena referencia que revisa estos enfoques es por Monique Laurent: Una comparación de las Relajaciones Sherali-Adams, Lovasz-Schrijver y Laserre para la programación 0-1 .

Aparte de eso, no conozco una sola buena fuente de referencias: supongo que al menos has leído los capítulos relevantes del libro de Vijay Vazirani .

Suresh Venkat
fuente

Gracias, su primera referencia es lo que tenía en mente y traté de evitar, porque me gustaría tener algo más simple si es posible.

Grigory Yaroslavtsev

En cuanto al libro de Vijay, describe brevemente la noción de brecha de integralidad, y luego pasa a la discusión de problemas específicos, sin dar técnicas generales. Sospecho que la noción de la brecha de integralidad y los resultados relevantes al respecto pueden ser muy diferentes de los resultados sobre los algoritmos de aproximación, debido a que el primero es un problema principalmente geométrico.

Grigory Yaroslavtsev