12

Sample Sub-optimal output

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).

Timothy Shields
  • 75,459
  • 18
  • 120
  • 173
Abhishek Bansal
  • 12,589
  • 4
  • 31
  • 46
  • I'm trying to wrap my mind around the height part of the problem. Do you stack cubicles? Do you have to provide stairs or a ladder to the cubicles on top? – Gilbert Le Blanc Aug 30 '13 at 17:13
  • Yes the cubicles are stacked one on top the other, making a 'column'. There can be one or more such columns placed side-by-side. Each column should have the same height (viz. <= MAXIMUM_HEIGHT). The MAXIMUM_HEIGHT is 2100mm so no stairs or ladders needed. I'm sorry I didn't understand this part of your query. – Abhishek Bansal Aug 30 '13 at 17:20
  • It is a 2d problem, no 3d element is involved. – Abhishek Bansal Aug 30 '13 at 17:23
  • @GilbertLeBlanc OP is only mentions 2 dimensions (height/width). Maybe think of this as a "wall plan" as opposed to a "floor plan"? – NealB Aug 30 '13 at 17:23
  • @NealB yes you are correct in visualizing. – Abhishek Bansal Aug 30 '13 at 17:24
  • Did you do the math to calculate the maximum number of cubicle per row/col with maximum number of permutation. Just to have rough idea if it's computer feasible to try every combination ? Because even If you do a good algorithm which by optimisation test only 1% of the combination it's maybe too huge to test everything. – ColdCat Sep 03 '13 at 07:31
  • When you get a preferred solution can you post a pic of the "after" configuration? – Peter M Sep 03 '13 at 17:22
  • Well no-one has asked me to solve any such problem if that's what you mean. I am working on a project out of my own interest and I was stuck with this. – Abhishek Bansal Sep 03 '13 at 17:35
  • Isn't this just the knapsack problem in 2d? And therefore NP hard? –  Sep 03 '13 at 17:37

3 Answers3

7

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.

Timothy Shields
  • 75,459
  • 18
  • 120
  • 173
  • shouldn't the last line be `max` instead of `min`? – Vincent van der Weele Sep 03 '13 at 17:08
  • @Heuster Yes, typo. :) – Timothy Shields Sep 03 '13 at 17:09
  • Thank You for your answer! Actually I can understand only little bit from the notation. Is N the number of columns? How does it ensure that each Cell occurs in only 1 column? Sorry can you please elaborate your problem formulation? Thanks Again! – Abhishek Bansal Sep 03 '13 at 17:22
  • Oh yes I see, for each cell, I can sum over the columns and make the sum equal to 1. Am I correct? – Abhishek Bansal Sep 03 '13 at 17:24
  • @AbhishekBansal `N` is the *maximum* number of columns - maybe less than `N` are actually used. In the canonical formulation at the end of my answer, constraint `[3]` is that which ensures each cell occurs in exactly one column. – Timothy Shields Sep 03 '13 at 17:24
  • GREAT! Just one more question. I will have to make an integer solver myself. Is any simple integer solver algorithm sufficient to solve above formulation? – Abhishek Bansal Sep 03 '13 at 17:29
  • @AbhishekBansal You **do not** want to write your own mixed integer program solver. Find a package for whatever programming language you are using and go with that. – Timothy Shields Sep 03 '13 at 17:31
  • 2
    +1, an ILP is a good way to solve this problem, which is surely NP-complete. One issue with your formulation is that it does not distinguish permutations of columns, so if the optimal solution has d columns, there will be d! equal-score optimal solutions, which may cause a solver to do more work than necessary. You can fix this by e.g. forcing each column to have height <= the previous column: change constraint 1 from the first formulation to `[1a] sum { H_i | C_i = 1 } <= T; [1b] sum { H_i | C_i = k } <= sum { H_j | C_j = k-1 } T for k = 2, ..., N`. – j_random_hacker Sep 04 '13 at 02:55
  • @j_random_hacker Good suggestion to disambiguate the optimal solutions. – Timothy Shields Sep 04 '13 at 03:53
  • @TimothyShields Hi again, I am trying to solve the above formulation using lp_solve. I have 1200 binary variables and 30 non-integer variables, and there are at present 1230 constraints. I want to ask, if I add more constraints, then does it help the solver in solving quickly or does it increase its complexity? Also, is the above size "handle-able" for the solver? – Abhishek Bansal Sep 19 '13 at 09:46
  • @AbhishekBansal More constraints typically means more complexity. Also, this size definitely sounds reasonable. If this isn't a real-time application, that's a relatively small problem. – Timothy Shields Sep 20 '13 at 01:41
  • @TimothyShields Hi, sorry to bother again. I am facing difficulty in solving this problem for N > 20. lp_solve seems to hang. I have re-opened this question here http://math.stackexchange.com/questions/507699/strange-but-practical-bin-packing-problem. Please check if any solution is possible. Thanks..! – Abhishek Bansal Oct 02 '13 at 04:34
  • @AbhishekBansal If you use a primal-dual algorithm, you can get guaranteed bounds on how good any particular suboptimal solution is. Because of the combinatorial nature of this problem, you can't really aim to get an optimal solution. Consider simply stopping your solver short of finding an optimal solution, at a solution that's "good enough." – Timothy Shields Oct 02 '13 at 05:32
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.

Gilbert Le Blanc
  • 50,182
  • 6
  • 67
  • 111
  • Columns don't have to all be the same width. Ie need to put narrow cubicles in narrow columns and wide cubicles in wide columns – James Waldby - jwpat7 Aug 30 '13 at 17:25
  • Also, the minimum width and height of each cubicle is different. (sorry very complicated scenario) :) – Abhishek Bansal Aug 30 '13 at 17:29
  • @AbhishekBansal: Ok, my mistake. You can use the same idea as my answer, except you place the cubicles in the row in sorted minimum width order, descending. You still allocate the left over space to all the cubicles in the row evenly. – Gilbert Le Blanc Aug 30 '13 at 17:40
  • Yes thanks for your answer. Actually as I said, at present I have implemented it in exactly the same way as you have suggested. But the problem is that there is 2nd dimension as well. For example, it may happen that for the largest minHeight, the minWidth is small and vice-versa. In such a case would this approach be a good one? – Abhishek Bansal Aug 30 '13 at 17:44
  • @AbhishekBansal: I have still not figured out how height figures into placing cubicles. You're going to have to post a photograph and show us. – Gilbert Le Blanc Sep 03 '13 at 12:47
  • Image added, in case there is any confusion, please ask. Thanks – Abhishek Bansal Sep 03 '13 at 16:52
2

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.

Micromega
  • 12,486
  • 7
  • 35
  • 72
  • Thanks for the link. It seems interesting but I am not able to adapt that problem to suit my need. Any ideas? – Abhishek Bansal Sep 03 '13 at 08:34
  • In vm packing the items shares space. The total size can be smaller then each individual item. http://en.m.wikipedia.org/wiki/Bin_packing_problem – Micromega Sep 03 '13 at 09:56