Algorithm to fit rectangles with different areas inside a matrix with lowest complexity

Hi everybody,

I have the following problem:

I have a matrix with M rows and N columns. Then I have a set of objects
that I have to fit in, and the area they have depends on where I will
place them in the matrix. Let's give an example:

Object 1:
-You can place it between rows 2 and 4 of the matrix, and if you do so
the are of the object is 10.
-You can place it between rows 3 and 7 of the matrix,and if you do so
the area of the object is 20
....

We have up to Li rules like this for every one of the objects. And the
rules are really like described in the example, they define a set of
rows and the area that the object will have if it is placed within
these rows. The way the actual filling is done, i. e. the shape that
the object will have between the rows in the matrix is in principle
irrelevant, but it is preferable if it is rectangular, this means that
given a set of rows and an area I either start filling by columns or by
rows.

You can also imagine that the rules are ordered in terms of area of the
object, if we allocate the object according to the first rule then the
area it takes is the smallest one, if we allocate the object according
to the last rule then the area is the biggest one.

So now I am given x objects each one with it x_l number of rules
ordered by area, and I have this matrix MxN. The problem is to find the
allocation of the objects that minimizes the occupied area in the
matrix.

Intuitively I would start trying to place all the objects according to
their rule number one, the one where they have the smallest area, if
all the objects fit without overlapping I am finished and this is the
optimum allocation, but if I can not allocate two objects in their best
rule because the matrix is not big enough then I have to decide to
place one of them there and go
for the second rule of the other object, that in turn can collide with
another object's allocation.

The trivial solution is the exhaustive search but this is too time
consuming.

Can you point me to some algorithms, that try to solve problems similar
to this in an optimum way ?

Thanks

Dani

.

Relevant Pages

  • Algorithm to fit rectangles with different areas inside a matrix with lowest complexity
    ... that I have to fit in, and the area they have depends on where I will ... The way the actual filling is done, ... if we allocate the object according to the first rule then the ... optimum allocation, but if I can not allocate two objects in their best ...
    (sci.math.research)
  • Algorithm to fit rectangles with different areas inside a matrix with lowest complexity
    ... that I have to fit in, and the area they have depends on where I will ... The way the actual filling is done, ... if we allocate the object according to the first rule then the ... optimum allocation, but if I can not allocate two objects in their best ...
    (comp.constraints)
  • Algorithm to fit rectangles with different areas inside a matrix
    ... that I have to fit in, and the area they have depends on where I will ... The way the actual filling is done, ... if we allocate the object according to the first rule then the ... this works I am finished and this is the optimum allocation, ...
    (sci.math)
  • Algorithm to fit rectangles with different areas inside a matrix
    ... that I have to fit in, and the area they have depends on where I will ... The way the actual filling is done, ... if we allocate the object according to the first rule then the ... this works I am finished and this is the optimum allocation, ...
    (comp.ai.genetic)
  • Re: Algorithm to fit rectangles with different areas inside a matrix with lowest complexity
    ... that I have to fit in, and the area they have depends on where I will ... if we allocate the object according to the first rule then the ... stock problem seeks to lay out n patterns on one or more pieces of stock in a non-overlapping manner so as to minimize the amount of stock consumed. ... It differs from your problem in two respects: the patterns have fixed dimensions; and the cost of the stock material includes the scrap portions, not just the part occupied by the patterns. ...
    (comp.constraints)