In [1], a question was posed about a particular type of 2d bin-packing. This is a good reason to play with some models.

First I discuss three formulations with continuous no-overlap constraints and one for discrete data. In the next post, I'll discuss the variant described by the post [1]. This actually leads to a very different, but easy problem.

#### Problem statement and example data

We consider \(n=50\) rectangular items of different sizes that have to be placed into bins. There are six different categories, each with a different size (height and width). All the bins have the same size. The goal is to use as few bins as possible.

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

Furthermore, we assume items cannot be rotated.

#### Continuous Model A

**not**assume that our sizes are integer-valued. The rectangles are allowed to have any positive width and height.

- Assignment of items to bins.
- We position the items inside a bin. No-overlap constraints are used for the items placed in the same bin.
- Some ordering constraints. This can make the solution look better and reduce symmetry in the problem.

**Assignment**

**Bounds**

**No-overlap**

**Objective**

**Order used bins**

**Order by area**

**Lower bound**

**Does it work?**

**Summary of the model**

MIP Model A |
---|

\[\begin{align} \min&\sum_k \color{darkred}u_k \\ & \color{darkred}u_k \ge \color{darkred}a_{i,k} &&\forall i,k \\ & \sum_k \color{darkred} a_{i,k} = 1 && \forall i \\ & \color{darkred}s_{i,j} \ge \color{darkred} a_{i,k} + \color{darkred} a_{j,k} - 1 && \forall k, i\lt j \\ & \color{darkred} x_i +\color{darkblue} w_i \le \color{darkred} x_j + \color{darkblue} M (1-\color{darkred}\delta_{i,j,1}) + \color{darkblue} M (1-\color{darkred}s_{i,j}) && \forall i \lt j\\ & \color{darkred} x_i \ge \color{darkred} x_j +\color{darkblue} w_j - \color{darkblue} M (1-\color{darkred}\delta_{i,j,2}) - \color{darkblue} M (1-\color{darkred}s_{i,j}) && \forall i \lt j\\ & \color{darkred} y_i +\color{darkblue} h_i \le \color{darkred} y_j + \color{darkblue} M (1-\color{darkred}\delta_{i,j,3}) + \color{darkblue} M (1-\color{darkred}s_{i,j})&& \forall i \lt j \\ & \color{darkred} y_i \ge \color{darkred} y_j +\color{darkblue} h_j - \color{darkblue} M (1-\color{darkred}\delta_{i,j,4}) - \color{darkblue} M (1-\color{darkred}s_{i,j}) && \forall i \lt j\\ & \sum_p \color{darkred}\delta_{i,j,p}\ge 1 && \forall i \lt j \\ & \color{darkred}u_k \ge \color{darkred}u_{k+1} && \forall k \> \text{except last}\\ & \color{darkred}u_k \in [0,1] \\ & \color{darkred} a_{i,k} \in \{0,1\} \\ & \color{darkred}s_{i,j}\in [0,1] \\ & \color{darkred}\delta_{i,j,p} \in \{0,1\} \end{align} \] |

#### Alternative model B

I don't immediately recognize much of my model in this version. The paper mentions that all data is assumed to be integer-valued. This is actually not required for this model: it is happy with floating-point values.

- Only \(\alpha_{i,k}\) for \(i \ge k\) is used. (This essentially means \(\alpha_{i,k}=0\) for \(i \lt k\)).
- The diagonal \(\alpha_{k,k}\) indicates if bin \(k\) is used. This explains the formulation of the objective.
- If the diagonal element is zero, the whole column should be zero, This is stated in constraint (3). We can skip equation (3) for the case \(i=k\). I.e. we only need to apply it for \(i\gt k\) instead of \(i\ge k\).

#### Alternative model C

- \(l_{i,j}\) indicating that item \(i\) is to the left of item \(j\),
- \(b_{i,j}=1\) means: item \(i\) is below item \(j\),
- \(p_{i,j}=1\) indicates \(m_i \lt m_j\).

#### Grid model D

Grid Model D |
---|

\[\begin{align} \min&\sum_k \color{darkred}u_k \\ & \sum_{r,c,k} \color{darkred}x_{t,r,c,k} = \color{darkblue}{\mathit{num}}_t && \forall t\\ & \sum_{t,r',c'|\color{darkblue}{\mathit{affect}}(r,c,t,r',c')} \color{darkred}x_{t,r',c',k} \le \color{darkred}u_k &&\forall r,c,k \\ & \color{darkred}u_k \ge \color{darkred}u_{k+1} && \forall k \> \text{except last} \\& \color{darkred}x_{t,r,c,k} \in \{0,1\} \\& \color{darkred}u_k \in [0,1] \end{align}\] |

#### Performance

Model A | Model B | Model C | Model D | |
---|---|---|---|---|

Data | Continuous | Continuous | Continuous | Integer |

Equations | 18,945 | 85,801 | 8,625 | 24,016 |

Variables | 6,746 | 6,276 | 7,501 | 144,011 |

Discrete variables | 5,400 | 6,175 | 7,400 | 144,010 |

Nonzeros | 63,289 | 425,176 | 29,500 | 10,558,099 |

Objective | 2 | 2 | 2 | 2 |

Time | 280 | 793 | 338 | 4,825 |

Nodes | 1,932 | 10,109 | 104,495 | 0 |

Iterations | 281,877 | 240,258 | 2,078,174 | 227,935 |

**mipemphasis**to put more effort into reaching optimality.

#### 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
- Christian Blum, Verena Schmid and Lukas Baumgartner,
*On Solving the Oriented Two-Dimensional under Free Guillotine Cutting: Exploiting the Power of Probabilistic Solution Construction*, sept. 2012,. https://www.researchgate.net/publication/230795080_On_Solving_the_Oriented_Two-Dimensional_Bin_Packing_Problem_under_FreeGuillotine_Cutting_Exploiting_the_Power_of_Probabilistic_SolutionConstruction - Christian Blum, Verena Schmid,
*Solving the 2D bin packing problem by means of a hybrid evolutionary algorithm*, Procedia Computer Science 18 ( 2013 ) 899 – 908, https://www.sciencedirect.com/science/article/pii/S1877050913003980 - David Pisinger, Mikkel Mühldorff Sigurd,
*Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem,*January 2007, Informs Journal on Computing 19(1):36-51

I looked at a similar model many years ago. In my case, everything fell onto a grid, so I wrote a very different model: x[i,j,k] if item k is in position i,j. Then I had a constraint for every position in the grid: sum (ii,jj,k covering i,j) x[i,j,k] <= 1 for all grid positions (i,j). Performance was much better - no disjunctive constraint.

ReplyDeleteI think in my case I need x(item,row,col,bin). About 1.2e6 variables if I did not make a mistake. Worth a try...

DeleteYou can simultaneously strengthen and shrink Model D by replacing <= 1 with u[k] and then omitting the x <= u constraints, which are then dominated.

Delete