A Heuristic Column Generation Approach for the Stochastic Bin Packing Problem

The stochastic bin packing problem (SBPP) is an extension of the well-studied classical bin packing problem with respect to imperfect information on the item sizes. From a practical point of view, the latter are typically represented by (stochastically independent) normally distributed random variables with given means and variances. In this scenario, the SBPP requires to determine the minimum number of bins needed to pack all the items, with the risk of overloading a bin not exceeding a certain tolerable limit. Such computations are of high relevance in server consolidation applications, where decisions have to be made before witnessing the true item characteristics. The resulting integer optimization problems are generally nonlinear and therefore difficult to solve. For this reason, previous approaches from the literature can only handle small instance sizes exactly. In this work, we present a column generation algorithm using heuristic information and near-optimal solutions of the associated (challenging) pricing problems. Based on numerical tests, we show that in most cases this heuristic approach already leads to an optimal solution, so that much larger instance sizes can now be dealt with in reasonable time.