Redondeo aleatorio de soluciones a programas lineales

Question

Programación lineal entera (ILP) es una herramienta increíblemente poderosa en la optimización combinatoria. Si podemos formular algún problema como una instancia de un ILP, los solucionadores están garantizados para encontrar el óptimo global. Sin embargo, hacer cumplir las soluciones integrales tiene un tiempo de ejecución que es exponencial en el peor de los casos. Para hacer frente a esta barrera, se pueden usar varios métodos de aproximación relacionados con los ILP,

• Esquema primario-dual
• Redondeo aleatorio

El esquema primal-dual es un método versátil que nos da una forma "empaquetada" de crear un algoritmo codicioso y probar sus límites de aproximación utilizando el LP dual relajado. Los algoritmos combinatorios resultantes tienden a ser muy rápidos y funcionan bastante bien en la práctica. Sin embargo, su relación con la programación lineal está más ligada al análisis. Además, debido a este análisis, podemos demostrar fácilmente que no se violan restricciones.

El redondeo aleatorio adopta un enfoque diferente y resuelve el LP relajado (usando métodos de punto interior o elipsoide) y redondea las variables de acuerdo con alguna distribución de probabilidad. Si se pueden probar los límites de aproximación, este método, como el esquema primal-dual, es bastante útil. Sin embargo, una porción no me queda del todo:

¿Cómo muestran los esquemas de redondeo aleatorizado que no se violan las restricciones?

¡Parece que voltear ingenuamente una moneda, al tiempo que resulta en una solución 0-1, podría violar las limitaciones! Se agradecería cualquier ayuda para iluminar este problema. Gracias.

Answer 1

Por supuesto, si redondea, debe verificar que el redondeo conserva la viabilidad.

Consideremos por ejemplo el relajado Formulación LP de cubierta de vértice. $$ begin {array} {lll} text {min} & sum_ {v in v} c (v) x_v & text {st} & x_u+x_v ge1, & quad (u, v, v, v, v, v, v, ) in e & x_v ge 0. & quad v in v end {array} $$

Se sabe que la solución a este problema es medio integral, es decir, cada variable es de $ 0 $, $ 1 $ o $ 1/2 $. El esquema de redondeo funciona de la siguiente manera, cada vez que su solución contiene $ x_v = 1/2 $ usted redondeo y establecer $ x_v = 1 $. Las restricciones del ILP fueron $$ begin {array} {lll} & x_u+x_v ge1, & quad (u, v) in e & x_v in {0,1 }. & quad v in v end {array} $$ ambas restricciones se cumplen después del redondeo. Y tienes una bonita agrupación de 2.

Answer 2

Sí, esto es confuso a primera vista.

Yo lo veo así:

Paso1) Generar una solución de programa lineal [todas las restricciones de programa lineal se cumplen aquí, excepto que no es una solución entera],

paso2) aleatorizarlo (cambie el valor a enteros de acuerdo con una distribución de probabilidad que seleccione),

Paso 3) Asegúrese de que la solución aleatoria sea correcta (haciendo pocos cambios).

Por ejemplo, en la cobertura de conjunto. Después de la aleatorización, puede terminar con una colección de conjuntos que no son necesariamente una cubierta establecida. En este caso, debe agregar algunos conjuntos que cubren todos los elementos descubiertos (y por lo tanto, obtenga la solución que desea).

Para evitar cambios tan grandes en la solución de programa lineal aleatorizado, siga un esquema de redondeo aleatorio que garantiza con alta probabilidad de que se encuentre una solución después del redondeo (es decir, no necesitará hacer muchos cambios en la solución del programa lineal para obtener lo que usted desear).

Vea esto para una referencia: 1