# Is this combinatorial optimisation problem similar to any known problem?

The problem is as follows:

We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a fixed integer $n$.

We now wish to overlay $n$ rectangles of dimensions $w \times h$ on the grid such that the total sum of the values of cells in these rectangles is maximized.

The following picture is an example of a two-dimensional grid with two such rectangles overlayed on it (the picture does not demonstrate the optimal solution, just one possible overlaying where $w = h = 2$ and $n = 2$) The rectangles cannot intersect (otherwise we would just need to find the optimal position for one rectangle and then put all the rectangles in that position.)

In the example above the total sum of values in cells would be $-2 + 4.2 + 2.4 + 3.14 + 2.3 -1.4 + 1 - 3.1$

Is this similar to any known problem in combinatorial optimisation? so that I can start doing some reading and try to find ways to solve it.

Some more background for those interested:

So far the only ideas I had are either a greedy algorithm (which would find the best location for the first rectangle, then find the non-overlapping loctaion for the second rectangle etc.) or some metaheuristic such as genetic algorithms.

In reality I wish to solve this problem with a grid which has around a million cells and tens of thousand (or even hundreds of thousands) of rectangles, though it is not necessary to solve it in a short time (i.e it would be acceptable for the algorithm to take hours or even days.) I am not expecting an exact solution but I want to get one which is as good as possible given these constraints.

Cheers!

• (on phone) this seems like it could be solved with maximum matching under a transformation and some additional constraints. I'll try to write up later. – Nicholas Mancuso Jan 30 '15 at 3:12
• I can imagine requiring the exact $n$ to be used means sometimes a "local" maximum is not used but a ring around it is. I'm imagining a simple dome shape here, where the "greedy" taking of the centre of the dome means you can't fit all $n-1$ around it. – Mark Hurd Jan 30 '15 at 3:52
• My first thought would be to try dynamic programming. Number the squares according to their Manhattan distance from the upper left. A subproblem is: a number $s$ of a square; a list $L$ of rectangles you've selected whose upper-left corder has number less than $s$; and the goal is to extend $L$ to the best possible set of non-overlapping squares by adding some subset of squares with upper-left corners having numbers $\ge s$. You can solve each subproblem quickly if you have the solution to all later subproblems. The only question is how many subproblems you'll have to explore. – D.W. Jan 30 '15 at 19:16

Another natural graphical formulation of the problem would be to create a graph where each vertex $r$ represents a rectangle with $w_r$. Any pair of overlapping rectangles $r, r'$ have an edge in this graph. By solving for maximum-weighted independent set of size $k=n$ we have a solution to your original problem. There exist many good heuristics and approximation algorithms for this.
Here's the ILP formulation. We have a zero-or-one variable $x_r$ for each possible rectangle $r$, with the intended interpretation that $x_r=1$ means you include rectangle $r$ in your set and $x_r=0$ means you don't include it. You want to maximize the objective function $\sum_r c_r x_r$ (where $c_r$ is the profit of rectangle $r$), subject to the restriction that $\sum_r x_r = n$ and that no two rectangles overlap. The latter restriction can be expressed as a linear inequality by requiring $x_r + x_s \le 1$ for all pairs of rectangles $r,s$ that overlap. So, in this way you get a ILP.