rectangle-packing-solver

A solver to find a solution of the 2D rectangle packing problem by simulated annealing (SA) optimization. Sequence-pair [1] is used to represent a rectangle placement (floorplan).

Features

• Solution quality and execution time are tunable, since the solver is SA-based.
• Not only integers but also real numbers can be set as a rectangle width and height.
• A rectangle can rotate while optimizing.
• The built-in visualizer visualizes a floorplan solution.

Installation

pip install rectangle-packing-solver

Example Usage

Sample code:

import rectangle_packing_solver as rps

# Define a problem
problem = rps.Problem(rectangles=[
    [4, 6],  # Format: [width, height] as list. Default rotatable: False
    (4, 4),  # Format: (width, height) as tuple. Default rotatable: False
    {"width": 2.1, "height": 3.2, "rotatable": False},  # Or can be defined as dict.
    {"width": 1, "height": 5, "rotatable": True},
])
print("problem:", problem)

# Find a solution
print("\n=== Solving without width/height constraints ===")
solution = rpm.Solver().solve(problem=problem)
print("solution:", solution)

# Visualization (to floorplan.png)
rps.Visualizer().visualize(solution=solution, path="./floorplan.png")

# [Other Usages]
# We can also give a solution width (and/or height) limit, as well as progress bar and random seed
print("\n=== Solving with width/height constraints ===")
solution = rps.Solver().solve(problem=problem, height_limit=6.5, show_progress=True, seed=1111)
print("solution:", solution)
rps.Visualizer().visualize(solution=solution, path="./figs/floorplan_limit.png")

Output:

problem: Problem({'n': 4, 'rectangles': [{'id': 0, 'width': 4, 'height': 6, 'rotatable': False}, {'id': 1, 'width': 4, 'height': 4, 'rotatable': False}, {'id': 2, 'width': 2.1, 'height': 3.2, 'rotatable': False}, {'id': 3, 'width': 1, 'height': 5, 'rotatable': True}]})

=== Solving without width/height constraints ===
solution: Solution({'sequence_pair': SequencePair(([3, 0, 2, 1], [0, 1, 3, 2])), 'floorplan': Floorplan({'positions': [{'id': 0, 'x': 0, 'y': 0, 'width': 4, 'height': 6}, {'id': 1, 'x': 4, 'y': 0, 'width': 4, 'height': 4}, {'id': 2, 'x': 5.0, 'y': 4.0, 'width': 2.1, 'height': 3.2}, {'id': 3, 'x': 0, 'y': 6, 'width': 5, 'height': 1}], 'bounding_box': (8, 7.2), 'area': 57.6})})

=== Solving with width/height constraints ===
Progress: 100%|█████████████████████████████████████████████████████████████| 10000/10000 [00:05<00:00, 1764.33it/s]
solution: Solution({'sequence_pair': SequencePair(([0, 1, 2, 3], [0, 3, 1, 2])), 'floorplan': Floorplan({'positions': [{'id': 0, 'x': 0, 'y': 0, 'width': 4, 'height': 6}, {'id': 1, 'x': 4, 'y': 1, 'width': 4, 'height': 4}, {'id': 2, 'x': 8.0, 'y': 1.0, 'width': 2.1, 'height': 3.2}, {'id': 3, 'x': 4, 'y': 0, 'width': 5, 'height': 1}], 'bounding_box': (10.1, 6), 'area': 60.599999999999994})})

Floorplan (example):

Floorplan (larger example):

References

[1] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence-pair," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, no. 12, pp. 1518--1524, Dec 1996.

License