Formulation
Given:
- for each cell
i = 1, ..., M
, the (min) widthW_i
and (min) heightH_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
.