kishorkukreja/awesome-supply-chain/1d-cutting-stock

def first_fit_decreasing(items, stock_length):
    """
    First Fit Decreasing Heuristic for 1D Cutting Stock
    Fast greedy algorithm - good for quick solutions
    Parameters:
    - items: list of (length, quantity, item_id) tuples
    - stock_length: length of standard stock
    Returns: cutting plan with patterns
    Performance: Typically 10-30% above optimal
    Complexity: O(n log n + nk) where k = number of stocks used
    """
    # Expand items by quantity and sort by decreasing length
    pieces = []
    for length, quantity, item_id in items:
        for _ in range(quantity):
            pieces.append((length, item_id))
    pieces.sort(reverse=True, key=lambda x: x[0])
    # Initialize bins (stocks)
    stocks = []
    for piece_length, item_id in pieces:
        # Try to fit in existing stock
        placed = False
        for stock in stocks:
            if stock['remaining'] >= piece_length:
                stock['items'].append({
                    'length': piece_length,
                    'id': item_id
                })
                stock['remaining'] -= piece_length
                placed = True
                break
        # Need new stock
        if not placed:
            new_stock = {
                'items': [{
                    'length': piece_length,
                    'id': item_id
                }],
                'remaining': stock_length - piece_length
            }
            stocks.append(new_stock)
    # Calculate statistics
    total_used = sum(stock_length - s['remaining'] for s in stocks)
    total_available = len(stocks) * stock_length
    utilization = (total_used / total_available * 100) if total_available > 0 else 0
    return {
        'num_stocks': len(stocks),
        'stocks': stocks,
        'utilization': utilization,
        'waste': total_available - total_used
    }
# Example usage
items = [
    (2300, 5, 'A'),  # 5 pieces of 2300mm
    (1500, 8, 'B'),  # 8 pieces of 1500mm
    (1200, 12, 'C'), # 12 pieces of 1200mm
    (800, 6, 'D')    # 6 pieces of 800mm
]
stock_length = 6000
result = first_fit_decreasing(items, stock_length)
print(f"Stocks needed: {result['num_stocks']}")
print(f"Utilization: {result['utilization']:.2f}%")
print(f"Waste: {result['waste']}mm")

def best_fit_decreasing(items, stock_length):
    """
    Best Fit Decreasing Heuristic
    Better than FFD - finds tightest fit to minimize waste
    Parameters:
    - items: list of (length, quantity, item_id) tuples
    - stock_length: length of standard stock
    Returns: cutting plan
    Performance: Typically 5-20% above optimal
    """
    # Expand and sort pieces
    pieces = []
    for length, quantity, item_id in items:
        for _ in range(quantity):
            pieces.append((length, item_id))
    pieces.sort(reverse=True, key=lambda x: x[0])
    stocks = []
    for piece_length, item_id in pieces:
        # Find best fitting stock (minimum remaining space after placement)
        best_stock_idx = None
        min_remaining = float('inf')
        for idx, stock in enumerate(stocks):
            if stock['remaining'] >= piece_length:
                remaining_after = stock['remaining'] - piece_length
                if remaining_after < min_remaining:
                    min_remaining = remaining_after
                    best_stock_idx = idx
        if best_stock_idx is not None:
            # Place in best fitting stock
            stocks[best_stock_idx]['items'].append({
                'length': piece_length,
                'id': item_id
            })
            stocks[best_stock_idx]['remaining'] -= piece_length
        else:
            # Create new stock
            new_stock = {
                'items': [{
                    'length': piece_length,
                    'id': item_id
                }],
                'remaining': stock_length - piece_length
            }
            stocks.append(new_stock)
    # Calculate statistics
    total_used = sum(stock_length - s['remaining'] for s in stocks)
    total_available = len(stocks) * stock_length
    return {
        'num_stocks': len(stocks),
        'stocks': stocks,
        'utilization': (total_used / total_available * 100) if total_available > 0 else 0,
        'waste': total_available - total_used
    }

from pulp import *
import numpy as np
class ColumnGenerationCuttingStock:
    """
    Column Generation for 1D Cutting Stock Problem
    Finds optimal or near-optimal solution using:
    1. Master Problem (LP): Select best patterns
    2. Pricing Problem (Knapsack): Generate new profitable patterns
    This is the state-of-the-art exact method for cutting stock
    """
    def __init__(self, stock_length, items, kerf=0):
        """
        Initialize cutting stock problem
        Parameters:
        - stock_length: length of standard stock
        - items: list of (length, demand, item_id) tuples
        - kerf: material lost per cut (saw blade width)
        """
        self.stock_length = stock_length
        self.items = items
        self.kerf = kerf
        self.n_items = len(items)
        # Extract lengths and demands
        self.lengths = [item[0] for item in items]
        self.demands = [item[1] for item in items]
        self.item_ids = [item[2] for item in items]
        # Storage for patterns
        self.patterns = []
        self.pattern_count = 0
    def generate_initial_patterns(self):
        """
        Generate initial patterns (one item type per pattern)
        Each pattern cuts maximum number of one item type
        """
        initial_patterns = []
        for i in range(self.n_items):
            pattern = [0] * self.n_items
            # Maximum number of item i that fits in one stock
            max_fit = int(self.stock_length / (self.lengths[i] + self.kerf))
            pattern[i] = max_fit
            initial_patterns.append(pattern)
        self.patterns = initial_patterns
        return initial_patterns
    def solve_master_problem(self):
        """
        Solve Master Problem (Restricted)
        Linear Programming Relaxation:
        Minimize Σ x_j
        Subject to: Σ(a_ij × x_j) ≥ d_i for all i
                    x_j ≥ 0
        Returns: solution and dual values
        """
        prob = LpProblem("Cutting_Stock_Master", LpMinimize)
        # Decision variables: x_j = number of times pattern j is used
        num_patterns = len(self.patterns)
        x = [LpVariable(f"x_{j}", lowBound=0, cat='Continuous')
             for j in range(num_patterns)]
        # Objective: minimize total stocks used
        prob += lpSum(x), "Total_Stocks"
        # Constraints: meet demand for each item type
        constraints = []
        for i in range(self.n_items):
            constraint = lpSum(self.patterns[j][i] * x[j]
                             for j in range(num_patterns)) >= self.demands[i]
            prob += constraint, f"Demand_{i}"
            constraints.append(constraint)
        # Solve
        prob.solve(PULP_CBC_CMD(msg=0))
        # Extract solution
        solution = {
            'objective': value(prob.objective),
            'pattern_usage': [x[j].varValue for j in range(num_patterns)],
            'status': LpStatus[prob.status]
        }
        # Extract dual values (shadow prices)
        dual_values = []
        for i in range(self.n_items):
            constraint_name = f"Demand_{i}"
            for name, constraint in prob.constraints.items():
                if constraint_name in name:
                    dual_values.append(constraint.pi)
                    break
        solution['dual_values'] = dual_values
        return solution
    def solve_pricing_problem(self, dual_values):
        """
        Solve Pricing Problem (Knapsack)
        Find new pattern with negative reduced cost:
        max Σ(π_i × a_i)
        subject to: Σ(l_i × a_i) ≤ L
                    a_i ≥ 0, integer
        This is a 0/1 knapsack variant (unbounded knapsack)
        Parameters:
        - dual_values: dual values from master problem (π_i)
        Returns: new pattern if found, None otherwise
        """
        # Solve unbounded knapsack
        # dp[w] = maximum value achievable with weight w
        capacity = self.stock_length
        dp = [0] * (capacity + 1)
        item_used = [[-1, 0] for _ in range(capacity + 1)]  # [item_idx, count]