In [1] the following problem is posted:

Consider the 2d bin packing problem [2]. Now we have the following additional restrictions: items of a different type or category cannot be below or above each other. In other words, we arrange items of the same type in columns.

We use again our small data set:

---- 37 PARAMETERitemSizesizes of bin and itemsw h cat1 7.000 12.000 cat2 9.000 3.000 cat3 5.000 14.000 cat4 13.000 9.000 cat5 6.000 8.000 cat6 20.000 5.000 bin 40.000 60.000 ---- 37 SETitemMapmapping between items and categoriesitem1 .cat1, item2 .cat1, item3 .cat1, item4 .cat1, item5 .cat1, item6 .cat1, item7 .cat1 item8 .cat1, item9 .cat1, item10.cat1, item11.cat2, item12.cat2, item13.cat2, item14.cat2 item15.cat2, item16.cat2, item17.cat2, item18.cat2, item19.cat2, item20.cat2, item21.cat3 item22.cat3, item23.cat3, item24.cat3, item25.cat3, item26.cat3, item27.cat3, item28.cat3 item29.cat3, item30.cat3, item31.cat4, item32.cat4, item33.cat4, item34.cat4, item35.cat4 item36.cat4, item37.cat4, item38.cat4, item39.cat4, item40.cat4, item41.cat5, item42.cat5 item43.cat5, item44.cat5, item45.cat5, item46.cat6, item47.cat6, item48.cat6, item49.cat6 item50.cat6

I'll try two different models:

- Assign items to bins, arrange them in columns
- Assign columns to bins

#### Model A: assign items

- the number of items in each category: \[\color{darkblue}{\mathit{itemCount}}_t = \sum_{i|\color{darkblue}{\mathit{itemMap}}(i,t)} 1\]
- the number of items that fit in a column: \[\color{darkblue}{\mathit{maxItemsInCol}}_t =\left\lfloor \frac{\color{darkblue}h_{\mathit{bin}}}{\color{darkblue}h_t} \right\rfloor\]
- the maximum number of columns in a bin: \[\color{darkblue}{\mathit{maxCols}}_t =\left\lfloor \frac{\color{darkblue}w_{\mathit{bin}}}{\color{darkblue}w_t} \right\rfloor\]
- the maximum number of items of category \(t\) that fit in a bin: \[\color{darkblue}{\mathit{maxInBin}}_t = \min(\color{darkblue}{\mathit{itemCount}}_t, \color{darkblue}{\mathit{maxItemsInCol}}_t\cdot \color{darkblue}{\mathit{maxCols}}_t) \]

---- 51 PARAMETERitemCountnumber of items in each categorycat1 10.000, cat2 10.000, cat3 10.000, cat4 10.000, cat5 5.000, cat6 5.000 ---- 55 PARAMETERMaxItemsInColcapacity of a columncat1 5.000, cat2 20.000, cat3 4.000, cat4 6.000, cat5 7.000, cat6 12.000 ---- 59 PARAMETERmaxColsmaximum number of columns in a bincat1 5.000, cat2 4.000, cat3 8.000, cat4 3.000, cat5 6.000, cat6 2.000 ---- 63 PARAMETERMaxInBincapacity of a bincat1 10.000, cat2 10.000, cat3 10.000, cat4 10.000, cat5 5.000, cat6 5.000

Side note: it is possible to (approximately) model the ceiling function \(y = \left\lceil x \right\rceil\) inside a MIP model: \[\begin{align} & y = x + s \\ & s \in [0,0.9999] \\ & y \in \{0,1,2,\dots\}\end{align} \]

The number of columns is limited by the bin width: \[\sum_t \color{darkred}{nc}_{t,k} \cdot \color{darkblue}w_t \le \color{darkblue}w_{\mathit{bin}}\] Finally, we need to impose the implication \[\color{darkred}u_k = 0 \Rightarrow \color{darkred}a_{t,k} = 0\] This can be written as: \[\color{darkred}a_{t,k} \le \color{darkred}u_k \cdot \color{darkblue}{\mathit{maxInBin}}_t\] The only thing that is left is to minimize the number of used bins.

With this we can write our complete model:

Model A |
---|

\[\begin{align}\min & \sum_k \color{darkred}u_k\\ & \sum_k \color{darkred}a_{t,k} = \color{darkblue}{\mathit{itemCount}}_t && \forall t \\ & \color{darkred}{nc}_{t,k} \ge \frac{\color{darkred}a_{t,k}}{\color{darkblue}{\mathit{maxItemsInCol}}_t} && \forall t,k \\ & \sum_t \color{darkred}{nc}_{t,k} \cdot \color{darkblue}w_t \le \color{darkblue}w_{\mathit{bin}} && \forall k\\ & \color{darkred}a_{t,k} \le \color{darkred}u_k \cdot \color{darkblue}{\mathit{maxInBin}}_t \\ &\color{darkred}u_k \ge\color{darkred}u_{k+1} \\ &\color{darkred}u_k\in \{0,1\} \\ &\color{darkred}a_{t,k} \in \{0,1,\dots,\color{darkblue}{\mathit{maxInBin}}_t\} \\ &\color{darkred}{nc}_{t,k} \in \{0,1,\dots,\color{darkblue}{\mathit{maxCols}}_t\} \end{align} \] |

**That is a very difficult question to answer. A better question is:**

*Why did the solver create this configuration?***Well, the answer is: there is no**

*why did the solver not combine these pink items?***incentive**to do this. Combining them does not lead to fewer used bins.

#### Model B: assign columns

---- 67 PARAMETERnumColsnumber of columns we need to assigncat1 2.000, cat2 1.000, cat3 3.000, cat4 2.000, cat5 1.000, cat6 1.000

Model B |
---|

\[\begin{align}\min & \sum_k \color{darkred}u_k\\ & \sum_k \color{darkred}a_{t,k} = \color{darkblue}{\mathit{numCols}}_t && \forall t \\ & \sum_t \color{darkred}a_{t,k}\cdot \color{darkblue}w_t \le \color{darkblue}w_{\mathit{bin}} && \forall k \\ & \color{darkred}a_{t,k} \le \color{darkred}u_k \cdot \color{darkblue}{\mathit{maxCols}}_t \\ &\color{darkred}u_k \ge\color{darkred}u_{k+1} \\ &\color{darkred}u_k\in \{0,1\} \\ &\color{darkred}a_{t,k} \in \{0,1,\dots,\color{darkblue}{\mathit{maxInBin}}_t\} \end{align} \] |

#### Conclusions

- In the original post, this problem was described as a variant of a 2d bin packing problem. This lead to the suggestion to start with a standard bin packing model and adapt this a bit. Here, I did things very differently: start from scratch and ignore what we know about bin packing.
- Opposed to bin packing models, which are notoriously difficult to solve, we use here simple, fast models.

#### References

- How to model fixed width columns for 2d bin/strip packing problem? https://stackoverflow.com/questions/66156154/how-to-model-fixed-width-columns-for-2d-bin-strip-packing-problem
- 2d Bin Packing, http://yetanothermathprogrammingconsultant.blogspot.com/2021/02/2d-bin-packing.html

## No comments:

## Post a Comment