I am trying to solve the following MILP through LP solve. A link for the original problem is here
I am re-iterating the problem as follows: 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.
First, I 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.
MAXIMUM_HEIGHT of panel = 2100mm, minwidth range (350mm to 800mm), minheight range (225mm to 2100mm)
As per the answer chosen, I formulated the Integer Linear Program as follows:
The total number of binary variables = M*N
The total number of real variables = N
The total number of constraints = N + M*N + M
M ~ 10, N ~ 40. (H_i, W_i | i = 1 to N) and T are constants.
minimize sum { CW_k | k = 1, ..., N }
with respect to
C_i_k in { 0, 1 }, Feeder i placed in column k, i = 1, ..., M; k = 1, ..., N
CW_k >= 0, Width of column k //k = 1, ..., N
and subject to
//Total height of each column less than T
// I have already implemented height of present column <= height of prev col
// to avoid duplicate solutions.
[1] sum { H_i * C_i_k | i = 1, ..., M } <= T, k = 1, ..., N
//Width of each column = max( widths of individual feeders in that column)
[2] CW_k >= W_i * C_i_k, i = 1, ..., M; k = 1, ..., N
// Each feeder can be placed in only 1 column.
[3] sum { C_i_k | k = 1, ..., N } = 1, i = 1, ..., M
However, beyond a particular value of N (say 20) lp_solve just appears to hang. I am told that the above size is pretty much "handle-able" for solvers.
Is there any way I can re-formulate the above MILP so that it can be solved more efficiently. I have not tried out other solvers but I guess the performance shall not vary much.
Any help shall be appreciated.
Thanks!
