majiayu000 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:
Strip Specifications
- Strip width? (fixed dimension)
- Maximum height allowed? (or unlimited)
- Strip material and cost structure?
- Single strip or multiple strips?
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?
Packing Constraints
- Guillotine cuts only? (straight cuts across strip)
- Free-form packing allowed?
- Minimum spacing between items?
- Items must be axis-aligned?
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:
Within strip bounds:
- 0 ≤ x_i ≤ W - width_i for all i
- 0 ≤ y_i for all i
No overlap:
- For all pairs (i, j): items don't overlap
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': height
}]
}
else:
# Add to current shelf
x = strip_width - current_shelf['remaining_width']
current_shelf['items'].append({
'id': item_id,
'x': x,
'y': current_shelf['y'],
'width': width,
'height': height
})
current_shelf['remaining_width'] -= width
# Add last shelf
if current_shelf is not None:
shelves.append(current_shelf)
# Calculate total height
total_height = sum(s['height'] for s in shelves)
# Collect all items
packed_items = []
for shelf in shelves:
packed_items.extend(shelf['items'])
return {
'height': total_height,
'width': strip_width,
'shelves': shelves,
'items': packed_items,
'utilization': calculate_utilization(packed_items, strip_width, total_height)
}
def calculate_utilization(items, width, height):
"""Calculate space utilization percentage"""
item_area = sum(item['width'] * item['height'] for item in items)
strip_area = width * height
return (item_area / strip_area * 100) if strip_area > 0 else 0
# Example
items = [
(20, 30, 'A'), (15, 25, 'B'), (25, 35, 'C'),
(18, 28, 'D'), (22, 30, 'E'), (12, 20, 'F')
]
strip_width = 50
result = next_fit_decreasing_height(items, strip_width)
print(f"Strip height: {result['height']}")
print(f"Utilization: {result['utilization']:.1f}%")
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': y_position,
'height': height,
'remaining_width': strip_width - width,
'items': [{
'id': item_id,
'x': 0,
'y': y_position,
'width': width,
'height': height
}]
}
shelves.append(new_shelf)
total_height = sum(s['height'] for s in shelves)
packed_items = []
for shelf in shelves:
packed_items.extend(shelf['items'])
return {
'height': total_height,
'width': strip_width,
'shelves': shelves,
'items': packed_items,
'utilization': 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
else:
# Create new shelf
y_position = sum(s['height'] for s in shelves)
new_shelf = {
'y': y_position,
'height': height,
'remaining_width': strip_width - width,
'items': [{
'id': item_id,
'x': 0,
'y': y_position,
'width': width,
'height': height
}]
}
shelves.append(new_shelf)
total_height = sum(s['height'] for s in shelves)
packed_items = []
for shelf in shelves:
packed_items.extend(shelf['items'])
return {
'height': total_height,
'width': strip_width,
'shelves': shelves,
'items': packed_items,
'utilization': 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': x,
'y': y,
'width': w,
'height': h,
'rotated': rotated
})
max_height = max(max_height, y + h)
return {
'height': max_height,
'width': strip_width,
'items': packed_items,
'utilization': calculate_utilization(packed_items, strip_width, max_height)
}
def find_lowest_position(x, width, height, placed_items, strip_width):
"""
Find lowest y-coordinate where item can be placed
Checks for overlaps with existing items
"""
if x + width > strip_width:
return None
y = 0
while True:
# Check for overlap
overlap = False
for item in placed_items:
if rectangles_intersect(
x, y, width, height,
item['x'], item['y'], item['width'], item['height']
):
overlap = True
# Move above this item
y = item['y'] + item['height']
break
if not overlap:
return y
# Safety check (prevent infinite loop)
if y > 10000:
return None
def rectangles_intersect(x1, y1, w1, h1, x2, y2, w2, h2):
"""Check if two rectangles intersect"""
return not (x1 + w1 <= x2 or x2 + w2 <= x1 or
y1 + h1 <= y2 or 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(self, chromosome):
"""Decode chromosome to packing using FFDH"""
ordered_items = []
for idx in chromosome['sequence']:
w, h, item_id = self.items[idx]
if chromosome['orientations'][idx]:
w, h = h, w # Rotate
ordered_items.append((w, h, item_id))
result = first_fit_decreasing_height(ordered_items, self.strip_width)
return result
def fitness(self, chromosome):
"""Fitness = total height (minimize)"""
result = self.decode_chromosome(chromosome)
return result['height']
def crossover(self, parent1, parent2):
"""Order crossover for sequence + uniform for orientations"""
if random.random() > self.crossover_rate:
return parent1.copy(), parent2.copy()
# Crossover sequence (OX)
size = len(parent1['sequence'])
cx1 = random.randint(0, size - 2)
cx2 = random.randint(cx1 + 1, size - 1)
child1_seq = [-1] * size
child2_seq = [-1] * size
child1_seq[cx1:cx2] = parent1['sequence'][cx1:cx2]
child2_seq[cx1:cx2] = parent2['sequence'][cx1:cx2]
self._fill_sequence(child1_seq, parent2['sequence'], cx2)
self._fill_sequence(child2_seq, parent1['sequence'], cx2)
# Crossover orientations (uniform)
child1_orient = []
child2_orient = []
for i in range(size):
if random.random() < 0.5:
child1_orient.append(parent1['orientations'][i])
child2_orient.append(parent2['orientations'][i])
else:
child1_orient.append(parent2['orientations'][i])
child2_orient.append(parent1['orientations'][i])
return (
{'sequence': child1_seq, 'orientations': child1_orient},
{'sequence': child2_seq, 'orientations': child2_orient}
)
def _fill_sequence(self, child, parent, start_pos):
"""Fill offspring sequence"""
child_set = set([x for x in child if x != -1])
pos = start_pos
for item in parent[start_pos:] + parent[:start_pos]:
if item not in child_set:
while child[pos % len(child)] != -1:
pos += 1
child[pos % len(child)] = item
child_set.add(item)
def mutate(self, chromosome):
"""Swap mutation + bit flip"""
# Swap in sequence
if random.random() < self.mutation_rate:
i, j = random.sample(range(self.n_items), 2)
chromosome['sequence'][i], chromosome['sequence'][j] = \
chromosome['sequence'][j], chromosome['sequence'][i]
# Flip orientations
for i in range(self.n_items):
if random.random() < self.mutation_rate / 2:
chromosome['orientations'][i] = not chromosome['orientations'][i]
return chromosome
def tournament_selection(self, population, fitnesses, tournament_size=3):
"""Tournament selection"""
indices = random.sample(range(len(population)), tournament_size)
fits = [fitnesses[i] for i in indices]
winner_idx = indices[fits.index(min(fits))]
return population[winner_idx]
def solve(self):
"""Run genetic algorithm"""
population = [self.create_chromosome() for _ in range(self.population_size)]
for generation in range(self.generations):
fitnesses = [self.fitness(chrom) for chrom in population]
# Track best
min_idx = fitnesses.index(min(fitnesses))
if fitnesses[min_idx] < self.best_height:
self.best_height = fitnesses[min_idx]
self.best_solution = self.decode_chromosome(population[min_idx])
print(f"Gen {generation}: Best height = {self.best_height:.1f}")
# New population
new_population = [population[min_idx]] # Elitism
while len(new_population) < self.population_size:
parent1 = self.tournament_selection(population, fitnesses)
parent2 = self.tournament_selection(population, fitnesses)
child1, child2 = self.crossover(parent1, parent2)
child1 = self.mutate(child1)
child2 = self.mutate(child2)
new_population.extend([child1, child2])
population = new_population[:self.population_size]
return self.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 == 'ffdh':
self.solution = first_fit_decreasing_height(self.items, self.strip_width)
elif algorithm == 'bfdh':
self.solution = best_fit_decreasing_height(self.items, self.strip_width)
elif algorithm == 'bottom_left':
self.solution = bottom_left_strip_packing(
self.items, self.strip_width, allow_rotation
)
elif algorithm == 'genetic':
ga = GeneticAlgorithmStripPacking(
self.items, self.strip_width,
population_size=kwargs.get('population_size', 50),
generations=kwargs.get('generations', 100)
)
self.solution = ga.solve()
else:
raise ValueError(f"Unknown algorithm: {algorithm}")
return self.solution
def visualize(self, save_path=None):
"""Visualize strip packing solution"""
if self.solution is None:
raise ValueError("No solution to visualize")
fig, ax = plt.subplots(figsize=(10, 12))
# Draw strip boundary
strip_rect = patches.Rectangle(
(0, 0), self.strip_width, self.solution['height'],
linewidth=2, edgecolor='black', facecolor='none'
)
ax.add_patch(strip_rect)
# Draw items
colors = plt.cm.tab20(np.linspace(0, 1, 20))
for idx, item in enumerate(self.solution['items']):
color = colors[idx % 20]
rect = patches.Rectangle(
(item['x'], item['y']),
item['width'], item['height'],
linewidth=1, edgecolor='black',
facecolor=color, alpha=0.7
)
ax.add_patch(rect)
# Add label
cx = item['x'] + item['width'] / 2
cy = item['y'] + item['height'] / 2
ax.text(cx, cy, str(item['id']),
ha='center', va='center',
fontsize=8, fontweight='bold')
ax.set_xlim(-2, self.strip_width + 2)
ax.set_ylim(-2, self.solution['height'] + 2)
ax.set_aspect('equal')
ax.set_xlabel('Width')
ax.set_ylabel('Height')
ax.set_title(f'Strip Packing Solution\n'
f'Width: {self.strip_width} | Height: {self.solution["height"]:.1f} | '
f'Utilization: {self.solution["utilization"]:.1f}%')
ax.grid(True, alpha=0.3)
if save_path:
plt.savefig(save_path, dpi=300, bbox_inches='tight')
plt.show()
def print_solution(self):
"""Print solution summary"""
if self.solution is None:
print("No solution available")
return
print("=" * 70)
print("STRIP PACKING SOLUTION")
print("=" * 70)
print(f"Strip Width: {self.solution['width']}")
print(f"Total Height: {self.solution['height']:.1f}")
print(f"Items Packed: {len(self.solution['items'])}")
print(f"Utilization: {self.solution['utilization']:.1f}%")
print(f"Waste: {100 - self.solution['utilization']:.1f}%")
# Example usage
if __name__ == "__main__":
# Create solver
solver = StripPackingSolver(strip_width=100)
# Add items
items = [
(40, 30), (35, 25), (50, 20), (30, 40),
(25, 35), (45, 30), (20, 25), (35, 35),
(30, 20), (40, 25)
]
for w, h in items:
solver.add_item(w, h)
# Solve using FFDH
print("Solving with FFDH algorithm...")
solution = solver.solve(algorithm='ffdh')
# Print results
solver.print_solution()
# Visualize
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
- What is the strip width?
- How many items need to be packed?
- Can items be rotated?
- Is there a maximum height limit?
- Are guillotine cuts required?
- 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