10
$\begingroup$

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$)

Grid example

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!

|cite|improve this question
$\endgroup$
  • $\begingroup$ (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. $\endgroup$ – Nicholas Mancuso Jan 30 '15 at 3:12
  • $\begingroup$ 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. $\endgroup$ – Mark Hurd Jan 30 '15 at 3:52
  • $\begingroup$ 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. $\endgroup$ – D.W.♦ Jan 30 '15 at 19:16
2
$\begingroup$

My last formulation had a fatal flaw that would require an exponential amount of "constraint" nodes.

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This is the direction I am currently leaning towards, I will experiment with this and accept the solution if it is the one I end up using, cheers. $\endgroup$ – fiftyeight Feb 4 '15 at 2:49
2
$\begingroup$

You could formulate this as a gigantic integer linear programming (ILP) instance, and then apply an off-the-shelf ILP solver (lp_solve, CPLEX, etc.). They will give you the best solution they can find. Given the size of your problem instance, I don't know whether this will be efficient enough, but it would be easy to try.

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Do you think this problem is NP-hard? I'm not convinced it doesn't have a poly time solution, and the ILP solvers are unlikely to finish even moderately sized instances. $\endgroup$ – R B Feb 1 '15 at 9:51
  • 1
    $\begingroup$ @RB, I have no idea whether it is NP-hard. See my comment under the question about dynamic programming for my first thought about how to try to find a polynomial-time algorithm (but I don't know if the resulting algorithm will be in P or not). As far as what ILP solvers can do, the only way to find out is to try -- sometimes their performance can be surprising. $\endgroup$ – D.W.♦ Feb 1 '15 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.