[Solved]: Is this combinatorial optimisation problem similar to any known problem?

Problem Detail: 

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!

Asked By : fiftyeight

Answered By : Nicholas Mancuso

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37731

3.2K people like this

 Download Related Notes/Documents