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 PARAMETER itemSize sizes of bin and items w 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 SET itemMap mapping between items and categories item1 .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
For each category \(t\) we calculate in advance the following numbers:
- 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 PARAMETER itemCount number of items in each category cat1 10.000, cat2 10.000, cat3 10.000, cat4 10.000, cat5 5.000, cat6 5.000 ---- 55 PARAMETER MaxItemsInCol capacity of a column cat1 5.000, cat2 20.000, cat3 4.000, cat4 6.000, cat5 7.000, cat6 12.000 ---- 59 PARAMETER maxCols maximum number of columns in a bin cat1 5.000, cat2 4.000, cat3 8.000, cat4 3.000, cat5 6.000, cat6 2.000 ---- 63 PARAMETER MaxInBin capacity of a bin cat1 10.000, cat2 10.000, cat3 10.000, cat4 10.000, cat5 5.000, cat6 5.000
We start with the assignment variable: \[\color{darkred}a_{t,k} \in \{0,1,2,\dots\}\] indicating the number of items of category \(t\) we place in bin \(k\). We need to place all items, so \[\sum_k \color{darkred}a_{t,k} = \color{darkblue}{\mathit{itemCount}}_t \>\>\forall t\] Next we introduce a variable \(\color{darkred}{nc}_{t,k}\) indicating the number of columns of category \(t\) in bin \(k\). We have: \[\color{darkred}{nc}_{t,k} \ge \frac{\color{darkred}a_{t,k}}{\color{darkblue}{\mathit{maxItemsInCol}}_t}\] This is similar to \[\color{darkred}{nc}_{t,k} = \left\lceil\frac{\color{darkred}a_{t,k}}{\color{darkblue}{\mathit{maxItemsInCol}}_t}\right\rceil\] We can't use a ceiling function in a linear model, so the bound will do.
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} \] |
We could fix this by adding a term to the objective that penalized this situation. However, the following model will also prevent this behavior.
Model B: assign columns
In this formulation, we form columns of items in advance, and then let the model figure out how to assign these columns to bins.
First we calculate beforehand, how many columns of each category we need: \[\color{darkblue}{\mathit{numCols}}_t = \left\lceil \frac{\color{darkblue}{\mathit{itemCount}}_t}{\color{darkblue}{\mathit{maxItemsInCol}}_t} \right\rceil\] This produces:
---- 67 PARAMETER numCols number of columns we need to assign cat1 2.000, cat2 1.000, cat3 3.000, cat4 2.000, cat5 1.000, cat6 1.000
Our assignment variable \(\color{darkred}a_{t,k}\) is redefined to indicate the number of columns of type \(t\) we allocate to bin \(k\). With this we can write the model as:
| 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} \] |
We need to assign items to their columns in post-processing. This leads to a solution like:
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