Esse problema de otimização combinatória é semelhante a qualquer problema conhecido?

O problema é o seguinte:

Temos uma matriz / grade bidimensional de números, cada um representando algum "benefício" ou "lucro". Temos também dois inteiros fixos e (para "width" e "height".) E um inteiro fixo .h $w$$h$$n$

Agora, desejamos sobrepor retângulos de dimensões na grade, de modo que a soma total dos valores das células nesses retângulos seja maximizada.w × $n$$w \times h$

O quadro que se segue é um exemplo de uma rede bidimensional com duas de tais rectângulos sobrepostos sobre ele (a imagem não demonstra a solução ideal, apenas uma possível sobreposição onde e )n = $w = h = 2$$n = 2$

Os retângulos não podem se cruzar (caso contrário, precisaríamos apenas encontrar a posição ideal para um retângulo e depois colocar todos os retângulos nessa posição.)

No exemplo acima, a soma total dos valores nas células seria$-2 + 4.2 + 2.4 + 3.14 + 2.3 -1.4 + 1 - 3.1$

É semelhante a qualquer problema conhecido na otimização combinatória? para que eu possa começar a ler e tentar encontrar maneiras de resolvê-lo.

Mais alguns antecedentes para os interessados:

Até agora, as únicas idéias que tive foram um algoritmo ganancioso (que encontraria a melhor localização para o primeiro retângulo, depois encontraria o local não sobreposto para o segundo retângulo etc.) ou algumas metaheurísticas, como algoritmos genéticos.

Na realidade, desejo resolver esse problema com uma grade com cerca de um milhão de células e dezenas de mil (ou mesmo centenas de milhares) de retângulos, embora não seja necessário resolvê-lo em um curto espaço de tempo (isto é, seria aceitável para o algoritmo pode levar horas ou até dias.) Não estou esperando uma solução exata, mas quero obter uma que seja a melhor possível, dadas essas restrições.

Felicidades!

Minha última formulação teve uma falha fatal que exigiria uma quantidade exponencial de nós de "restrição".

Outra formulação gráfica natural do problema seria criar um gráfico em que cada vértice represente um retângulo com . Qualquer par de retângulos sobrepostos tem uma aresta neste gráfico. Ao resolver o conjunto independente de tamanho máximo ponderado , temos uma solução para o seu problema original. Existem muitas boas heurísticas e algoritmos de aproximação para isso.w r r , r ′ k = $r$$w_r$$r, r'$$k=n$

Você pode formular isso como uma instância de programação linear inteira gigantesca (ILP) e aplicar um solucionador de ILP pronto para uso (lp_solve, CPLEX etc.). Eles lhe darão a melhor solução que encontrarem. Dado o tamanho da sua instância do problema, não sei se isso será eficiente o suficiente, mas seria fácil tentar.

Aqui está a formulação do ILP. Temos uma variável zero ou um para cada retângulo possível , com a interpretação pretendida de que significa que você inclui o retângulo no seu conjunto e significa que você não o inclui. Você deseja maximizar a função objetivo (em que é o lucro do retângulo ), sujeito à restrição que e que não há dois retângulos sobrepostos. A última restrição pode ser expressa como uma desigualdade linear, exigindo para todos os pares de retângulos r x r = 1 r x r = 0 ∑ r c r x r c r r ∑ r x r = n x r + x s ≤ 1 r , $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$essa sobreposição. Então, dessa maneira, você obtém um ILP.