2D Cutting Stock Problem

You are an expert in two-dimensional cutting stock problems and rectangular sheet optimization. Your goal is to help minimize material waste and costs when cutting large sheets (steel plates, glass panels, wood boards, fabric, paper) into smaller rectangular pieces to meet customer orders.

Initial Assessment

Before solving 2D cutting stock problems, understand:

Material Characteristics

• What material? (steel plate, glass, wood, fabric, paper)

• Standard sheet dimensions? (e.g., 2440×1220mm, 3000×1500mm)

• Single sheet size or multiple available?

• Sheet cost per piece or per square meter?

• Material grain direction matters?

Item Requirements

• How many different rectangular items needed?

• Dimensions of each item (width × height)?

• Quantity of each item?

• Total list of (width, height, quantity) tuples?

• Can items be rotated 90 degrees?

Cutting Constraints

• Guillotine cuts only? (straight cuts across entire sheet)

• Free-form cutting allowed?

• Maximum number of cutting stages? (2-stage, 3-stage)

• Saw blade kerf (material lost per cut)?

• Minimum trim size?

Optimization Objective

• Minimize number of sheets used?

• Minimize total material cost?

• Minimize trim waste percentage?

• Minimize cutting complexity?

• Balance waste vs. setup time?

Production Constraints

• Any item grouping requirements?

• Maximum items per sheet?

• Cutting machine limitations?

• Time constraints for solution?

2D Cutting Stock Framework

Problem Classification

1. Unconstrained 2D Cutting Stock

• Free-form cutting allowed

• Any cutting pattern acceptable

• Minimize sheets used or waste

• Most flexible but complex

2. Guillotine 2D Cutting Stock

• All cuts must be guillotine (edge-to-edge)

• Simpler cutting process

• May increase waste vs. free-form

• Common in manufacturing

3. Two-Stage Guillotine Cutting

• Stage 1: Cut sheet into strips

• Stage 2: Cut strips into items

• Practical for many cutting machines

• Restricted pattern space

4. Three-Stage Guillotine Cutting

• Stage 1: Cut sheet into sections

• Stage 2: Cut sections into strips

• Stage 3: Cut strips into items

• More flexible than two-stage

5. Non-Guillotine with Limited Cuts

• Allow some non-guillotine cuts

• Minimize number of non-guillotine cuts

• Balance flexibility vs. complexity

Mathematical Formulation

Classical 2D Cutting Stock Problem

Given:

• W, H = sheet width and height

• n = number of item types

• w_i, h_i = width and height of item type i

• d_i = demand for item type i

Pattern Definition: A cutting pattern p is a layout of items on one sheet where:

• Items don't overlap

• Items fit within sheet boundaries

• a_ip = number of items of type i in pattern p

• Can be represented by coordinates: (x, y, w, h, rotation) for each item

Decision Variables:

• x_p = number of times pattern p is used

Objective: Minimize Σ x_p (minimize sheets used)

Or: Minimize Σ (cost_p × x_p) (minimize material cost)

Constraints: Σ (a_ip × x_p) ≥ d_i for all i = 1, ..., n (meet demand) x_p ≥ 0, integer

Complexity:

• Strongly NP-hard

• Pattern generation is itself NP-hard (2D knapsack)

• Requires sophisticated algorithms

Algorithms and Solution Methods

Method 1: Two-Stage Guillotine Cutting - Practical Heuristic

import numpy as np from typing import List, Tuple, Dict

class TwoStageGuillotineCutting: """ Two-Stage Guillotine Cutting for 2D Cutting Stock

Stage 1: Cut sheet horizontally into strips
Stage 2: Cut strips vertically into items

This is a practical approximation that works well for many applications
"""

def __init__(self, sheet_width, sheet_height, kerf=0):
    """
    Initialize solver

    Parameters:
    - sheet_width: width of standard sheet
    - sheet_height: height of standard sheet
    - kerf: material lost per cut
    """
    self.sheet_width = sheet_width
    self.sheet_height = sheet_height
    self.kerf = kerf
    self.items = []

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

    self.items.append({
        'id': item_id,
        'width': width,
        'height': height,
        'quantity': quantity,
        'area': width * height
    })

def generate_strip_patterns(self):
    """
    Generate feasible strip patterns

    A strip pattern: one height, multiple items of possibly different widths

    Returns: list of strip patterns
    """
    strip_patterns = []

    # For each unique height, generate strip patterns
    unique_heights = list(set(item['height'] for item in self.items))

    for strip_height in unique_heights:
        if strip_height > self.sheet_height:
            continue

        # Items that fit this height
        eligible_items = [item for item in self.items
                        if item['height'] <= strip_height]

        # Use 1D cutting stock to pack items into strip width
        patterns = self._generate_1d_patterns_for_strip(
            eligible_items, strip_height, self.sheet_width
        )

        for pattern in patterns:
            strip_patterns.append({
                'height': strip_height,
                'items': pattern,
                'waste_width': self._calculate_strip_waste(pattern)
            })

    return strip_patterns

def _generate_1d_patterns_for_strip(self, eligible_items, strip_height, strip_width):
    """
    Generate 1D patterns for items that fit in a strip

    This is essentially 1D cutting stock in the width dimension
    """
    patterns = []

    # Simple greedy pattern generation
    # In practice, use proper 1D column generation here

    # Pattern 1: Single item type per strip (simple patterns)
    for item in eligible_items:
        if item['height'] == strip_height:
            num_fit = int(strip_width / (item['width'] + self.kerf))
            if num_fit > 0:
                pattern = {item['id']: num_fit}
                patterns.append(pattern)

    # Pattern 2: Multiple item types (mixed patterns)
    # Simplified: try pairs of items
    for i, item1 in enumerate(eligible_items):
        if item1['height'] > strip_height:
            continue

        for item2 in eligible_items[i:]:
            if item2['height'] > strip_height:
                continue

            # Try different combinations
            for n1 in range(int(strip_width / (item1['width'] + self.kerf)) + 1):
                remaining = strip_width - n1 * (item1['width'] + self.kerf)
                n2 = int(remaining / (item2['width'] + self.kerf))

                if n1 + n2 > 0:
                    pattern = {}
                    if n1 > 0:
                        pattern[item1['id']] = n1
                    if n2 > 0:
                        pattern[item2['id']] = n2
                    patterns.append(pattern)

    return patterns

def _calculate_strip_waste(self, pattern):
    """Calculate waste width in a strip pattern"""
    total_width = 0
    for item in self.items:
        if item['id'] in pattern:
            total_width += item['width'] * pattern[item['id']]
    return self.sheet_width - total_width

def solve_column_generation(self):
    """
    Solve 2-stage guillotine cutting using column generation

    This is simplified - full implementation would use proper pricing problem
    """

    from pulp import *

    # Generate initial strip patterns
    strip_patterns = self.generate_strip_patterns()

    # Master problem: select strips to pack into sheets
    prob = LpProblem("Two_Stage_Cutting", LpMinimize)

    # Variables: how many of each strip pattern to use
    n_patterns = len(strip_patterns)
    x = [LpVariable(f"strip_{i}", lowBound=0, cat='Integer')
         for i in range(n_patterns)]

    # Approximate number of sheets as sum of strip heights / sheet height
    # This is a simplification; exact formulation requires bin packing constraint
    prob += lpSum(x[i] * strip_patterns[i]['height'] / self.sheet_height
                 for i in range(n_patterns)), "Sheets"

    # Demand constraints
    for item in self.items:
        item_id = item['id']
        prob += lpSum(x[i] * strip_patterns[i]['items'].get(item_id, 0)
                     for i in range(n_patterns)) >= item['quantity'], f"Demand_{item_id}"

    # Solve
    prob.solve(PULP_CBC_CMD(msg=0))

    # Extract solution
    strip_usage = [x[i].varValue for i in range(n_patterns)]

    # Pack strips into sheets
    sheets = self._pack_strips_into_sheets(strip_patterns, strip_usage)

    return {
        'num_sheets': len(sheets),
        'sheets': sheets,
        'strip_patterns': strip_patterns,
        'strip_usage': strip_usage
    }

def _pack_strips_into_sheets(self, strip_patterns, strip_usage):
    """
    Pack strips into sheets using First Fit Decreasing Height
    """

    # Create list of strips to pack
    strips_to_pack = []
    for i, usage in enumerate(strip_usage):
        if usage and usage > 0.5:
            for _ in range(int(usage)):
                strips_to_pack.append(strip_patterns[i])

    # Sort by decreasing height
    strips_to_pack.sort(key=lambda s: s['height'], reverse=True)

    # Pack into sheets
    sheets = []

    for strip in strips_to_pack:
        # Try to fit in existing sheet
        placed = False

        for sheet in sheets:
            if sheet['remaining_height'] >= strip['height']:
                sheet['strips'].append(strip)
                sheet['remaining_height'] -= strip['height']
                placed = True
                break

        if not placed:
            # Create new sheet
            sheets.append({
                'strips': [strip],
                'remaining_height': self.sheet_height - strip['height']
            })

    # Calculate utilization
    for sheet in sheets:
        used_area = sum(
            (self.sheet_width - s['waste_width']) * s['height']
            for s in sheet['strips']
        )
        sheet['utilization'] = used_area / (self.sheet_width * self.sheet_height) * 100

    return sheets

def solve_simple(self):
    """
    Simple two-stage solution without column generation

    Faster but less optimal
    """

    # Sort items by area (largest first)
    sorted_items = sorted(self.items, key=lambda x: x['area'], reverse=True)

    sheets = []
    remaining_items = {item['id']: item['quantity'] for item in self.items}

    while any(qty > 0 for qty in remaining_items.values()):
        # Create new sheet
        sheet = self._fill_sheet_greedy(remaining_items)
        sheets.append(sheet)

    total_used_area = sum(
        sum(item['width'] * item['height'] * item.get('count', 1)
            for item in sheet['items'])
        for sheet in sheets
    )
    total_sheet_area = len(sheets) * self.sheet_width * self.sheet_height

    return {
        'num_sheets': len(sheets),
        'sheets': sheets,
        'utilization': (total_used_area / total_sheet_area * 100) if total_sheet_area > 0 else 0
    }

def _fill_sheet_greedy(self, remaining_items):
    """Fill one sheet greedily using two-stage approach"""

    sheet = {
        'strips': [],
        'items': [],
        'remaining_height': self.sheet_height
    }

    # Sort items by height (tallest first)
    items_by_height = sorted(
        [(item, remaining_items[item['id']]) for item in self.items
         if remaining_items[item['id']] > 0],
        key=lambda x: x[0]['height'],
        reverse=True
    )

    for item, qty_needed in items_by_height:
        if sheet['remaining_height'] < item['height']:
            continue

        # Create strip for this item
        strip_height = item['height']
        strip_width = self.sheet_width
        num_items_in_strip = int(strip_width / (item['width'] + self.kerf))

        if num_items_in_strip > 0:
            num_items_to_cut = min(num_items_in_strip, qty_needed)

            sheet['strips'].append({
                'height': strip_height,
                'items': [{
                    'id': item['id'],
                    'width': item['width'],
                    'height': item['height'],
                    'count': num_items_to_cut
                }]
            })

            sheet['items'].extend([item] * num_items_to_cut)
            remaining_items[item['id']] -= num_items_to_cut
            sheet['remaining_height'] -= strip_height

    return sheet

Example usage

def example_two_stage_cutting(): """Example: Cutting steel plates"""

solver = TwoStageGuillotineCutting(
    sheet_width=2440,  # mm
    sheet_height=1220,  # mm
    kerf=3  # mm saw kerf
)

# Add items to cut
solver.add_item(800, 600, 10, 'A')
solver.add_item(1000, 500, 8, 'B')
solver.add_item(600, 400, 15, 'C')
solver.add_item(1200, 800, 5, 'D')

# Solve
print("Solving two-stage guillotine cutting...")
solution = solver.solve_simple()

print(f"\nSheets needed: {solution['num_sheets']}")
print(f"Utilization: {solution['utilization']:.2f}%")

for i, sheet in enumerate(solution['sheets']):
    print(f"\nSheet {i+1}:")
    for strip in sheet['strips']:
        print(f"  Strip (h={strip['height']}): {strip['items']}")

return solution

Method 2: Column Generation for 2D Cutting Stock

from pulp import * import itertools

class ColumnGeneration2DCuttingStock: """ Column Generation for 2D Cutting Stock Problem

Uses:
- Master Problem: Select best cutting patterns
- Pricing Problem: Generate new patterns (2D knapsack)

Note: Pricing problem for 2D is NP-hard itself
We use heuristics for pattern generation
"""

def __init__(self, sheet_width, sheet_height, items, kerf=0):
    """
    Initialize solver

    Parameters:
    - sheet_width: sheet width
    - sheet_height: sheet height
    - items: list of {'id', 'width', 'height', 'quantity'}
    - kerf: cutting kerf
    """
    self.sheet_width = sheet_width
    self.sheet_height = sheet_height
    self.items = items
    self.kerf = kerf
    self.n_items = len(items)

    self.patterns = []

def generate_initial_patterns(self):
    """
    Generate initial patterns

    Simple approach: one item type per pattern, maximum quantity that fits
    """
    initial_patterns = []

    for item in self.items:
        # Calculate max items that fit
        max_cols = int(self.sheet_width / (item['width'] + self.kerf))
        max_rows = int(self.sheet_height / (item['height'] + self.kerf))
        max_items = max_cols * max_rows

        if max_items > 0:
            pattern = {
                'items': {item['id']: max_items},
                'layout': self._create_simple_layout(item, max_cols, max_rows)
            }
            initial_patterns.append(pattern)

        # Also try rotated
        if item['width'] != item['height']:
            max_cols_rot = int(self.sheet_width / (item['height'] + self.kerf))
            max_rows_rot = int(self.sheet_height / (item['width'] + self.kerf))
            max_items_rot = max_cols_rot * max_rows_rot

            if max_items_rot > max_items:
                pattern = {
                    'items': {item['id']: max_items_rot},
                    'layout': self._create_simple_layout_rotated(item, max_cols_rot, max_rows_rot)
                }
                initial_patterns.append(pattern)

    self.patterns = initial_patterns
    return initial_patterns

def _create_simple_layout(self, item, cols, rows):
    """Create simple grid layout"""
    layout = []
    for row in range(rows):
        for col in range(cols):
            layout.append({
                'id': item['id'],
                'x': col * (item['width'] + self.kerf),
                'y': row * (item['height'] + self.kerf),
                'width': item['width'],
                'height': item['height'],
                'rotated': False
            })
    return layout

def _create_simple_layout_rotated(self, item, cols, rows):
    """Create simple grid layout with rotation"""
    layout = []
    for row in range(rows):
        for col in range(cols):
            layout.append({
                'id': item['id'],
                'x': col * (item['height'] + self.kerf),
                'y': row * (item['width'] + self.kerf),
                'width': item['height'],  # Swapped
                'height': item['width'],  # Swapped
                'rotated': True
            })
    return layout

def solve_master_problem(self):
    """
    Solve Master Problem (LP Relaxation)

    min Σ x_p
    s.t. Σ a_ip * x_p >= d_i  ∀i
         x_p >= 0
    """

    prob = LpProblem("2D_Cutting_Master", LpMinimize)

    n_patterns = len(self.patterns)
    x = [LpVariable(f"x_{p}", lowBound=0, cat='Continuous')
         for p in range(n_patterns)]

    # Objective: minimize sheets
    prob += lpSum(x), "Total_Sheets"

    # Demand constraints
    for item in self.items:
        item_id = item['id']
        prob += lpSum(
            self.patterns[p]['items'].get(item_id, 0) * x[p]
            for p in range(n_patterns)
        ) >= item['quantity'], f"Demand_{item_id}"

    # Solve
    prob.solve(PULP_CBC_CMD(msg=0))

    # Extract dual values
    dual_values = {}
    for item in self.items:
        constraint_name = f"Demand_{item['id']}"
        for name, constraint in prob.constraints.items():
            if constraint_name in name:
                dual_values[item['id']] = constraint.pi
                break

    return {
        'objective': value(prob.objective),
        'pattern_usage': [x[p].varValue for p in range(n_patterns)],
        'dual_values': dual_values,
        'status': LpStatus[prob.status]
    }

def solve_pricing_problem(self, dual_values):
    """
    Solve Pricing Problem: Find pattern with negative reduced cost

    This is a 2D knapsack problem - NP-hard
    We use heuristic pattern generation

    max Σ π_i * a_i
    s.t. items fit in sheet without overlap
    """

    # Use greedy heuristic to generate pattern
    # Try several heuristics and pick best

    best_pattern = None
    best_value = 0

    # Heuristic 1: Greedy by value density
    pattern1 = self._generate_pattern_greedy_value(dual_values)
    value1 = self._calculate_pattern_value(pattern1, dual_values)

    if value1 > best_value:
        best_value = value1
        best_pattern = pattern1

    # Heuristic 2: First Fit Decreasing
    pattern2 = self._generate_pattern_ffd(dual_values)
    value2 = self._calculate_pattern_value(pattern2, dual_values)

    if value2 > best_value:
        best_value = value2
        best_pattern = pattern2

    # Check reduced cost
    reduced_cost = 1 - best_value

    if reduced_cost >= -1e-6:
        return None  # No profitable pattern

    return best_pattern

def _generate_pattern_greedy_value(self, dual_values):
    """Generate pattern greedily by value density"""

    # Calculate value per area for each item
    items_with_value = []
    for item in self.items:
        value_density = dual_values.get(item['id'], 0) / (item['width'] * item['height'])
        items_with_value.append((value_density, item))

    items_with_value.sort(reverse=True)

    # Greedy placement
    placed_items = []
    occupied = np.zeros((self.sheet_height, self.sheet_width), dtype=bool)

    for _, item in items_with_value:
        # Try to place as many as possible
        for rotation in [False, True]:
            w = item['width'] if not rotation else item['height']
            h = item['height'] if not rotation else item['width']

            # Find positions where item fits
            for y in range(0, self.sheet_height - h + 1, max(1, h // 10)):
                for x in range(0, self.sheet_width - w + 1, max(1, w // 10)):
                    if not occupied[y:y+h, x:x+w].any():
                        # Place item
                        placed_items.append({
                            'id': item['id'],
                            'x': x,
                            'y': y,
                            'width': w,
                            'height': h,
                            'rotated': rotation
                        })
                        occupied[y:y+h, x:x+w] = True

    # Convert to pattern format
    pattern = {'items': {}, 'layout': placed_items}
    for placed in placed_items:
        item_id = placed['id']
        pattern['items'][item_id] = pattern['items'].get(item_id, 0) + 1

    return pattern

def _generate_pattern_ffd(self, dual_values):
    """Generate pattern using First Fit Decreasing"""

    # Sort items by value (dual value)
    items_sorted = sorted(
        self.items,
        key=lambda x: dual_values.get(x['id'], 0),
        reverse=True
    )

    # Use shelf-based packing
    shelves = []
    placed_items = []

    for item in items_sorted:
        # Try both orientations
        for rotation in [False, True]:
            w = item['width'] if not rotation else item['height']
            h = item['height'] if not rotation else item['width']

            # Try to fit on existing shelf
            placed = False
            for shelf in shelves:
                if shelf['remaining_width'] >= w and shelf['height'] >= h:
                    # Place on shelf
                    x = self.sheet_width - shelf['remaining_width']
                    y = shelf['y']

                    placed_items.append({
                        'id': item['id'],
                        'x': x,
                        'y': y,
                        'width': w,
                        'height': h,
                        'rotated': rotation
                    })

                    shelf['remaining_width'] -= w
                    placed = True
                    break

            if placed:
                break

            # Try new shelf
            current_height = sum(s['height'] for s in shelves)
            if not placed and current_height + h <= self.sheet_height:
                shelves.append({
                    'y': current_height,
                    'height': h,
                    'remaining_width': self.sheet_width - w
                })

                placed_items.append({
                    'id': item['id'],
                    'x': 0,
                    'y': current_height,
                    'width': w,
                    'height': h,
                    'rotated': rotation
                })
                break

    # Convert to pattern
    pattern = {'items': {}, 'layout': placed_items}
    for placed in placed_items:
        item_id = placed['id']
        pattern['items'][item_id] = pattern['items'].get(item_id, 0) + 1

    return pattern

def _calculate_pattern_value(self, pattern, dual_values):
    """Calculate total value of pattern"""
    total_value = 0
    for item_id, count in pattern['items'].items():
        total_value += dual_values.get(item_id, 0) * count
    return total_value

def solve(self, max_iterations=50):
    """
    Solve 2D cutting stock using column generation

    Returns: solution with patterns and usage
    """

    print("Starting 2D Column Generation...")

    # Generate initial patterns
    self.generate_initial_patterns()
    print(f"Initial patterns: {len(self.patterns)}")

    for iteration in range(max_iterations):
        # Solve master problem
        master_sol = self.solve_master_problem()

        print(f"Iteration {iteration+1}: LP Obj = {master_sol['objective']:.2f}")

        # Solve pricing problem
        new_pattern = self.solve_pricing_problem(master_sol['dual_values'])

        if new_pattern is None:
            print("No profitable pattern found. Optimal.")
            break

        # Add pattern
        self.patterns.append(new_pattern)
        print(f"  Added pattern with {sum(new_pattern['items'].values())} items")

    # Solve as IP
    print("\nSolving integer program...")
    final_solution = self.solve_master_ip()

    return final_solution

def solve_master_ip(self):
    """Solve master problem as integer program"""

    prob = LpProblem("2D_Cutting_IP", LpMinimize)

    n_patterns = len(self.patterns)
    x = [LpVariable(f"x_{p}", lowBound=0, cat='Integer')
         for p in range(n_patterns)]

    prob += lpSum(x), "Total_Sheets"

    for item in self.items:
        item_id = item['id']
        prob += lpSum(
            self.patterns[p]['items'].get(item_id, 0) * x[p]
            for p in range(n_patterns)
        ) >= item['quantity'], f"Demand_{item_id}"

    prob.solve(PULP_CBC_CMD(msg=0))

    # Build solution
    pattern_usage = [x[p].varValue for p in range(n_patterns)]

    sheets = []
    for p, usage in enumerate(pattern_usage):
        if usage and usage > 0.5:
            for _ in range(int(usage)):
                sheets.append({
                    'pattern_id': p,
                    'pattern': self.patterns[p],
                    'layout': self.patterns[p]['layout']
                })

    # Calculate utilization
    sheet_area = self.sheet_width * self.sheet_height
    total_used = 0
    for sheet in sheets:
        for placed in sheet['layout']:
            total_used += placed['width'] * placed['height']

    utilization = (total_used / (len(sheets) * sheet_area) * 100) if sheets else 0

    return {
        'num_sheets': len(sheets),
        'sheets': sheets,
        'utilization': utilization,
        'total_waste': len(sheets) * sheet_area - total_used
    }

Example usage

def example_2d_column_generation(): """Example: 2D cutting stock with column generation"""

items = [
    {'id': 'A', 'width': 800, 'height': 600, 'quantity': 10},
    {'id': 'B', 'width': 1000, 'height': 500, 'quantity': 8},
    {'id': 'C', 'width': 600, 'height': 400, 'quantity': 15},
    {'id': 'D', 'width': 1200, 'height': 800, 'quantity': 5}
]

solver = ColumnGeneration2DCuttingStock(
    sheet_width=2440,
    sheet_height=1220,
    items=items,
    kerf=3
)

solution = solver.solve()

print(f"\n{'='*70}")
print(f"SOLUTION")
print(f"{'='*70}")
print(f"Sheets needed: {solution['num_sheets']}")
print(f"Utilization: {solution['utilization']:.2f}%")
print(f"Total waste: {solution['total_waste']}")

return solution

Method 3: Guillotine Cutting with Pattern Generation

class GuillotineCuttingPattern: """ Generate guillotine cutting patterns

All cuts must be straight edge-to-edge
"""

def __init__(self, sheet_width, sheet_height):
    self.sheet_width = sheet_width
    self.sheet_height = sheet_height

def generate_guillotine_patterns(self, items, max_patterns=100):
    """
    Generate feasible guillotine cutting patterns

    Uses recursive subdivision
    """

    patterns = []

    # Try different first-cut positions and orientations
    for first_cut_horizontal in [True, False]:
        if first_cut_horizontal:
            # Horizontal first cut
            for cut_pos in range(100, self.sheet_height, 100):
                pattern = self._recursive_guillotine(
                    0, 0, self.sheet_width, self.sheet_height,
                    items, cut_pos, True
                )
                if pattern:
                    patterns.append(pattern)

        else:
            # Vertical first cut
            for cut_pos in range(100, self.sheet_width, 100):
                pattern = self._recursive_guillotine(
                    0, 0, self.sheet_width, self.sheet_height,
                    items, cut_pos, False
                )
                if pattern:
                    patterns.append(pattern)

        if len(patterns) >= max_patterns:
            break

    return patterns

def _recursive_guillotine(self, x, y, width, height, items, cut_pos, horizontal):
    """
    Recursively generate guillotine pattern

    Parameters:
    - x, y: position of current rectangle
    - width, height: size of current rectangle
    - items: items to pack
    - cut_pos: position of guillotine cut
    - horizontal: True if horizontal cut, False if vertical
    """

    # Base case: try to fit single item type
    pattern = {'items': {}, 'layout': []}

    for item in items:
        # Try both orientations
        for rotated in [False, True]:
            w = item['width'] if not rotated else item['height']
            h = item['height'] if not rotated else item['width']

            # How many fit?
            cols = int(width / w)
            rows = int(height / h)
            count = cols * rows

            if count > 0:
                # Create pattern with this item
                for row in range(rows):
                    for col in range(cols):
                        pattern['layout'].append({
                            'id': item['id'],
                            'x': x + col * w,
                            'y': y + row * h,
                            'width': w,
                            'height': h,
                            'rotated': rotated
                        })
                pattern['items'][item['id']] = count
                return pattern

    return None

Complete 2D Cutting Stock Solver

import matplotlib.pyplot as plt import matplotlib.patches as patches import numpy as np

class TwoDCuttingStockSolver: """ Comprehensive 2D Cutting Stock Solver

Supports:
- Two-stage guillotine cutting
- Column generation
- Visualization
- Export to cutting lists
"""

def __init__(self, sheet_width, sheet_height, kerf=0):
    """
    Initialize solver

    Parameters:
    - sheet_width: standard sheet width
    - sheet_height: standard sheet height
    - kerf: saw blade kerf (material lost per cut)
    """
    self.sheet_width = sheet_width
    self.sheet_height = sheet_height
    self.kerf = kerf
    self.items = []
    self.solution = None

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

    self.items.append({
        'id': item_id,
        'width': width,
        'height': height,
        'quantity': quantity
    })

def solve(self, method='two_stage'):
    """
    Solve 2D cutting stock problem

    Methods:
    - 'two_stage': Two-stage guillotine (fast, practical)
    - 'column_generation': Column generation (better, slower)

    Returns: solution
    """

    if method == 'two_stage':
        solver = TwoStageGuillotineCutting(
            self.sheet_width, self.sheet_height, self.kerf
        )
        for item in self.items:
            solver.add_item(item['width'], item['height'],
                          item['quantity'], item['id'])
        self.solution = solver.solve_simple()
        self.solution['method'] = 'Two-Stage Guillotine'

    elif method == 'column_generation':
        solver = ColumnGeneration2DCuttingStock(
            self.sheet_width, self.sheet_height, self.items, self.kerf
        )
        self.solution = solver.solve()
        self.solution['method'] = 'Column Generation'

    return self.solution

def visualize(self, sheet_index=0, save_path=None):
    """
    Visualize cutting pattern for a specific sheet

    Parameters:
    - sheet_index: index of sheet to visualize
    - save_path: path to save figure
    """

    if self.solution is None:
        raise ValueError("No solution. Run solve() first.")

    if sheet_index >= len(self.solution['sheets']):
        raise ValueError(f"Sheet index {sheet_index} out of range")

    sheet = self.solution['sheets'][sheet_index]

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

    # Draw sheet boundary
    ax.add_patch(patches.Rectangle(
        (0, 0), self.sheet_width, self.sheet_height,
        fill=False, edgecolor='black', linewidth=3
    ))

    # Get layout
    if 'layout' in sheet:
        layout = sheet['layout']
    else:
        # Reconstruct from strips
        layout = []
        y_pos = 0
        for strip in sheet.get('strips', []):
            for item in strip.get('items', []):
                for i in range(item.get('count', 1)):
                    layout.append({
                        'id': item['id'],
                        'x': i * item['width'],
                        'y': y_pos,
                        'width': item['width'],
                        'height': item['height']
                    })
            y_pos += strip['height']

    # Draw items
    colors = plt.cm.tab20(np.linspace(0, 1, 20))

    for item in layout:
        color = colors[hash(item['id']) % 20]

        rect = patches.Rectangle(
            (item['x'], item['y']),
            item['width'], item['height'],
            facecolor=color, edgecolor='black',
            linewidth=1, alpha=0.7
        )
        ax.add_patch(rect)

        # Label
        cx = item['x'] + item['width'] / 2
        cy = item['y'] + item['height'] / 2
        ax.text(cx, cy, f"{item['id']}\n{item['width']}×{item['height']}",
               ha='center', va='center',
               fontsize=9, fontweight='bold',
               bbox=dict(boxstyle='round', facecolor='white', alpha=0.8))

    ax.set_xlim(0, self.sheet_width)
    ax.set_ylim(0, self.sheet_height)
    ax.set_aspect('equal')
    ax.set_xlabel('Width (mm)', fontsize=12)
    ax.set_ylabel('Height (mm)', fontsize=12)
    ax.set_title(
        f'2D Cutting Pattern - Sheet {sheet_index + 1}\n'
        f'Sheet: {self.sheet_width}×{self.sheet_height}mm',
        fontsize=14, fontweight='bold'
    )
    ax.grid(True, alpha=0.3)

    plt.tight_layout()

    if save_path:
        plt.savefig(save_path, dpi=300, bbox_inches='tight')

    plt.show()

def print_solution(self):
    """Print solution summary"""

    if not self.solution:
        print("No solution available.")
        return

    print("=" * 80)
    print("2D CUTTING STOCK SOLUTION")
    print("=" * 80)
    print(f"Method: {self.solution.get('method', 'Unknown')}")
    print(f"Sheet size: {self.sheet_width} × {self.sheet_height}")
    print(f"Sheets used: {self.solution['num_sheets']}")
    print(f"Utilization: {self.solution.get('utilization', 0):.2f}%")
    print()

    print("Items to cut:")
    for item in self.items:
        print(f"  {item['id']}: {item['quantity']} pcs @ {item['width']}×{item['height']}")

Example usage

if name == "main":

print("Example: Steel Plate Cutting")
print("=" * 80)

solver = TwoDCuttingStockSolver(
    sheet_width=2440,
    sheet_height=1220,
    kerf=3
)

solver.add_item(800, 600, 10, 'A')
solver.add_item(1000, 500, 8, 'B')
solver.add_item(600, 400, 15, 'C')
solver.add_item(1200, 800, 5, 'D')

# Solve
solution = solver.solve(method='two_stage')
solver.print_solution()

# Visualize first sheet
solver.visualize(sheet_index=0)

Tools & Libraries

Python Libraries

• PuLP: Linear programming for column generation

• OR-Tools: Google's optimization toolkit

• py2d-pack: 2D packing algorithms

• rectpack: Rectangle packing library

Commercial Software

• CutLogic 2D: Professional 2D cutting optimizer

• Cutting Optimization Pro: Glass and metal cutting

• OptiCut: Sheet cutting optimization

• MaxCut: Industrial cutting stock

Common Challenges & Solutions

Challenge: Guillotine Constraint Too Restrictive

Solution: Use three-stage cutting or limited non-guillotine cuts

Challenge: Many Small Items

Solution: Pre-clustering and hierarchical optimization

Challenge: Mixed Materials

Solution: Multi-objective optimization balancing cost and waste

Output Format

Solution Summary:

• Sheets used: 8

• Utilization: 87.3%

• Method: Two-Stage Guillotine

Pattern Details: See cutting diagrams

Questions to Ask

• What material? (steel, glass, wood, fabric)

• Standard sheet size?

• Items list with dimensions and quantities?

• Guillotine cuts only?

• Can items rotate?

• Saw kerf width?

• Optimization goal?

Related Skills

• 1d-cutting-stock: For 1D cutting problems

• guillotine-cutting: For guillotine-specific algorithms

• nesting-optimization: For irregular shapes

• trim-loss-minimization: For general trim loss

• 2d-bin-packing: For bin packing variants