kotarot / rectangle-packing-solver

A solver to find a solution of the 2D rectangle packing problem by simulated annealing (SA) optimization.

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

rectangle-packing-solver's Issues

Getting Wrong Result

Hello there, actually i like your packing solver because it came out with visualization.

The issue here im getting wrong placement of the result (or im just using wrong code i dont know).

problem = rps.Problem(rectangles=[
    {"width": 30, "height": 60, "rotatable": True},
    {"width": 30, "height": 50, "rotatable": True}
])
solution = rps.Solver().solve(problem=problem, width_limit=60, show_progress=True, seed=1111)
print("solution:", solution)

###
solution: Solution({'sequence_pair': SequencePair(([0, 1], [1, 0])), 'floorplan': Floorplan({'positions': [{'id': 0, 'x': 0, 'y': 50, 'width': 30, 'height': 60}, {'id': 1, 'x': 0, 'y': 0, 'width': 30, 'height': 50}], 'bounding_box': (30, 110), 'area': 3300})})

for the bounding box, it should be this right ?

'bounding_box': (60, 60)

Same Value Of 2 Rectangle = No Results

Im getting nothing from the same rectangles =
(4, 4),
(4, 4)

But its working if im using =
(4, 3),
(4, 4)

import rectangle_packing_solver as rps

# Define a problem
problem = rps.Problem(rectangles=[
    (4, 3),
    (4, 4),
])

print("\n=== Solving without width/height constraints ===")
solution = rps.Solver().solve(problem=problem, show_progress=True)
print("solution:", solution)

Feature Request - Optimization strategy

Hi, thanks for the great piece of code.

Would be very nice to have an option for the solving method target.
At the moment you are minimizing the box area.

For my usecase I have a heigth_limit, and want to minimze the overall box width,
( This is an irrigation system, where height_limit is the pump volume, and box width is the watering time per circuit )
I had to change the solver energy def, but having an option for this would be very handy.

Kind regards
Alfred

Solve in 3D space as well

Hi!

Would it be possible to also calculate and solve the rectangles in 3D? So that the algorithm, besides using x and y, also takes z into consideration. Meaning that the floorplan will be stacking the rectangles on top of eachother if they would fit in z space.

I understand that its quite a hefty change, but I figured you might be up for the challange :)

Thanks in advance already!

Run 20 blocks SA with different results

Hi KOATAROT-san,

I ran example_large.py with the same script.
And trying find the solution with the limit.
for example, height_limit of solver is set 50,
but finally I got a sparse floorplan, rather than a tight design in your example picture (floorplan_large_limit.png).

is there any parameter need to be set for solver in large scale? I try small number of block, and the results looks normal.

hello

Why is the result different every time?