strip-packing

name	strip-packing
description	When the user wants to solve strip packing problems, pack items into fixed-width strips, or minimize packing height. Also use when the user mentions "strip packing," "cutting stock with fixed width," "ribbon packing," "shelf packing," "minimize height packing," or "2D strip packing problem." For general 2D packing, see 2d-bin-packing. For 3D packing, see 3d-bin-packing.

Strip Packing

You are an expert in strip packing optimization. Your goal is to help pack rectangular items into a strip of fixed width while minimizing the total height used, which is common in manufacturing, printing, fabric cutting, and material utilization problems.

Initial Assessment

Before solving strip packing problems, understand:

1. Strip Specifications

   • Strip width? (fixed dimension)
   • Maximum height allowed? (or unlimited)
   • Strip material and cost structure?
   • Single strip or multiple strips?

2. Items to Pack

   • How many rectangles to pack?
   • Item dimensions (width x height)?
   • Can items be rotated 90 degrees?
   • All items must be packed?
   • Item priorities or packing sequence?

3. Packing Constraints

   • Guillotine cuts only? (straight cuts across strip)
   • Free-form packing allowed?
   • Minimum spacing between items?
   • Items must be axis-aligned?

4. Optimization Goal

   • Minimize total height (most common)?
   • Minimize waste percentage?
   • Minimize number of strips used?
   • Balance between height and cutting complexity?

---

Strip Packing Framework

Problem Definition

Strip Packing Problem (SPP)

• Given: Rectangle items and strip of fixed width W
• Find: Arrangement minimizing total height H
• Constraints: No overlapping, items within strip bounds
• Orientation: Items can typically be rotated 90°

Key Difference from Bin Packing:

• Bin packing: minimize number of bins (both dimensions fixed)
• Strip packing: minimize height (width fixed, height variable)

Problem Variants

1. Guillotine Strip Packing

• All cuts must be guillotine cuts
• Simplifies cutting process
• May sacrifice some efficiency
• Common in manufacturing

2. Non-Guillotine Strip Packing

• Free-form packing allowed
• Better space utilization
• More complex cutting patterns
• May require CNC equipment

3. Multiple Strip Packing

• Use minimum number of strips
• Each strip has fixed width and max height
• Hybrid between strip packing and bin packing

4. Online Strip Packing

• Items arrive sequentially
• Pack without knowing future items
• Cannot rearrange previously placed items
• Real-time manufacturing scenarios

---

Mathematical Formulation

Basic Strip Packing Model

Decision Variables:

• x_i = x-coordinate of item i's bottom-left corner
• y_i = y-coordinate of item i's bottom-left corner
• r_i ∈ {0, 1} = rotation of item i (0=original, 1=rotated 90°)
• H = total height of packing

Objective: Minimize H

Constraints:

1. Within strip bounds:

   • 0 ≤ x_i ≤ W - width_i for all i
   • 0 ≤ y_i for all i

2. No overlap:

   • For all pairs (i, j): items don't overlap

3. Height constraint:

   • y_i + height_i ≤ H for all i

Complexity:

• NP-hard problem
• Harder than 2D bin packing
• No polynomial-time optimal algorithm

---

Algorithms and Solution Methods

Shelf-Based Algorithms

Next Fit Decreasing Height (NFDH)

def next_fit_decreasing_height(items, strip_width):
    """
    Next Fit Decreasing Height Algorithm

    Simple shelf-based approach:
    1. Sort items by decreasing height
    2. Pack items left-to-right on shelves
    3. Start new shelf when item doesn't fit width

    Parameters:
    - items: list of (width, height, item_id) tuples
    - strip_width: fixed width of strip

    Returns: packing with minimized height
    """

    # Sort by decreasing height
    sorted_items = sorted(items, key=lambda x: x[1], reverse=True)

    shelves = []
    current_shelf = None

    for width, height, item_id in sorted_items:
        # Check if item fits on current shelf
        if current_shelf is None or current_shelf['remaining_width'] < width:
            # Start new shelf
            if current_shelf is not None:
                shelves.append(current_shelf)

            current_shelf = {
                'y': sum(s['height'] for s in shelves),
                'height': height,
                'remaining_width': strip_width - width,
                'items': [{
                    'id': item_id,
                    'x': 0,
                    'y': sum(s['height'] for s in shelves),
                    'width': width,
                    : height
                }]
            }
        :
            
            x = strip_width - current_shelf[]
            current_shelf[].append({
                : item_id,
                : x,
                : current_shelf[],
                : width,
                : height
            })
            current_shelf[] -= width

    
     current_shelf   :
        shelves.append(current_shelf)

    
    total_height = (s[]  s  shelves)

    
    packed_items = []
     shelf  shelves:
        packed_items.extend(shelf[])

     {
        : total_height,
        : strip_width,
        : shelves,
        : packed_items,
        : calculate_utilization(packed_items, strip_width, total_height)
    }

 ():
    
    item_area = (item[] * item[]  item  items)
    strip_area = width * height
     (item_area / strip_area * )  strip_area >   


items = [
    (, , ), (, , ), (, , ),
    (, , ), (, , ), (, , )
]
strip_width = 

result = next_fit_decreasing_height(items, strip_width)
()
()

First Fit Decreasing Height (FFDH)

def first_fit_decreasing_height(items, strip_width):
    """
    First Fit Decreasing Height Algorithm

    More efficient than NFDH:
    - Tries to place each item on the first shelf that fits
    - Creates new shelf only if no existing shelf works
    - Better utilization than NFDH

    Parameters:
    - items: list of (width, height, item_id) tuples
    - strip_width: fixed width of strip

    Returns: optimized packing solution
    """

    sorted_items = sorted(items, key=lambda x: (x[1], x[0]), reverse=True)
    shelves = []

    for width, height, item_id in sorted_items:
        placed = False

        # Try to place on existing shelves
        for shelf in shelves:
            if (shelf['remaining_width'] >= width and
                shelf['height'] >= height):
                # Place on this shelf
                x = strip_width - shelf['remaining_width']
                shelf['items'].append({
                    'id': item_id,
                    'x': x,
                    'y': shelf['y'],
                    'width': width,
                    'height': height
                })
                shelf['remaining_width'] -= width
                placed = True
                break

        # Create new shelf if not placed
        if not placed:
            y_position = sum(s['height'] for s in shelves)
            new_shelf = {
                : y_position,
                : height,
                : strip_width - width,
                : [{
                    : item_id,
                    : ,
                    : y_position,
                    : width,
                    : height
                }]
            }
            shelves.append(new_shelf)

    total_height = (s[]  s  shelves)
    packed_items = []
     shelf  shelves:
        packed_items.extend(shelf[])

     {
        : total_height,
        : strip_width,
        : shelves,
        : packed_items,
        : calculate_utilization(packed_items, strip_width, total_height)
    }

Best Fit Decreasing Height (BFDH)

def best_fit_decreasing_height(items, strip_width):
    """
    Best Fit Decreasing Height Algorithm

    Finds the shelf with minimum wasted space
    - Tries to minimize gaps
    - Better utilization than FFDH
    - More computation time

    Parameters:
    - items: list of (width, height, item_id) tuples
    - strip_width: fixed width of strip

    Returns: optimized packing
    """

    sorted_items = sorted(items, key=lambda x: (x[1], x[0]), reverse=True)
    shelves = []

    for width, height, item_id in sorted_items:
        best_shelf = None
        min_waste = float('inf')

        # Find shelf with minimum waste
        for idx, shelf in enumerate(shelves):
            if (shelf['remaining_width'] >= width and
                shelf['height'] >= height):
                waste = shelf['remaining_width'] - width
                if waste < min_waste:
                    min_waste = waste
                    best_shelf = idx

        if best_shelf is not None:
            # Place on best shelf
            shelf = shelves[best_shelf]
            x = strip_width - shelf['remaining_width']
            shelf['items'].append({
                'id': item_id,
                'x': x,
                'y': shelf['y'],
                'width': width,
                'height': height
            })
            shelf['remaining_width'] -= width
        :
            
            y_position = (s[]  s  shelves)
            new_shelf = {
                : y_position,
                : height,
                : strip_width - width,
                : [{
                    : item_id,
                    : ,
                    : y_position,
                    : width,
                    : height
                }]
            }
            shelves.append(new_shelf)

    total_height = (s[]  s  shelves)
    packed_items = []
     shelf  shelves:
        packed_items.extend(shelf[])

     {
        : total_height,
        : strip_width,
        : shelves,
        : packed_items,
        : calculate_utilization(packed_items, strip_width, total_height)
    }

Bottom-Left Algorithm

def bottom_left_strip_packing(items, strip_width, allow_rotation=True):
    """
    Bottom-Left Algorithm for Strip Packing

    Places each item at the lowest, leftmost position available
    - No shelf constraint
    - More flexible packing
    - Better utilization than shelf algorithms

    Parameters:
    - items: list of (width, height, item_id) tuples
    - strip_width: fixed width
    - allow_rotation: allow 90-degree rotation

    Returns: free-form packing
    """

    # Sort by area (largest first)
    sorted_items = sorted(items,
                         key=lambda x: x[0] * x[1],
                         reverse=True)

    packed_items = []
    max_height = 0

    for width, height, item_id in sorted_items:
        orientations = [(width, height, False)]
        if allow_rotation:
            orientations.append((height, width, True))

        best_position = None
        best_y = float('inf')

        for w, h, rotated in orientations:
            # Try all possible x positions
            for x in range(0, strip_width - w + 1):
                # Find lowest feasible y
                y = find_lowest_position(x, w, h, packed_items, strip_width)

                if y is not None and y < best_y:
                    best_y = y
                    best_position = (x, y, w, h, rotated)

        if best_position:
            x, y, w, h, rotated = best_position
            packed_items.append({
                'id': item_id,
                : x,
                : y,
                : w,
                : h,
                : rotated
            })
            max_height = (max_height, y + h)

     {
        : max_height,
        : strip_width,
        : packed_items,
        : calculate_utilization(packed_items, strip_width, max_height)
    }

 ():
    

     x + width > strip_width:
         

    y = 

     :
        
        overlap = 
         item  placed_items:
             rectangles_intersect(
                x, y, width, height,
                item[], item[], item[], item[]
            ):
                overlap = 
                
                y = item[] + item[]
                

          overlap:
             y

        
         y > :
             

 ():
    
      (x1 + w1 <= x2  x2 + w2 <= x1 
                y1 + h1 <= y2  y2 + h2 <= y1)

Genetic Algorithm for Strip Packing

import random
import numpy as np

class GeneticAlgorithmStripPacking:
    """
    Genetic Algorithm for Strip Packing

    Optimizes packing sequence and orientations
    """

    def __init__(self, items, strip_width,
                 population_size=50, generations=100,
                 mutation_rate=0.15, crossover_rate=0.8):
        self.items = items
        self.strip_width = strip_width
        self.population_size = population_size
        self.generations = generations
        self.mutation_rate = mutation_rate
        self.crossover_rate = crossover_rate

        self.n_items = len(items)
        self.best_solution = None
        self.best_height = float('inf')

    def create_chromosome(self):
        """Create random chromosome: (sequence, orientations)"""
        sequence = list(np.random.permutation(self.n_items))
        orientations = [random.choice([True, False]) for _ in range(self.n_items)]
        return {'sequence': sequence, 'orientations': orientations}

    def decode_chromosome():
        
        ordered_items = []
         idx  chromosome[]:
            w, h, item_id = .items[idx]
             chromosome[][idx]:
                w, h = h, w  
            ordered_items.append((w, h, item_id))

        result = first_fit_decreasing_height(ordered_items, .strip_width)
         result

     ():
        
        result = .decode_chromosome(chromosome)
         result[]

     ():
        
         random.random() > .crossover_rate:
             parent1.copy(), parent2.copy()

        
        size = (parent1[])
        cx1 = random.randint(, size - )
        cx2 = random.randint(cx1 + , size - )

        child1_seq = [-] * size
        child2_seq = [-] * size

        child1_seq[cx1:cx2] = parent1[][cx1:cx2]
        child2_seq[cx1:cx2] = parent2[][cx1:cx2]

        ._fill_sequence(child1_seq, parent2[], cx2)
        ._fill_sequence(child2_seq, parent1[], cx2)

        
        child1_orient = []
        child2_orient = []
         i  (size):
             random.random() < :
                child1_orient.append(parent1[][i])
                child2_orient.append(parent2[][i])
            :
                child1_orient.append(parent2[][i])
                child2_orient.append(parent1[][i])

         (
            {: child1_seq, : child1_orient},
            {: child2_seq, : child2_orient}
        )

     ():
        
        child_set = ([x  x  child  x != -])
        pos = start_pos

         item  parent[start_pos:] + parent[:start_pos]:
             item   child_set:
                 child[pos % (child)] != -:
                    pos += 
                child[pos % (child)] = item
                child_set.add(item)

     ():
        
        
         random.random() < .mutation_rate:
            i, j = random.sample((.n_items), )
            chromosome[][i], chromosome[][j] = \
                chromosome[][j], chromosome[][i]

        
         i  (.n_items):
             random.random() < .mutation_rate / :
                chromosome[][i] =  chromosome[][i]

         chromosome

     ():
        
        indices = random.sample(((population)), tournament_size)
        fits = [fitnesses[i]  i  indices]
        winner_idx = indices[fits.index((fits))]
         population[winner_idx]

     ():
        
        population = [.create_chromosome()  _  (.population_size)]

         generation  (.generations):
            fitnesses = [.fitness(chrom)  chrom  population]

            
            min_idx = fitnesses.index((fitnesses))
             fitnesses[min_idx] < .best_height:
                .best_height = fitnesses[min_idx]
                .best_solution = .decode_chromosome(population[min_idx])
                ()

            
            new_population = [population[min_idx]]  

             (new_population) < .population_size:
                parent1 = .tournament_selection(population, fitnesses)
                parent2 = .tournament_selection(population, fitnesses)

                child1, child2 = .crossover(parent1, parent2)
                child1 = .mutate(child1)
                child2 = .mutate(child2)

                new_population.extend([child1, child2])

            population = new_population[:.population_size]

         .best_solution

Complete Strip Packing Solver

import matplotlib.pyplot as plt
import matplotlib.patches as patches

class StripPackingSolver:
    """
    Comprehensive Strip Packing Solver

    Supports multiple algorithms and visualization
    """

    def __init__(self, strip_width, max_height=None):
        self.strip_width = strip_width
        self.max_height = max_height
        self.items = []
        self.solution = None

    def add_item(self, width, height, item_id=None):
        """Add rectangular item to pack"""
        if item_id is None:
            item_id = f"Item_{len(self.items)}"
        self.items.append((width, height, item_id))

    def solve(self, algorithm='ffdh', allow_rotation=False, **kwargs):
        """
        Solve strip packing problem

        Algorithms:
        - 'nfdh': Next Fit Decreasing Height
        - 'ffdh': First Fit Decreasing Height (default)
        - 'bfdh': Best Fit Decreasing Height
        - 'bottom_left': Bottom-Left algorithm
        - 'genetic': Genetic Algorithm
        """

        if algorithm == 'nfdh':
            self.solution = next_fit_decreasing_height(self.items, self.strip_width)

        elif algorithm == :
            .solution = first_fit_decreasing_height(.items, .strip_width)

         algorithm == :
            .solution = best_fit_decreasing_height(.items, .strip_width)

         algorithm == :
            .solution = bottom_left_strip_packing(
                .items, .strip_width, allow_rotation
            )

         algorithm == :
            ga = GeneticAlgorithmStripPacking(
                .items, .strip_width,
                population_size=kwargs.get(, ),
                generations=kwargs.get(, )
            )
            .solution = ga.solve()

        :
             ValueError()

         .solution

     ():
        

         .solution  :
             ValueError()

        fig, ax = plt.subplots(figsize=(, ))

        
        strip_rect = patches.Rectangle(
            (, ), .strip_width, .solution[],
            linewidth=, edgecolor=, facecolor=
        )
        ax.add_patch(strip_rect)

        
        colors = plt.cm.tab20(np.linspace(, , ))

         idx, item  (.solution[]):
            color = colors[idx % ]

            rect = patches.Rectangle(
                (item[], item[]),
                item[], item[],
                linewidth=, edgecolor=,
                facecolor=color, alpha=
            )
            ax.add_patch(rect)

            
            cx = item[] + item[] / 
            cy = item[] + item[] / 
            ax.text(cx, cy, (item[]),
                   ha=, va=,
                   fontsize=, fontweight=)

        ax.set_xlim(-, .strip_width + )
        ax.set_ylim(-, .solution[] + )
        ax.set_aspect()
        ax.set_xlabel()
        ax.set_ylabel()
        ax.set_title(
                    
                    )
        ax.grid(, alpha=)

         save_path:
            plt.savefig(save_path, dpi=, bbox_inches=)

        plt.show()

     ():
        

         .solution  :
            ()
            

        ( * )
        ()
        ( * )
        ()
        ()
        ()
        ()
        ()



 __name__ == :
    
    solver = StripPackingSolver(strip_width=)

    
    items = [
        (, ), (, ), (, ), (, ),
        (, ), (, ), (, ), (, ),
        (, ), (, )
    ]

     w, h  items:
        solver.add_item(w, h)

    
    ()
    solution = solver.solve(algorithm=)

    
    solver.print_solution()

    
    solver.visualize()

---

Common Challenges & Solutions

Challenge: Poor Height Utilization

Problem:

• Large wasted space
• Height much more than necessary
• Gaps between items

Solutions:

• Use BFDH instead of NFDH
• Allow item rotation
• Try bottom-left algorithm for non-shelf packing
• Use genetic algorithm for optimization
• Sort items differently (by area, perimeter)

Challenge: Guillotine Cut Requirement

Problem:

• Manufacturing requires guillotine cuts
• Shelf algorithms don't guarantee guillotine
• Need to modify patterns

Solutions:

• Use explicit guillotine algorithm
• Constrain placement to guillotine-compatible positions
• Generate cutting pattern separately
• Trade some efficiency for guillotine compliance

---

Output Format

Strip Packing Report

Problem:

• Items: 50 rectangles
• Strip Width: 100 cm
• Optimization: Minimize height

Solution:

• Algorithm: FFDH
• Total Height: 185 cm
• Utilization: 87.3%
• Waste: 12.7%

Items Packed:

• Layer 1 (0-30cm): 12 items
• Layer 2 (30-55cm): 10 items
• Layer 3 (55-85cm): 13 items
• Layer 4 (85-120cm): 9 items
• Layer 5 (120-185cm): 6 items

---

Questions to Ask

1. What is the strip width?
2. How many items need to be packed?
3. Can items be rotated?
4. Is there a maximum height limit?
5. Are guillotine cuts required?
6. Is this a one-time problem or recurring?

---

Related Skills

• 2d-bin-packing: For general 2D packing with fixed dimensions
• 1d-cutting-stock: For one-dimensional cutting
• guillotine-cutting: For guillotine-constrained cutting
• trim-loss-minimization: For waste minimization