# Heuristics for vector bin packing

## Metadata

URL: <https://www.microsoft.com/en-us/research/publication/heuristics-for-vector-bin-packing/>

Authors: Rina Panigrahy, Kunal Talwar, Lincoln Uyeda, Udi Wieder (*MSR*)

## Understanding the paper

### Background

The resource allocation problem is actually a vector bin packing problem.

Generally, two types of methods can be used to solve this problem. One is based on First Fit Decreasing (FFD) heuristics, and the other is formulated as Integer Linear Program (ILP) (the disadvantage is that it cannot scale).

### Algorithms

#### Step

* Item-centric
  * Sort items in decreasing order of "size".
  * Place items sequentially in the first bin with sufficient capacity.
* Bin-centric
  * Open one bin at any time.
  * Place the "largest" item that fits the current bin.
  * Open a fresh bin if there is no feasible item.

#### FFD-based heuristics

* **FFDProd**: $$w(I) = \prod\_{i \le d} I\_i$$
* **FFDSum**: $$w(I) = \sum\_{i \le d} a\_i I\_i$$
  * **FFDAvgSum**: $$a\_i = \frac{1}{n} \sum\_{l=1}^{n} I\_i^l$$
  * **FFDExpSum**: $$a\_i = exp(\epsilon \cdot \frac{1}{n} \sum\_{l=1}^{n} I\_i^l)$$

#### Heuristics that consider the item's demand `I` and the bin's remaining capacity `r(t)`

* **Dot Product**: maximize $$\sum\_i a\_i I\_i^l r(t)\_i$$
* **Norm-based Greedy (**$$L\_n$$**)**: minimize $$\sum\_i a\_i (I\_i^l - r(t)\_i)^n$$
* **Grasp and Bubblesearch**: choose the $$k$$-th "largest" item, where $$k$$ is chosen with probability proportional to $$(1-p)^k$$. Random multiple times and pick the best allocation.