 |
| Boston custom house tower |
Assume we have an infinite collection of 3d boxes of different sizes. As an example let's use [1]:
---- 30 PARAMETER boxes available box sizes size-x size-y size-z box1 4 6 7 box2 1 2 3 box3 4 5 6 box4 10 12 32
We want to build a tower of boxes such that the base of the box on top is strictly smaller than the underlying box. The "strictly" part is essential. Otherwise, we can just repeat the same type of box ad infinitum. The interesting angle is: we can rotate the boxes. Without loss of generality, we can assume that for all boxes, after rotation, we have: the width (\(x\)) is less than the depth \((y\)). (This may require a bit of thinking). With this, any box can be placed in just three different ways.
 |
| 3d rotations |
The objective is to build a tower that is as tall as possible. In [1], this problem is solved using a Dynamic Programming algorithm. Here I want to see how this looks using a MIP model.
Model development
The first thing to do is to create the rotations. I created a mapping set that maps from one size to another. Then I applied this mapping to all our boxes. The result is:
---- 38 SET rot rotate s1->s2 size-x size-y size-z rot1.size-x YES rot1.size-y YES rot1.size-z YES rot2.size-x YES rot2.size-y YES rot2.size-z YES rot3.size-x YES rot3.size-y YES rot3.size-z YES ---- 44 PARAMETER sizes sizes under rotation size-x size-y size-z box1.rot1 4 6 7 box1.rot2 4 7 6 box1.rot3 6 7 4 box2.rot1 1 2 3 box2.rot2 1 3 2 box2.rot3 2 3 1 box3.rot1 4 5 6 box3.rot2 4 6 5 box3.rot3 5 6 4 box4.rot1 10 12 32 box4.rot2 10 32 12 box4.rot3 12 32 10
I used the assumption that the original data is ordered by size (i.e. \(x \le y \le z\)). See our first data table above to verify that this indeed holds. The set \(\color{darkblue}{\mathit{rot}}\) was created by hand: it says what type of rotations we can apply. It produces three rotations as follows:\[\begin{pmatrix}x\\y\\z\end{pmatrix} \rightarrow \begin{pmatrix}x\\y\\z\end{pmatrix}\> \begin{pmatrix}x\\z\\y\end{pmatrix}\>\begin{pmatrix}y\\z\\x\end{pmatrix}\] Note that all these rotations obey that the first coordinate is less-than-or-equal to the second coordinate. After this, we just apply this operation to our original data table and produce all rotations for all boxes in one swoop.
With this under our belt, the model is not very difficult. We use the following indices:
- \(i\): the level. Just use a set that is larger than the number of levels you expect.
- \(k\): the box type from the inventory.
- \(r\): the rotation
- \(s\): the sizes in each direction.
- \({\mathit{xy}}\): subset of \(s\), only the \(x\) and \(y\) coordinates.
| MIP Model |
|---|
| \[\begin{align}\max\>&\color{darkred}{\mathit{height}}=\sum_i \color{darkred}{\mathit{size}}_{i,z}\\ & \color{darkred}b_i = \sum_{k,r}\color{darkred}{\mathit{assign}}_{i,k,r} \\ & \color{darkred}b_i \le \color{darkred}b_{i-1} && \text{ordering} \\ & \color{darkred}{\mathit{size}}_{i,s} = \sum_{k,r}\color{darkred}{\mathit{assign}}_{i,k,r} \cdot \color{darkblue}{\mathit{sizes}}_{k,r,s} && \text{size at level $i$} \\ & \color{darkred}{\mathit{size}}_{i,xy} \le\color{darkred}{\mathit{size}}_{i-1,xy}-0.5\cdot\color{darkred}b_i && \text{smaller boxes on top} \end{align}\] |
Notes:
- We start at the bottom, i.e. \(\color{darkred}b_1 = 1\). So \(\color{darkred}b_i=0\) only happens only at the top. The constraint \(\color{darkred}b_i \le \color{darkred}b_{i-1}\) is not really needed as the equation that requires smaller boxes to be on top, has the same effect. So, we can make the model even more compact.
- We require that the width and the depth are both 0.5 less than the box of the previous layer. We make an exception when there is no box, in which case all sizes remain zero. If we have continuous sizes, we need to change this minimum shrinkage to something like 0.001 (this number should be larger than the feasibility tolerance of the solver).
---- 82 PARAMETER results optimal stack size-x size-y size-z level1.box4.rot3 12 32 10 level2.box4.rot1 10 12 32 level3.box1.rot3 6 7 4 level4.box3.rot3 5 6 4 level5.box3.rot1 4 5 6 level6.box2.rot3 2 3 1 level7.box2.rot1 1 2 3
- This model is of course very different from the Dynamic Programming algorithm shown in [1].
- It is very easy to change the model to use a maximum height in terms of blocks (instead of inches or cm). We can choose from: \[\begin{align} & \max \> \color{darkred}{\mathit{height}}=\sum_i \color{darkred}{\mathit{size}}_{i,z} && \text{maximize height}\\ & \max\>\color{darkred}{\mathit{numBoxes}}=\sum_i \color{darkred}b_i && \text{maximize boxes (or levels)}\end{align}\] For this example, the solution is the same for both objectives.
- I started by saying we have an infinite supply of boxes. Actually, we never need more than two boxes of each type.
A larger data set
---- 34 PARAMETER boxes available box sizes size-x size-y size-z box1 2.546 12.529 16.766 box2 8.589 14.798 18.961 box3 5.953 15.874 18.057 box4 3.710 11.570 13.921 box5 3.630 5.806 12.108 box6 3.016 9.774 18.252 box7 4.148 6.584 9.661 box8 8.706 11.957 18.949 box9 1.604 8.624 16.607 box10 5.502 10.420 14.153
---- 113 PARAMETER results optimal stack INDEX 1 = max height size-x size-y size-z level1.box2 .rot3 14.798 18.961 8.589 level2.box8 .rot2 8.706 18.949 11.957 level3.box9 .rot3 8.624 16.607 1.604 level4.box2 .rot1 8.589 14.798 18.961 level5.box10.rot2 5.502 14.153 10.420 level6.box4 .rot2 3.710 13.921 11.570 level7.box5 .rot2 3.630 12.108 5.806 level8.box6 .rot1 3.016 9.774 18.252 level9.box9 .rot1 1.604 8.624 16.607 INDEX 1 = max boxes size-x size-y size-z level1 .box2 .rot3 14.798 18.961 8.589 level2 .box8 .rot3 11.957 18.949 8.706 level3 .box6 .rot3 9.774 18.252 3.016 level4 .box9 .rot3 8.624 16.607 1.604 level5 .box3 .rot1 5.953 15.874 18.057 level6 .box10.rot2 5.502 14.153 10.420 level7 .box4 .rot2 3.710 13.921 11.570 level8 .box5 .rot2 3.630 12.108 5.806 level9 .box6 .rot1 3.016 9.774 18.252 level10.box9 .rot1 1.604 8.624 16.607 ---- 113 PARAMETER objectives optimal values height vs boxes height boxes max height 103.767 9.000 max boxes 102.629 10.000
 |
| "max height" vs "max levels" results |
This larger example also gives us the opportunity to see if the extra ordering condition \(\color{darkred}b_i \le \color{darkred}b_{i-1}\) is helping or not. The model with the "max boxes" objective solves in zero nodes, so I'll focus on the "max height" objective. I ran the "max height" problem both with and without the extra constraint, and the results are:
---- 136 PARAMETER stats statistics iterations nodes objective extra 2672.000 402.000 103.767 no extra 4679.000 713.000 103.767
References
- Box stacking problem, DP-22, https://www.geeksforgeeks.org/box-stacking-problem-dp-22/
Appendix: GAMS model
|
$ontext |
- There are some interesting modeling issues in the model.
- The set levels should be larger than the expected size. (Obvious questions are: What happens if too small? Can we detect this?)
- The equation order is optional. It can help with large instances.
- Note how the equations order and smaller have protection against the index becoming 1. E.g. order(i-1). Check the equation listing to see the impact. (Question: what happens if we drop this?)
No comments:
Post a Comment