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

Patent metadata

Field	Value
Publication number	US-2015161317-A1
Application number	US-201414300688-A
Country	US
Kind code	A1
Filing date	Jun 10, 2014
Priority date	Dec 6, 2013
Publication date	Jun 11, 2015
Grant date	—

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.

First claim

1 . A computer-performed method of placing objects in partitions of a physical layout, the method comprising:
within a computer system, first determining requirements vectors corresponding to the objects, wherein the requirements vectors contain values specifying requirements of the object in multiple dimensions; and assigning the objects to the partitions of the physical layout using a bin-packing algorithm executed by the computer system that recursively explores partial solutions for assigning the objects to individual ones of the partitions in order to satisfy the requirements vectors for the objects, wherein the bin-packing algorithm extends the partial solutions via the recursion until the requirements in the requirements vectors are met by assignment of the corresponding object to partitions having sufficient resources in the multiple dimensions to meet the values specified in the requirements vectors, wherein the bin-packing algorithm tests requirements vectors of remaining unassigned ones of objects for both assignment and non-assignment to a current individual partition in a current partial solution until the current partial solution becomes a complete solution that satisfies the requirements vectors for the objects.

2 . The method of claim 1 , wherein the bin-packing algorithm terminates the recursion of partial solutions that do not become the complete solution upon detecting that a partial solution being explored is covered by a dominant solution previously explored.

3 . The method of claim 2 , wherein the detecting is performed by second determining that a requirements vector for an excluded object can be satisfied by the current individual partition without excluding another object assigned to the current individual partition in the current partial solution.

4 . The method of claim 1 , wherein the bin-packing algorithm comprises:
for the current partial solution, second determining if any objects remain to be assigned to the partitions; responsive to having determined that objects remain to be assigned to the partitions, selecting an unassigned object; with the selected object assigned to the partition corresponding to the current partial solution, first recursively applying the assigning of the objects to assign the remaining objects other than the selected object; third determining if the recursively applying generated a complete solution assigning the remaining objects; responsive to having determined that the recursively applying did not generate a complete solution, fourth determining if the current partition has an included object; and responsive to having determined that the current group has an included object, with the selected object excluded from the current partition, second recursively applying the assigning of the objects to assign the remaining objects other than the selected object.

5 . The method of claim 4 , further comprising:
prior to the second determining if any objects remain to be assigned to the partitions, fifth determining if any object placed in the current partition has a requirements vector that cannot be satisfied by the current partition or if any object excluded from the current partition has a requirements vector that cannot be satisfied by a remaining one of the partitions; and responsive to having determined that the requirements vector cannot be satisfied by the current partition or if any object excluded from the current partition has a requirements vector that cannot be satisfied by a remaining one of the partitions, not performing the selecting, the first recursively applying and the second recursively applying.

6 . The method of claim 1 , wherein the partitions are physical layout resources of an electronic device, and wherein the objects are interconnecting conductors of the electronic device.

7 . The method of claim 1 , wherein the partitions are physical storage locations, and wherein the objects are objects to be stored.

Assignees

• IBM

Inventors

• Moffitt Michael David

Classifications

• G06F30/18 Primary

  Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling (circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18) · CPC title

• G06F30/392 Primary

  Floor-planning or layout, e.g. partitioning or placement · CPC title

• G06F17/5072 Primary

  Physics · mapped topic