The load-balanced multi-dimensional bin-packing problem

Alessio Trivella, David Pisinger

    Research output: Contribution to journalJournal articleResearchpeer-review

    1304 Downloads (Pure)


    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.
    Original languageEnglish
    JournalComputers and Operations Research
    Pages (from-to)152-164
    Publication statusPublished - 2016


    • Load balancing
    • Local search
    • MILP modeling
    • Multi-dimensional bin-packing


    Dive into the research topics of 'The load-balanced multi-dimensional bin-packing problem'. Together they form a unique fingerprint.

    Cite this