Multi-dimensional physical arrangement techniques using bin-packing with per-branch combination tries

Abstract

A recursive solution to a bin-packing algorithm provides efficient placement of objects in a physical layout. The algorithm determines requirement vectors for the objects that specify requirement for placement of the object in multiple dimensions, thereby forming a multi-dimensional bin-packing problem. The algorithm assigns the objects to physical partitions or 'bins' by recursively exploring partial solutions that place the objects in the partitions by extending the partial solutions via recursion until the objects are placed. The bin-packing algorithm tests requirements vectors for remaining unassigned ones of the objects for both assignment and non-assignment to a current partition in a current partial solution until the current partial solution becomes a complete solution that satisfies the requirement vectors for the plurality of objects.