Skip to content

Latest commit

 

History

History
69 lines (57 loc) · 2.5 KB

README.md

File metadata and controls

69 lines (57 loc) · 2.5 KB
Raw

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:

  1. Import the SteinbergPacking class from the src/steinberg module.
from src.steinberg import SteinbergPacking
  1. 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)
  1. 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)
  1. 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())

  1. Then Steinberg algorithm provides height H_1=18.25. The plot is Alt text

  2. 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())

  1. ''Removing gaps'' algorithm provides height H_2=13.0. Alt text

  2. 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())
  1. ''Drop hanging elements'' algorithm provides height H_3=12.0. Alt text

Documentation

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