Multi-dimensional Bin Packing Problems with Guillotine Constraints

Rasmus Resen Amossen, David Pisinger

    Research output: Contribution to journalJournal articleResearchpeer-review


    The problem addressed in this paper is the decision problem of determining if a set of multi-dimensional rectangular boxes can be orthogonally packed into a rectangular bin while satisfying the requirement that the packing should be guillotine cuttable. That is, there should exist a series of face parallel straight cuts that can recursively cut the bin into pieces so that each piece contains a box and no box has been intersected by a cut. The unrestricted problem is known to be NP-hard. In this paper we present a generalization of a constructive algorithm for the multi-dimensional bin packing problem, with and without the guillotine constraint, based on constraint programming.
    Original languageEnglish
    JournalComputers and Operations Research
    Issue number11
    Pages (from-to)1999-2006
    Publication statusPublished - 2010


    • constraint programming
    • packing
    • cutting


    Dive into the research topics of 'Multi-dimensional Bin Packing Problems with Guillotine Constraints'. Together they form a unique fingerprint.

    Cite this