The load-balanced multi-dimensional bin-packing problem

The bin-packing problem is one of the most investigated and applicable combinatorial optimization problems. In this paper we consider its multi-dimensional version with the practical extension of load balancing, i.e. to find the packing requiring the minimum number of bins while ensuring that the average center of mass of the loaded bins falls as close as possible to an ideal point, for instance, the center of the bin. We formally describe the problem using mixed-integer linear programming models, from the simple case where we want to optimally balance a set of items already assigned to a single bin, to the general balanced bin-packing problem. Given the difficulty for standard solvers to deal even with small size instances, a multi-level local search heuristic is presented. The algorithm takes advantage of the Fekete-Schepers representation of feasible packings in terms of particular classes of interval graphs, and iteratively improves the load balancing of a bin-packing solution using different search levels. The first level explores the space of transitive orientations of the complement graphs associated with the packing, the second modifies the structure itself of the interval graphs, the third exchanges items between bins repacking proper n-tuples of weakly balanced bins. Computational experiments show very promising results on a set of 3D bin-packing instances from the literature.