slides.md

theme	title	titleTemplate	background	class	highlighter	lineNumbers	colorSchema	drawings	download
seriph	3D-BPP	%s - Slides	https://www.publicdomainpictures.net/pictures/200000/velka/plain-red-background.jpg	text-center	prism	false	light	persist	true

<style> p { opacity: 1.0 !important; } </style>

3D Bin Packing

Artificial Intelligence in Industry - Final Project
University of Bologna - Academic Year 2020/21

Leonardo Calbi, Lorenzo Cellini, Alessio Falai

---

3D-BPP

Problem definition

• We are given a set of $n$ rectangular-shaped items, each characterized by width $w_j$, depth $d_j$ and height $h_j$
• We are given a number of identical 3D containers (bins) having width $W$, depth $D$ and height $H$
• The three-dimensional bin-packing problem (3D-BPP) consists in orthogonally packing all the items into the minimum number of bins

Assumptions

• Items may not be rotated
• We have unlimited bins $b_1,b_2,\dots$ at our disposal
• All input data are positive integers satisfying $w_j\le W,d_j\le D,h_j\le H$

---

Lower bounds

1. $L_0=\lceil \frac{\sum _{j=1}^n{v}_j}{B}\rceil$, where $v_j=w_j\times d_h\times h_j$
   • Continuous lower bound: measures the overall liquid volume
   • Worst-case performance ratio of $\frac{1}{8}$
   • Time complexity: $O(n)$
2. $L_1=max{L}_1^{WH},L_1^{WD},L_1^{HD}$
   • Obtained by reduction to the one-dimensional case
   • Worst-case performance arbitrarily bad
   • Time complexity: $O(n)$
3. $L_2=max{L}_2^{WH},L_2^{WD},L_2^{HD}$
   • Explicitly takes into account the three dimensions of the items and dominates $L_1$
   • Worst-case performance ratio of $\frac{2}{3}$
   • Time complexity: $O(n^2)$

---

Dataset

Distributions

Misplaced \hline

$$
\begin{array} {|l|l|l|}\hline
\textbf{Characteristic} & \textbf{Distribution} & \textbf{Parameters}        \ \hline
\text{Depth/width ratio } R_{DW}       & \text{Normal}                & (0.695,0.118)  \\
\text{Height/width ratio } R_{HW}      & \text{Lognormal}             & (-0.654,0.453) \\
\text{Repetition } F             & \text{Lognormal}             & (0.544,0.658)  \\
\text{Volume } V     & \text{Lognormal}             & (2.568,0.705) \\
\text{Weight } L     & \text{Lognormal}             & (2,2) \ \hline
\end{array}
$$

Reasoning

1. Volumes: $V\sim LN(\mu ,{\sigma }^2),\mu =\frac{\sum _{j=1}^N\log v_j}{N},{\sigma }^2=\frac{\sum _{j=1}^N(\log v_j-\mu {)}^2}{N},N=166407,j\in C_1,\dots C_5$
2. Widths: $W=(\frac{V}{R_{DW}\times R_{HW}}{)}^{\frac{1}{3}}$
3. Depths: $D=W\times R_{DW}$
4. Heights: $H=W\times R_{HW}$

---

Superitems

• A superitem is a collection of individual items that are compactly stacked together
• Building procedure
  1. Single: composed of a unique item
  2. Horizontal: composed of items having the exact same dimensions
     • Possibility to restrict their generation (2D, 2W, 4 or none)
  3. Vertical: composed of items s.t. the ones on top have an area support of at least $70$
     • Maximum $M$ stacked superitems (either single or horizontal)

---

Layers

• A layer is defined as a two-dimensional arrangement of items within the horizontal boundaries of a bin with no superitems stacked on top of each other
• Superitems are placed relative to layers and layers are placed relative to bins

---

Workflow

---

layout: two-cols

Baseline

::right::

Constraints

• (5): ensure that every item is included in a layer
• (6): define the height of layer $l$
• (7): redundant valid cuts that force the area of a layer to fit within the area of a bin
• (8): enforce at least one relative positioning relationship between each pair of items in a layer
• (9) and (10): ensure that there is at most one spatial relationship between items $i$ and $j$ along each of the width and depth dimensions
• (11) and (12): non-overlapping constraints
• (13) and (14): ensure that items are placed within the boundaries of the bin

---

layout: two-cols

MAXRECTS

::right::

Details

• MAXRECTS is a procedural algorithm for solving the 2D bin packing problem, based on an extension of the GUILLOTINE split rule
• Height groups: divide the whole pool of superitems into groups having heights within a given tolerance
• MAXRECTS is used to generate layers
• Run multiple strategies (Bottom-Left, Best Area Fit, Best Short Side Fit and Best Long Side Fit) and select the most dense layers

---

Column generation

• Warm start: single item layers vs MAXRECTS
• Each iteration builds only a single layer and adds it to the whole pool
• Stopping criterion: maximum iterations or convergence (non-negative reduced costs)
• Optimality: no branch-and-price scheme

---

RMP

• RMP selects the best layers so far
• ${\alpha }_l\ge 0$ represents the linear relaxation of the integrality constraint ${\alpha }_l\in 0,1$
• $\lambda$ are the dual variables corresponding to constraints (18)
• The master problem is solved using BOP (it only contains boolean variables), while the reduced one is solved with GLOP (linear program)

---

SP

• SP selects items and positions them in a new layer
• $o^l-\sum _i\sum _s{\lambda }_i{f}_{si}{z}_{sl}$ is the reduced cost of a new layer $l$
• SP can be solved in the following ways
  • MAXRECTS: solve the whole pricing subproblem heuristically, using MAXRECTS to place superitems by biggest duals first
  • Placement and no-placement strategy
    1. No-placement: serves as an item selection mechanism, thus ignoring the expensive placement constraints (MIP or CP)
    2. Placement: checks whether there is a feasible placement of the selected items in a layer and places them if possible, otherwise iterates with the no-placement model (MIP or CP or MAXRECTS)

---

Layer filtering

1. Discard layers by densities (given a minimum density $d_m$)
2. Discard layers by item coverage
   • If at least one item in layer $l$ was already selected more times than $M_a$, discard $l$
   • If at least $M_s$ items in layer $l$ are already covered by previously selected layers, discard $l$
3. Remove duplicated items
   • Remove superitems in different layers containing the same item (remove the ones in less dense layers)
   • Remove superitems in the same layer containing the same item (remove the ones with less volume)
   • Re-arrange layers (using MAXRECTS) in which at least one superitem was removed (if $d_l>d_m$)
4. Remove empty layers
5. Sort layers by densities

---

Bin packing

1. Uncovered items: create new layers filled with items that were not covered in the previous procedures and add them to the layer pool
2. Bins building procedure: stack layers on top of each other until a bin is full and open new bins as needed
3. Compact bins: let items "fall" to the ground as much as possible, without allowing intersections

---

Future improvements

• Allow items to be rotated on the 3 axis
• Integrate the branch-and-price scheme into column generation to prove optimality
• Handle weight constraints and bin load capacity
• Improve item support through MP models (as described in the paper)
• Load bins inside containers

---

layout: center

Demo

python3 -m streamlit run src/dashboard.py
jupyter notebook bpp.ipynb

---

layout: end

Bye bye