¿Es este problema de optimización combinatoria similar a cualquier problema conocido?

El problema es el siguiente:

Tenemos una matriz / cuadrícula bidimensional de números, cada uno representa algún "beneficio" o "beneficio". También tenemos dos enteros fijos y (para "ancho" y "altura"). Y un entero fijo .$w$$h$$n$

Ahora deseamos superponer rectángulos de dimensiones en la cuadrícula de modo que se maximice la suma total de los valores de las celdas en estos rectángulos.$n$$w \times h$

La siguiente imagen es un ejemplo de una rejilla bidimensional con dos de tales rectángulos superpuestos en él (la imagen no demuestra la solución óptima, sólo una posible superposición donde y )$w = h = 2$$n = 2$

Los rectángulos no pueden cruzarse (de lo contrario, solo tendríamos que encontrar la posición óptima para un rectángulo y luego colocar todos los rectángulos en esa posición).

En el ejemplo anterior, la suma total de valores en las celdas sería$-2 + 4.2 + 2.4 + 3.14 + 2.3 -1.4 + 1 - 3.1$

¿Es esto similar a algún problema conocido en la optimización combinatoria? para que pueda comenzar a leer un poco e intentar encontrar formas de resolverlo.

Algunos antecedentes más para los interesados:

Hasta ahora, las únicas ideas que tenía son un algoritmo codicioso (que encontraría la mejor ubicación para el primer rectángulo, luego encontraría la loctaión no superpuesta para el segundo rectángulo, etc.) o algunos metaheurísticos como los algoritmos genéticos.

En realidad, deseo resolver este problema con una cuadrícula que tiene alrededor de un millón de celdas y decenas de miles (o incluso cientos de miles) de rectángulos, aunque no es necesario resolverlo en poco tiempo (es decir, sería aceptable para el algoritmo puede llevar horas o incluso días.) No espero una solución exacta, pero quiero obtener una que sea lo mejor posible, dadas estas limitaciones.

¡Salud!

Mi última formulación tenía un defecto fatal que requeriría una cantidad exponencial de nodos de "restricción".

Otra formulación gráfica natural del problema sería crear un gráfico donde cada vértice represente un rectángulo con . Cualquier par de rectángulos superpuestos tiene un borde en este gráfico. Al resolver un conjunto independiente de ponderación máxima de tamaño , tenemos una solución a su problema original. Existen muchos buenos algoritmos de heurística y aproximación para esto.$r$$w_r$$r, r'$$k=n$

Puede formular esto como una instancia de programación lineal de enteros gigantes (ILP) y luego aplicar un solucionador ILP estándar (lp_solve, CPLEX, etc.). Le darán la mejor solución que puedan encontrar. Dado el tamaño de la instancia de su problema, no sé si será lo suficientemente eficiente, pero sería fácil intentarlo.

Aquí está la formulación de ILP. Tenemos una variable cero o uno para cada posible rectángulo , con la interpretación prevista de que significa que incluye el rectángulo en su conjunto y significa que no lo incluye. Desea maximizar la función objetivo (donde es el beneficio del rectángulo ), sujeto a la restricción de que que no se superponen dos rectángulos. La última restricción se puede expresar como una desigualdad lineal al requerir para todos los pares de rectángulos$x_r$$r$$x_r=1$$r$$x_r=0$$\sum_r c_r x_r$$c_r$$r$$\sum_r x_r = n$$x_r + x_s \le 1$$r,s$Esa superposición. Entonces, de esta manera obtienes un ILP.