Thursday, February 18, 2021

An easy variant of 2d bin packing

 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} \]

This is an easy model to solve. It almost takes no time. A solution can look like:




The number of bins is minimized. But the number of columns is not. The pink items in bin 2 and 3 could have been placed in the same column. Why did the solver create this configuration? That is a very difficult question to answer. A better question is: why did the solver not combine these pink items? Well, the answer is: there is no incentive to do this. Combining them does not lead to fewer used bins.

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


No comments:

Post a Comment