Bin packing: config-enum algorithm

Dependencies:

For a bin packing problem, suppose we have $k$ different types of items and there are $n_{i}$ items of each type. We are also promised that a bin can accommodate at most $t$ items (regardless of the types of the items).

A configuration is defined to be a $k$ -tuple $(m_{1}, m_{2}, \dots, m_{k})$ such that it is possible to pack $m_{i}$ copies of items of type $i$ for all $i$ in a single bin. Let there be $R$ possible configurations. Assume that we have an algorithm that given a $k$ -tuple, decides whether it is a configuration or not (for 1D bin packing, this algorithm simply checks that the sum of the items is at most 1). Assume this algorithm runs in time $O (V (t, k))$ (for 1D bin packing, $V (t, k) = k$ ).

Any bin packing instance can be solved exactly using the 'config-enum algorithm', also known as 'exact algorithm' or 'brute-force algorithm'. This algorithm first enumerates all possible configurations. Then it looks at all possible combinations of configurations that can give a valid bin packing. Out of these, we pick the combination with the least number of bins.

Let $m$ be a known upper-bound on the number of bins in the optimal solution. A naive upper-bound is $m \leq n$ , since we can pack each item in its own bin.

The config-enum algorithm is a $O (k R (\binom{m + R}{R}) + V (t, k) (\binom{t + k}{k}))$ -time algorithm. We can prove that $R \leq (\binom{k + t}{t}) \leq (t + 1)^{k}$ , so when $k$ and $t$ are constants, this is a polynomial-time algorithm. Also, $\begin{aligned} k R (\binom{m + R}{R}) + V (t, k) (\binom{t + k}{k}) \\ \leq k R (m + 1)^{R} + V (t, k) (t + 1)^{k} \\ \leq k (t + 1)^{k} (m + 1)^{(t + 1)^{k}} + V (t, k) (t + 1)^{k} . \end{aligned}$

Algorithm

Enumerating configurations

To enumerate all possible configurations, iterate over all $k$ -tuples with sum at most $t$ and where the $i^{th}$ element of the tuple is at most $n_{i}$ . Then check if the tuple is a valid configuration. This takes time $O (V (t, k) (\binom{t + k}{k}))$ . Since there can be at most $(\binom{t + k}{k})$ such tuples, $R \leq (\binom{t + k}{k})$ . Assign an integer identifier from 1 to $R$ to each configuration.

Enumerating combinations

To enumerate all possible combinations of configurations, iterate over all $R$ -tuples with sum at most $m$ . Here the $i^{th}$ element of the $R$ -tuple is the number of bins of configuration $i$ . This gives us $(\binom{m + R}{R})$ tuples.

To check if a combination is a valid bin packing, find the number of items of type $i$ across all bins. This should be greater than or equal to $n_{i}$ . Checking the validity of a combination takes $O (k R)$ time.

Finally pick the combination with the least number of bins, i.e. the $R$ -tuple with the least sum.

Bin packing: config-enum algorithm

Dependencies:

Algorithm

Enumerating configurations

Enumerating combinations

Dependency for:

Info:

Transitive dependencies: