Steinberg Algorithm for Strip Packing Problem with two heuristics

This project implements the Steinberg algorithm for solving the strip packing problem in Python. (see A. Steinberg, 1997) We also provide two heuristics: ''removing gaps'' and ''dropping hanging rectangles''. See documentation and examples.

Installation

Clone the repository and install the dependencies:

git clone https://github.com/yzdxdydz/strip-packing.git
cd strip-packing
pip install -r requirements.txt

Usage

To execute the packing algorithm, follow these steps:

Import the SteinbergPacking class from the src/steinberg module.

from src.steinberg import SteinbergPacking

Create an instance of the SteinbergPacking class with the desired parameters. For example for original algorithm.

sp = SteinbergPacking(width=10, without_gaps=False, drop_hanging_element=False)

Call the get_packing method, passing in the list of elements to be packed.

elements = [[1, 1], [1, 1], [10, 8], [3, 1], [9, 1], [2, 1], [1, 1], [3, 1]]
#Optimal height H_opt = 10 can be provided with the packing 
# [9, 9], [8, 9], [0, 0], [5, 9], [0, 8], [3, 9], [9, 8], [0, 9].  
sp.get_packing(elements)

Calculate the height, plot the packing and save it to file.

from random import randint
colors = []
for _ in elements:
    colors.append('#%06X' % randint(0, 0xFFFFFF))
sp.plot_packing(colors, "figure-1.png")
print("Height: ", sp.max_height())

Then Steinberg algorithm provides height H_1=18.25. The plot is
For ''Removing gaps'' algorithm,

sp = SteinbergPacking(width=10, without_gaps=True, drop_hanging_element=False)
sp.get_packing(elements)
sp.plot_packing(colors, "figure-2.png")
print("Height: ", sp.max_height())

''Removing gaps'' algorithm provides height H_2=13.0.
To ''Drop hanging elements'',

sp = SteinbergPacking(width=10, without_gaps=True, drop_hanging_element=True)
sp.get_packing(elements)
sp.plot_packing(colors, "figure-3.png")
print("Height: ", sp.max_height())

''Drop hanging elements'' algorithm provides height H_3=12.0.

Documentation

For detailed information on the algorithm, please refer to the documentation strip-packing.pdf