Price-and-branch heuristic for vector bin packing

Vector bin packing is an NP-hard problem in which a set of item vectors must be packed into a minimum number of bins such that, in each bin, the sum of the vectors does not exceed the bin's vector capacity. Vector bin packing has many applications such as scheduling virtual machines in cloud computing. In this paper, we introduce the Pattern Heuristic, a price-and-branch heuristic which applies column generation. It creates a large pool of valid packings called patterns by running fast heuristics. Then it optimally solves the integer linear program of finding a minimum set of patterns which covers the complete set of items. Despite its complexity, it finds optimal or near-optimal solutions for benchmark instances with 200 items in a matter of seconds. The pattern pool is created by a Local Search Heuristic which, while being very fast, achieves surprisingly good results. As a stand-alone heuristic, it is suitable for scenarios with real-time demands. The new heuristics are compared with algorithms from the literature in experiments using established benchmarks. They demonstrate a good trade-off between running time and packing quality. The Pattern Heuristic computes new optimal solutions for a 20-dimensional benchmark.