Strange but practical 2D bin packing optimization

Question

I am trying to write an application that generates drawing for compartmentalized Panel.

I have N cubicles (2D rectangles) (N <= 40). For each cubicle there is a minimum height (minHeight[i]) and minimum width (minWidth[i]) associated. The panel itself also has a MAXIMUM_HEIGHT constraint.

These N cubicles have to be arranged in a column-wise grid such that the above constraints are met for each cubicle.

Also, the width of each column is decided by the maximum of minWidths of each cubicle in that column.

Also, the height of each column should be the same. This decides the height of the panel

We can add spare cubicles in the empty space left in any column or we can increase the height/width of any cubicle beyond the specified minimum. However we cannot rotate any of the cubicles.

OBJECTIVE: TO MINIMIZE TOTAL PANEL WIDTH.

At present I have implemented it simply by ignoring the widths of cubicles in my optimization. I just choose the cubicle with largest minHeight and try to fit it in my panel. However, it does not gurantee an optimal solution.

Can I get any better than this?

EDIT 1: MAXIMUM_HEIGHT of panel = 2100mm, minwidth range (350mm to 800mm), minheight range (225mm to 2100mm)

EDIT 2: PROBLEM OBJECTIVE: TO MINIMIZE PANEL WIDTH (not panel area).

Answer 1

Formulation

Given:

• for each cell i = 1, ..., M, the (min) width W_i and (min) height H_i
• the maximum allowed height of any stack, T

We can formulate the mixed integer program as follows:

minimize sum { CW_k | k = 1, ..., N }
with respect to

    C_i in { 1, ..., N },                        i = 1, ..., M

    CW_k >= 0,                                   k = 1, ..., N

and subject to

[1] sum { H_i | C_i = k } <= T,                  k = 1, ..., N

[2] CW_k = max { W_i | C_i = k },                k = 1, ..., N
           (or 0 when set is empty)

You can pick N to be any sufficiently large integer (for example, N = M).

Algorithm

Plug this mixed integer program into an existing mixed integer program solver to determine the cell-to-column mapping given by the optimal C_i, i = 1, ..., M values.

This is the part you do not want to reinvent yourself. Use an existing solver!

Note

Depending on the expressive power of your mixed integer program solver package, you may or may not be able to directly apply the formulation I described above. If the constraints [1] and [2] cannot be specified because of the "set based" nature of them or the max, you can manually transform the formulation to an equivalent less-declarative but more-canonical one that does not need this expressive power:

minimize sum { CW_k | k = 1, ..., N }
with respect to

    C_i_k in { 0, 1 },                           i = 1, ..., M; k = 1, ..., N

    CW_k >= 0,                                   k = 1, ..., N

and subject to

[1] sum { H_i * C_i_k | i = 1, ..., M } <= T,    k = 1, ..., N

[2] CW_k >= W_i * C_i_k,                         i = 1, ..., M; k = 1, ..., N

[3] sum { C_i_k | k = 1, ..., N } = 1,           i = 1, ..., M

Here the C_i variables from before (taking values in { 1, ..., N }) have been replaced with C_i_k variables (taking values in { 0, 1 }) under the relationship C_i = sum { C_i_k | k = 1, ..., N }.

The final cell-to-column mapping is described by the the C_i_k: cell i belongs in column k if and only if C_i_k = 1.

Answer 2

One solution is to divide the width of the cubicle row by the minimum width. This gives you the maximum number of cubicles that can fit in a row.

Divide the remainder of the first division by the number of cubicles. This gives you the extra width to add to the minimum width to make all of the cubicle widths even.

Example: You have a cubicle row of 63 meters. Each cubicle has a minimum width of 2 meters. I'm assuming that the thickness of one of the cubicle walls is included in the 2 meters. I'm also assuming that one end cubicle will be against a wall.

Doing the math, we get 63 / 2 = 31.5 or 31 cubicles.

Now we divide 0.5 meters by 31 cubicles and get 16 millimeters. So, the cubicle widths are 2.016 meters.

Answer 3

You can look into vm packing especially share aware algorithm for virtual machine collocation: http://dl.acm.org/citation.cfm?id=1989554. You can read also about @ http://en.m.wikipedia.org/wiki/Bin_packing_problem. The problem is already difficult but the cubicle can share width or height. Thus the search space gets bigger.