algorithm - online - Cobertura mínima exacta de cuadrícula con cuadrados; cortes extra

linear and integer programming online (5)

Restricciones en el valor de la función objetivo.

Siempre que el valor de la función objetivo no sea integral, por ejemplo, debido a que tiene un número impar de cuadrados de 0.5 en la solución fraccional, puede agregar un corte "directamente en la función objetivo" para forzarlo a la siguiente integral más alta valor: por ejemplo, en su ejemplo, la solución fraccionaria con 13 cuadrados cada uno con un peso de 0.5 para un valor total de la función objetivo de 6.5, puede agregar la restricción de que la suma de todos x_i> = 7.

Cortes mas generales

Esto lleva a una regla más general que funcionará siempre que tenga una solución fraccionaria en la que algún subconjunto C de celdas esté "cubierto exactamente" por algún subconjunto S de cuadrados que tengan un peso total no integral w. Por "exactamente cubierto", quiero decir que los cuadrados en S tienen cada uno un peso distinto de cero y juntos proporcionan un peso total de 1 para cada celda en C, y no se superponen con ninguna celda fuera de C. Puede encontrar estos subconjuntos de celdas fácilmente al creando un gráfico con un vértice para cada celda y un borde entre dos vértices siempre que estén (parcialmente) cubiertos por el mismo cuadrado en la solución fraccionaria: cada componente conectado de este gráfico es un subconjunto (mínimo) de este tipo.

Dada una solución fraccionaria con un subconjunto de células C exactamente cubierto y un subconjunto de cuadrados S como antes, sea T el conjunto de todos los cuadrados que se superponen solo con las células en C (obviamente, T es un superconjunto de S). Sabemos que cualquier solución óptima X para el subproblema LP que consiste solo en el subconjunto C de celdas (y el subconjunto relevante T de cuadrados candidatos) debe tener un peso total idéntico a S, ya que si no fuera así, esto contradeciría la optimalidad de Solución fraccional al LP original: puede reemplazar S por X y obtener una mejor solución.

Ahora, hay dos conjuntos de soluciones al problema original (cualquiera de los cuales puede estar vacío): aquellas soluciones en las que ningún cuadrado cubre una celda en C y una celda fuera de C, y aquellas soluciones en las que al menos alguna casilla sí lo hace. Queremos prohibir soluciones en la primera categoría que tengan un peso total <RoundUp (w). Sea U el conjunto de todos los cuadrados que se superponen al menos a una celda en C y al menos a una celda fuera de C. Podemos lograr esto agregando la restricción

Sum_{square_i in T}(x_i) + RoundUp(w) * Sum_{square_j in U}(x_j) >= RoundUp(w)

El efecto de multiplicar el segundo término en el LHS por RoundUp (w) es que si incluso un solo cuadrado que cubre una celda en C y alguna otra celda se incluye en la solución, la restricción "desaparece" de manera efectiva. Esto es necesario porque S y C no nos dicen nada sobre tales soluciones al problema original y, por lo tanto, no podemos permitirnos descartarlas. Tenga en cuenta que la solución original que contiene el subconjunto de cuadrados S estará prohibida por esta restricción, ya que cada cuadrado en U debe tener un peso 0 en esta solución.

Sin panacea

El segundo enfoque es más poderoso que el primero, ya que puede suceder que, por ejemplo, el gráfico contenga dos componentes, cada uno de los cuales tiene un número impar de cuadrados, todos los cuales tienen un peso de 0.5: esto significaría que hay un total uniforme número de cuadrados, lo que significa que el valor global de la función objetivo es integral, lo que evita la posibilidad de agregar un corte en la función objetivo. Pero incluso la aplicación de estos cortes una y otra vez no garantiza que se encuentre una solución viable: como ejemplo concreto, cada vez que la cuadrícula es horizontal y / o verticalmente simétrica pero puede ser cubierta por un conjunto asimétrico de cuadrados, entonces se puede cubrir con la misma facilidad con la versión invertida horizontal y / o verticalmente de ese conjunto de cuadrados, y, lo que es más molesto, con cualquier "combinación afín" de estos dos conjuntos de cuadrados (es decir, con cualquier combinación de pesos que sume 1 ). En general, podría haber muchas soluciones factibles igualmente buenas, y los cortes que he descrito aquí no dan forma de evitar que el solucionador de LP devuelva una solución que contenga una "superposición" de todos los k, con todos los cuadrados asignados de peso 1 / k.

[EDITAR 1/7/2015]

Un lado brillante!

Aunque, como mencioné anteriormente, no hay forma de que el solucionador de LP "aísle" una cubierta factible particular de una "superposición" fraccionaria de varias cubiertas óptimas simétricas, hay una buena noticia: en caso de que obtenga una superposición de este tipo En realidad, es muy fácil recuperar una sola cobertura óptima y factible. Todo lo que necesita hacer es elegir con avidez los cuadrados con un peso distinto de cero, cada vez que elimine los cuadrados que se superponen con el cuadrado que acaba de seleccionar. Se garantiza que esto funcionará si la solución es una superposición como he descrito, y, lo que es más importante: si este procedimiento funciona en una solución fraccionada (es decir, si repetir este paso codicioso cubre todas las celdas), entonces la solución ¡Debe ser óptimo! (Suponga que no fue así: sea X la solución fraccional óptima devuelta por el solucionador de LP, sea F la solución factible que acaba de extraer de ella con avidez y sea el peso más pequeño de cualquier casilla en F. Observe que cada casilla en F contribuye al menos y al valor de cobertura de cada celda, por lo que, dado que F es subóptimo por supuesto, restar y del peso de cada cuadrado en F y escalar todos los demás pesos en X por 1 / (1-y) dar otra solución (posiblemente de nuevo fraccional) de menor peso, lo que contradice la optimalidad de X.)

Sería muy útil demostrar que cualquier solución fraccionaria (i) tiene algún componente en el "gráfico de cobertura" con peso total no integral, o (ii) consiste en tal superposición: esto significaría que podría continuar aplicando mi "general" corta hasta que obtengas una superposición, que luego podrías resolver con avidez. Pero tal como está, podría haber soluciones fraccionarias fuera de estas dos categorías.

Este problema apareció en un challenge , pero como ahora está cerrado, debería estar bien preguntar al respecto.

El problema (no esta pregunta en sí, es solo información de antecedentes) puede describirse visualmente de esta manera, tomando prestada su propia imagen:

Elegí resolverlo de manera óptima. Eso es probablemente (para la variante de decisión) un problema NP-completo (ciertamente está en NP, y huele como una cobertura exacta, aunque no he probado que se pueda reducir un problema general de cobertura exacta), pero está bien, solo tiene que ser rápido en la práctica, no necesariamente en el peor de los casos. En el contexto de esta pregunta, no estoy interesado en ningún algoritmo de aproximación, a menos que provean cortes.

Hay un modelo ILP obvio: generar todos los cuadrados posibles (un cuadrado es posible si cubre solo las celdas de la cuadrícula que están presentes), introduzca una variable binaria x_i para cada cuadrado que indique si lo usamos o no, entonces

minimize sum x_i subject to: 1) x_i is an integer 2) 0 ≤ x_i ≤ 1 3) for every cell c (sum[j | c ϵ square_j] x_j) = 1

La restricción 3 dice que cada celda está cubierta exactamente una vez. Las restricciones 1 y 2 hacen que x_i sea binario. La solución mínima da una solución óptima al problema original.

La relajación lineal de esto (es decir, ignorar la restricción 1) es medio decente, pero hace cosas como esta (esto es una cuadrícula de 6x6 en la que falta la esquina superior izquierda):

Aquí se eligieron 13 cuadrados "mitad" (dando un valor objetivo de 6.5), de los tamaños (para que puedas encontrarlos más fácilmente)

1 de 4x4
3 de 3x3
6 de 2x2
3 de 1x1

Una solución óptima para esta instancia tiene un valor objetivo de 8, como este:

La relajación lineal es medio decente, pero no estoy completamente feliz con ella. La brecha a veces supera el 10%, y en ocasiones lleva a una fase de enteros muy lenta.

Ahí es donde entra la pregunta real, ¿hay restricciones adicionales que puedo agregar (perezosamente) como cortes, para mejorar una solución fraccionada?

He intentado formulaciones alternativas del problema para encontrar cortes, por ejemplo, en lugar de elegir cuadrados, ¿qué tal si seleccionamos "esquinas superiores izquierdas" y "esquinas inferiores derechas", que luego deben combinarse para formar cuadrados no superpuestos que cubrir todas las celulas? Luego, en cada "diagonal de barra diagonal inversa", debe haber un número coincidente de esquinas superior izquierda y derecha inferior. Pero eso no ayuda, porque si elegimos cuadrados, entonces esa condición siempre es cierta, también en soluciones fraccionarias.

También he intentado algún razonamiento sobre las superposiciones, por ejemplo, si dos cuadrados se superponen claramente, su suma no debe ser mayor que 1, y eso se puede mejorar agregando también todos los cuadrados que están totalmente contenidos en la región de superposición. Pero esa restricción es menos poderosa que la restricción de que todas las celdas se cubran exactamente una vez.

He intentado razonar sobre el área total (como en, el área cubierta total debe ser igual al número de celdas), pero eso ya está garantizado por la restricción de que cada celda debe cubrirse una vez, indicándola en términos del área total Solo permite mas libertad.

También traté de hacer algo con números cuadrados (el área de cada cuadrado es, bueno, un cuadrado) y diferencias de números cuadrados, pero eso tampoco terminó en nada útil.

¿Qué tal si usamos una restricción de que el área total de los cuadrados es igual al área total que se cubrirá, además de la restricción de no superposiciones? Esto debería ser más difícil que verificar la restricción de doble cobertura.

Programación dinámica: elija una celda (cualquier celda servirá), calcule todos los cuadrados válidos que la cubren (es decir, que solo cubran la celda actual y otras celdas de la cuadrícula). Para cada cuadrado de este tipo, obtenga recursivamente el valor de cobertura mínimo para el área restante (cuadrícula menos el cuadrado), y luego elija el valor mínimo de esos (el resultado es ese valor + 1). Para hacer que las cosas sean más rápidas, intente elegir una celda que tenga el menor cuadrado de cobertura válido en cada nivel de la recursión (reduciendo así el número de llamadas recursivas en cada nivel).

Realmente simple.

Usaría una búsqueda como A* para encontrar una solución. Es importante tener en cuenta que A * es como Greedy Best-First-Search en que puede usar una heurística para guiarse. Suponiendo que tenga una heurística correcta, encontrará una solución casi óptima (~ 0.95) en un tiempo razonable.

La solución de ejemplo usa 18 bloques en lugar de 19 como se muestra en el ejemplo. Además de la heurística , puede utilizar cierta precomputación para aumentar la efectividad del algoritmo. Por ejemplo, calculé lo que llamo gradiente de libertad para cada ubicación. Por ejemplo, su mapa inicial se convierte en una etapa:

Puede tener su propia heurística que puede ser igualmente buena o incluso mejor. Usé esto solo porque encontré que era trivial. Los números de etapa tienen el siguiente significado: más alto es el número, más probable es que esté en una caja grande (hay más restricciones que puedes concluir, pero es un comienzo).

El valor de etapa es la suma total de 4 reglas de automatización de bodega.

Por ejemplo arriba a la izquierda

cell(x,y) := min(cell(x,y-1) ?? 0, cell(x-1,y) ?? 0, cell(x-1,y-1) ?? 0) + 1

Los ?? operador se llama el operador de unión nula. Devuelve el operando de la izquierda si el operando no es nulo; De lo contrario, devuelve el operando de la mano derecha.

Además, puede reducir el trabajo de computación requerido al eliminar las soluciones conocidas que obtuvo de la precomputación y en cada etapa. En este caso el estado 0:

El algoritmo mismo se repetiría:

Ordena celdas y toma las más altas.
Ordena los resultados de la regla de automatización y toma la mayor
Encuentra cortes triviales

Si desea obtener resultados aún más rápidos para grillas más grandes, una forma bastante avanzada sería extender la precomputación para compilar plantillas. Después de eso puedes hacer reducción de plantilla.

Por ejemplo, podría tener una plantilla (parte superior izquierda)

--+++ +-+++ +++++

Puede generar su hash y agregarlo a hashmap / dictionary con valor 4 (lo que significa que tomará un mínimo de 4 rectángulos para cubrir los + ''s). Entonces tiene un rango de 5x3 con el mismo hash que sabe que es un corte trivial con costo 4.

La razón por la que esto es más rápido es que las comparaciones toman mucho tiempo en comparación con calcular un hash que está cerca de la velocidad constante.

Alternativamente, hay una manera de hipnotizar si o qué tipo de solución estamos buscando. Usando la función de Wolfram Mathematica FindMinimum se vería algo en las líneas de:

FindMinimum[{ a + b + c + d + e + f + g, (a 1^2 + b 2^2 + c 3^2 + d 4^2 + e 5^2 + f 6^2 + g 7^2) == 119 && a >= 0 && b >= 0 && c >= 0 && d >= 0 && e >= 0 && f >= 0 && g >= 0 && a /[Element] Integers && b /[Element] Integers && c /[Element] Integers && d /[Element] Integers && e /[Element] Integers && f /[Element] Integers && g /[Element] Integers }, {a,b,c,d,e,f,g}]

Esto se basa en el supuesto de que tenemos una cuadrícula de 12x12 con 119 celdas y nos brindaría una solución óptima con los conteos de tamaño de cuadrícula utilizados.

Lamentablemente, el motor de búsqueda alfa de Wolfram no interpreta esto, quizás en el futuro.

Utilicé el método de rama y precio para un buen efecto en un problema similar ( Strawberry Fields de ITA; desplácese hacia abajo). Aquí está mi código , que (sin comentarios) probablemente sea bueno solo como una prueba de conocimiento cero de que sé de lo que estoy hablando. Fueron órdenes de magnitud más rápidas que un solucionador comercial (que no mencionaré).

La clave fue la estrategia de ramificación. En lugar de bifurcarse directamente en las variables x_i , que es probablemente lo que está haciendo su solucionador, se bifurca en una decisión de nivel superior. El que usé para Strawberry Fields fue decidir si dos celdas serían cubiertas por el mismo cuadrado. Si apunta a los pares sobre los que la solución fraccionada está más cerca, la estructura de la solución parece establecerse con bastante rapidez.

Desafortunadamente, no puedo ofrecerle consejos sobre cómo programar esto en un solucionador de programas de enteros existente. Para Strawberry Fields, fui con todo personalizado, principalmente porque quería, pero en parte porque estaba generando columnas sobre la marcha, utilizando filas de cuadrícula acumuladas y sumas de columnas de cuadrícula para evaluar rectángulos rápidamente.