1d-cutting-stock

一维下料问题

你是一名一维下料问题和线性切割优化专家。你的目标是将标准长度的库存材料（管材、棒材、梁材、纸卷等）切割成较短的材料，以满足客户需求，同时尽量减少材料浪费和成本。

初步评估

在解决一维下料问题之前，请先了解：

1. 问题特征

   • 要切割什么材料？（钢棒、管材、木材、纸张、织物）
   • 可用的标准库存长度是多少？（例如，6m、12m、自定义长度）
   • 有多种库存长度可选，还是只有一种？
   • 每根库存材料或每单位长度的成本是多少？

2. 需求要求

   • 需要多少种不同长度的材料？
   • 每种长度的数量是多少？（几十、几百、几千）
   • 是否有完整的（长度、数量）配对清单？
   • 长度是否有公差要求（允许正负偏差）？

3. 切割约束

   • 最小可用材料长度是多少？
   • 每根库存材料最多可切几刀？
   • 锯缝宽度是多少（每刀锯片厚度／材料损耗）？
   • 不同切割模式是否会产生设置成本？

4. 优化目标

   • 尽量减少使用的库存材料数量？
   • 尽量降低材料总成本？
   • 尽量减少切边废料占比？
   • 尽量提高利用率？

5. 解决方案要求

   • 需要精确的最优解，还是快速近似解？
   • 是实时切割（在线），还是批量规划（离线）？
   • 切割模式可以复杂，还是需要简单易行？

---

一维下料框架

问题分类

1. 经典下料问题（CSP）

• 单一库存长度
• 多种材料长度及其需求量
• 尽量减少使用的库存材料数量
• 尽量减少废料

2. 多种库存长度问题

• 可选不同的库存长度
• 每种长度的成本不同
• 尽量降低总成本（而不只是数量）

3. 余料问题

• 可使用先前切割后剩余的材料
• 优先使用余料，再切割新的库存材料
• 尽量减少材料总消耗量

4. 有设置成本的下料问题

• 每种不同的切割模式都有设置成本
• 尽量减少使用的库存材料数量和模式复杂度
• 在废料与设置成本之间权衡

5. 两阶段切割

• 首先将库存材料切成中间材料
• 然后将中间材料切成最终材料
• 常见于集成生产

---

数学建模

经典下料问题

已知：

• L = 标准库存长度
• n = 材料类型数量
• l_i = 第 i 种材料的长度（i = 1, ..., n）
• d_i = 第 i 种材料的需求量

切割模式定义： 切割模式 j 是一个向量 a_j = (a_1j, a_2j, ..., a_nj)，其中：

• a_ij = 模式 j 切出的第 i 种材料数量
• Σ(l_i × a_ij) ≤ L（模式可行性）

决策变量：

• x_j = 模式 j 的使用次数

目标函数： 最小化 Σ x_j（尽量减少使用的库存材料总数）

约束条件： 对所有 i = 1, ..., n，Σ(a_ij × x_j) ≥ d_i（满足需求） x_j ≥ 0，且为整数

主要挑战：

• 可能的切割模式数量呈指数级增长
• 无法显式枚举所有模式
• 需要使用列生成技术

---

算法和求解方法

方法 1：降序首次适配（FFD）——简单启发式

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")

方法 2：降序最佳适配（BFD）——改进的启发式

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
    }

方法 3：列生成——最优解

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]

        for w in range(1, capacity + 1):
            for i in range(self.n_items):
                item_length = self.lengths[i] + self.kerf
                if item_length <= w:
                    value = dp[w - item_length] + dual_values[i]
                    if value > dp[w]:
                        dp[w] = value
                        item_used[w] = [i, 1]

        # Check if new pattern is profitable (reduced cost < 0)
        # Reduced cost = 1 - max_value
        max_value = dp[capacity]
        reduced_cost = 1 - max_value

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

        # Backtrack to find pattern
        new_pattern = [0] * self.n_items
        w = capacity

        while w > 0 and item_used[w][0] != -1:
            item_idx = item_used[w][0]
            # Count how many of this item in the pattern
            temp_w = w
            count = 0
            while temp_w > 0 and item_used[temp_w][0] == item_idx:
                count += 1
                item_length = self.lengths[item_idx] + self.kerf
                temp_w -= item_length

            new_pattern[item_idx] += count
            w = temp_w

        # Alternative: use proper unbounded knapsack backtracking
        new_pattern = self._knapsack_backtrack(dual_values)

        return new_pattern

    def _knapsack_backtrack(self, values):
        """
        Solve unbounded knapsack properly and backtrack
        """
        capacity = self.stock_length
        dp = [0] * (capacity + 1)
        used_item = [-1] * (capacity + 1)

        for w in range(1, capacity + 1):
            for i in range(self.n_items):
                item_length = self.lengths[i] + self.kerf
                if item_length <= w:
                    new_value = dp[w - item_length] + values[i]
                    if new_value > dp[w]:
                        dp[w] = new_value
                        used_item[w] = i

        # Backtrack
        pattern = [0] * self.n_items
        w = capacity

        while w > 0 and used_item[w] != -1:
            i = used_item[w]
            pattern[i] += 1
            w -= (self.lengths[i] + self.kerf)

        return pattern

    def solve(self, max_iterations=100, tolerance=1e-6):
        """
        Solve cutting stock problem using column generation

        Algorithm:
        1. Start with initial patterns
        2. Solve master problem (LP)
        3. Get dual values
        4. Solve pricing problem to generate new pattern
        5. If profitable pattern found, add to master and repeat
        6. Otherwise, solve master as IP for integer solution

        Returns: optimal cutting plan
        """

        # Generate initial patterns
        self.generate_initial_patterns()

        print("Starting Column Generation...")
        print(f"Items: {self.n_items}")
        print(f"Total demand: {sum(self.demands)}")
        print(f"Stock length: {self.stock_length}")
        print()

        iteration = 0

        while iteration < max_iterations:
            iteration += 1

            # Solve master problem
            master_solution = self.solve_master_problem()

            if master_solution['status'] != 'Optimal':
                print(f"Warning: Master problem not optimal: {master_solution['status']}")
                break

            dual_values = master_solution['dual_values']

            print(f"Iteration {iteration}: LP Objective = {master_solution['objective']:.2f}")

            # Solve pricing problem
            new_pattern = self.solve_pricing_problem(dual_values)

            if new_pattern is None:
                print("No more profitable patterns. LP optimal.")
                break

            # Add new pattern
            self.patterns.append(new_pattern)
            print(f"  Added pattern: {new_pattern}")

        # Solve master problem as Integer Program for final solution
        print("\nSolving integer program for final solution...")
        integer_solution = self.solve_master_ip()

        return integer_solution

    def solve_master_ip(self):
        """
        Solve Master Problem as Integer Program

        Get integer solution from LP relaxation
        """

        prob = LpProblem("Cutting_Stock_IP", LpMinimize)

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

        # Objective
        prob += lpSum(x), "Total_Stocks"

        # Constraints
        for i in range(self.n_items):
            prob += (lpSum(self.patterns[j][i] * x[j] for j in range(num_patterns))
                    >= self.demands[i]), f"Demand_{i}"

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

        # Extract solution
        pattern_usage = [x[j].varValue for j in range(num_patterns)]

        # Build cutting plan
        stocks = []
        for j, usage in enumerate(pattern_usage):
            if usage and usage > 0.5:
                for _ in range(int(usage)):
                    stock = {
                        'pattern_id': j,
                        'pattern': self.patterns[j],
                        'items': []
                    }

                    # Add items according to pattern
                    for i in range(self.n_items):
                        if self.patterns[j][i] > 0:
                            for _ in range(self.patterns[j][i]):
                                stock['items'].append({
                                    'length': self.lengths[i],
                                    'id': self.item_ids[i]
                                })

                    # Calculate utilization
                    total_length = sum(item['length'] for item in stock['items'])
                    stock['used_length'] = total_length
                    stock['waste'] = self.stock_length - total_length

                    stocks.append(stock)

        total_used = sum(s['used_length'] for s in stocks)
        total_available = len(stocks) * self.stock_length

        solution = {
            'num_stocks': int(value(prob.objective)),
            'stocks': stocks,
            'patterns': self.patterns,
            'pattern_usage': pattern_usage,
            'utilization': (total_used / total_available * 100) if total_available > 0 else 0,
            'total_waste': total_available - total_used,
            'status': LpStatus[prob.status]
        }

        print(f"\nOptimal solution found!")
        print(f"Stocks needed: {solution['num_stocks']}")
        print(f"Utilization: {solution['utilization']:.2f}%")
        print(f"Total waste: {solution['total_waste']}")

        return solution


# Example usage
def example_column_generation():
    """Example: Cutting steel rods"""

    # Items: (length, quantity, id)
    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
        (600, 10, 'E')    # 10 pieces of 600mm
    ]

    stock_length = 6000  # 6 meter standard stock
    kerf = 5  # 5mm saw blade width

    solver = ColumnGenerationCuttingStock(stock_length, items, kerf)
    solution = solver.solve()

    # Print detailed results
    print("\n" + "="*70)
    print("CUTTING PLAN")
    print("="*70)

    for idx, stock in enumerate(solution['stocks']):
        print(f"\nStock {idx+1}:")
        print(f"  Pattern: {stock['pattern']}")
        print(f"  Items: {[f\"{item['id']}({item['length']})\" for item in stock['items']]}")
        print(f"  Used: {stock['used_length']}mm")
        print(f"  Waste: {stock['waste']}mm ({stock['waste']/stock_length*100:.1f}%)")

    return solution

方法 4：动态规划——适用于小规模问题

def cutting_stock_dp_small(items, stock_length, max_stocks=None):
    """
    Dynamic Programming approach for small cutting stock problems

    Only practical for small problems due to exponential state space

    Parameters:
    - items: list of (length, quantity, item_id)
    - stock_length: standard stock length
    - max_stocks: maximum number of stocks to consider

    Returns: optimal solution

    Limitation: Only works for small problems (total items < 30)
    """

    # Expand items
    pieces = []
    for length, quantity, item_id in items:
        for _ in range(quantity):
            pieces.append((length, item_id))

    n = len(pieces)

    if n > 30:
        raise ValueError("Problem too large for DP approach. Use column generation.")

    if max_stocks is None:
        max_stocks = n  # Worst case

    # State: (items_packed_bitmask, number_of_stocks)
    # Value: True if achievable, False otherwise

    from functools import lru_cache

    @lru_cache(maxsize=None)
    def can_pack(remaining_mask, num_stocks):
        """Check if remaining items can be packed in num_stocks"""

        if remaining_mask == 0:
            return True

        if num_stocks == 0:
            return False

        # Try all possible patterns for next stock
        # Enumerate all subsets of remaining items that fit in one stock
        for pattern_mask in range(1, remaining_mask + 1):
            if (pattern_mask & remaining_mask) != pattern_mask:
                continue

            # Check if pattern fits in one stock
            total_length = 0
            for i in range(n):
                if pattern_mask & (1 << i):
                    total_length += pieces[i][0]

            if total_length <= stock_length:
                # Try this pattern
                new_remaining = remaining_mask & ~pattern_mask
                if can_pack(new_remaining, num_stocks - 1):
                    return True

        return False

    # Find minimum number of stocks needed
    initial_mask = (1 << n) - 1  # All items need to be packed

    for num_stocks in range(1, max_stocks + 1):
        if can_pack(initial_mask, num_stocks):
            return {
                'min_stocks': num_stocks,
                'method': 'DP (exact)',
                'note': 'Optimal solution'
            }

    return None

---

完整的一维下料求解器

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

class OneDCuttingStockSolver:
    """
    Comprehensive 1D Cutting Stock Solver

    Supports multiple solution methods:
    - Fast heuristics (FFD, BFD)
    - Optimal column generation
    - Visualization
    """

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

        Parameters:
        - stock_length: length of standard stock material
        - kerf: material lost per cut (saw blade width)
        """
        self.stock_length = stock_length
        self.kerf = kerf
        self.items = []
        self.solution = None

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

        self.items.append((length, quantity, item_id))

    def add_items(self, items_list):
        """
        Add multiple items

        items_list: list of (length, quantity) or (length, quantity, id)
        """
        for item in items_list:
            if len(item) == 2:
                self.add_item(item[0], item[1])
            else:
                self.add_item(item[0], item[1], item[2])

    def solve(self, method='column_generation', **kwargs):
        """
        Solve cutting stock problem

        Methods:
        - 'ffd': First Fit Decreasing (fast)
        - 'bfd': Best Fit Decreasing (better)
        - 'column_generation': Optimal or near-optimal

        Returns: solution dictionary
        """

        if method == 'ffd':
            self.solution = first_fit_decreasing(self.items, self.stock_length)
            self.solution['method'] = 'First Fit Decreasing'

        elif method == 'bfd':
            self.solution = best_fit_decreasing(self.items, self.stock_length)
            self.solution['method'] = 'Best Fit Decreasing'

        elif method == 'column_generation':
            cg_solver = ColumnGenerationCuttingStock(
                self.stock_length, self.items, self.kerf
            )
            self.solution = cg_solver.solve(**kwargs)
            self.solution['method'] = 'Column Generation (Optimal)'

        else:
            raise ValueError(f"Unknown method: {method}")

        return self.solution

    def visualize(self, max_stocks=10, save_path=None):
        """
        Visualize cutting patterns

        Parameters:
        - max_stocks: maximum number of stocks to display
        - save_path: path to save figure
        """

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

        stocks_to_show = min(max_stocks, len(self.solution['stocks']))

        fig, axes = plt.subplots(stocks_to_show, 1,
                                figsize=(12, stocks_to_show * 0.8))

        if stocks_to_show == 1:
            axes = [axes]

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

        for idx in range(stocks_to_show):
            ax = axes[idx]
            stock = self.solution['stocks'][idx]

            # Draw stock boundary
            ax.add_patch(patches.Rectangle(
                (0, 0), self.stock_length, 1,
                fill=False, edgecolor='black', linewidth=2
            ))

            # Draw pieces
            current_pos = 0
            for item_idx, item in enumerate(stock['items']):
                color = colors[hash(item['id']) % 20]

                # Draw piece
                ax.add_patch(patches.Rectangle(
                    (current_pos, 0), item['length'], 1,
                    facecolor=color, edgecolor='black',
                    linewidth=1, alpha=0.7
                ))

                # Add label
                center_x = current_pos + item['length'] / 2
                ax.text(center_x, 0.5, f"{item['id']}\n{item['length']}",
                       ha='center', va='center',
                       fontsize=8, fontweight='bold')

                current_pos += item['length']

            # Draw waste area
            if current_pos < self.stock_length:
                waste = self.stock_length - current_pos
                ax.add_patch(patches.Rectangle(
                    (current_pos, 0), waste, 1,
                    facecolor='gray', edgecolor='black',
                    linewidth=1, alpha=0.3, hatch='//'
                ))
                ax.text(current_pos + waste/2, 0.5, f"Waste\n{waste}",
                       ha='center', va='center',
                       fontsize=7, style='italic')

            ax.set_xlim(0, self.stock_length)
            ax.set_ylim(0, 1)
            ax.set_aspect('auto')
            ax.set_title(f'Stock {idx+1} (Used: {current_pos}, Waste: {self.stock_length-current_pos})',
                        fontsize=10)
            ax.set_xlabel('Length')
            ax.set_yticks([])
            ax.grid(True, alpha=0.3, axis='x')

        plt.suptitle(
            f'1D Cutting Stock Solution - {self.solution["method"]}\n'
            f'Stocks Used: {self.solution["num_stocks"]} | '
            f'Utilization: {self.solution["utilization"]:.1f}%',
            fontsize=14, fontweight='bold'
        )

        plt.tight_layout()

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

        plt.show()

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

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

        print("=" * 80)
        print("1D CUTTING STOCK SOLUTION")
        print("=" * 80)
        print(f"Method: {self.solution['method']}")
        print(f"Stock length: {self.stock_length}")
        print(f"Stocks used: {self.solution['num_stocks']}")
        print(f"Utilization: {self.solution['utilization']:.2f}%")
        print(f"Total waste: {self.solution.get('total_waste', self.solution.get('waste', 0))}")
        print()

        print("CUTTING PATTERNS:")
        print("-" * 80)

        for idx, stock in enumerate(self.solution['stocks'][:20]):  # Show first 20
            items_str = ", ".join([f"{item['id']}({item['length']})"
                                  for item in stock['items']])
            waste = self.stock_length - sum(item['length'] for item in stock['items'])
            print(f"Stock {idx+1:3d}: {items_str:50s} | Waste: {waste}")

        if len(self.solution['stocks']) > 20:
            print(f"... and {len(self.solution['stocks']) - 20} more stocks")

        print()

        # Item summary
        print("ITEM SUMMARY:")
        print("-" * 80)
        for length, quantity, item_id in self.items:
            print(f"{item_id}: {quantity} pieces × {length} = {quantity * length} total length")

    def export_cutting_list(self, filename):
        """Export cutting list to CSV"""

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

        import csv

        with open(filename, 'w', newline='') as f:
            writer = csv.writer(f)
            writer.writerow(['Stock #', 'Item ID', 'Length', 'Position', 'Stock Waste'])

            for stock_idx, stock in enumerate(self.solution['stocks']):
                position = 0
                waste = self.stock_length - sum(item['length'] for item in stock['items'])

                for item in stock['items']:
                    writer.writerow([
                        stock_idx + 1,
                        item['id'],
                        item['length'],
                        position,
                        waste if position == 0 else ''
                    ])
                    position += item['length']

        print(f"Cutting list exported to {filename}")


# Example usage
if __name__ == "__main__":

    print("Example 1: Steel Rod Cutting")
    print("=" * 80)

    # Create solver
    solver = OneDCuttingStockSolver(stock_length=6000, kerf=5)

    # Add items to cut
    solver.add_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
        (600, 10, 'E')    # 10 pieces of 600mm
    ])

    # Solve using column generation (optimal)
    print("\nSolving with Column Generation (optimal)...")
    solution = solver.solve(method='column_generation')
    solver.print_solution()

    # Visualize
    solver.visualize(max_stocks=5)

    # Export cutting list
    solver.export_cutting_list('cutting_list.csv')

    print("\n" + "=" * 80)
    print("Example 2: Compare Methods")
    print("=" * 80)

    # Compare different methods
    methods = ['ffd', 'bfd', 'column_generation']
    results = {}

    for method in methods:
        solver2 = OneDCuttingStockSolver(stock_length=6000)
        solver2.add_items([
            (2300, 5, 'A'),
            (1500, 8, 'B'),
            (1200, 12, 'C'),
            (800, 6, 'D')
        ])

        solution = solver2.solve(method=method)
        results[method] = {
            'stocks': solution['num_stocks'],
            'utilization': solution['utilization']
        }

    print("\nMethod Comparison:")
    print("-" * 60)
    print(f"{'Method':<25} {'Stocks':<10} {'Utilization':<15}")
    print("-" * 60)
    for method, result in results.items():
        print(f"{method:<25} {result['stocks']:<10} {result['utilization']:<15.2f}%")

---

工具和库

Python 库

PuLP——线性规划

pip install pulp

Google OR-Tools——综合优化

from ortools.linear_solver import pywraplp

# OR-Tools has built-in cutting stock examples

SciPy——优化工具包

from scipy.optimize import linprog

pycutstock——专用下料库

pip install pycutstock

商业软件

• CutList Plus——专业切割优化工具
• OptiCut——一维／二维切割优化
• Cutting Optimization Pro——多材料切割
• MaxCut——工业下料软件

在线工具

• Cut List Optimizer - 免费的网页版工具
• Cut List Calculator - 简易切割规划工具

---

常见挑战与解决方案

挑战：物料数量庞大

问题：

• 数百或数千件物料
• 列生成速度太慢
• 需要考虑的模式过多

解决方案：

• 使用 FFD/BFD 快速生成初始解
• 在时间限制内应用列生成
• 将长度相近的物料分组
• 并行生成模式
• 实施模式池管理

挑战：多种原料长度

问题：

• 可用的原料长度不同
• 每种原料的成本不同
• 必须选择使用哪种原料

解决方案：

def multi_length_cutting_stock(items, stock_specs):
    """
    Solve cutting stock with multiple stock lengths

    Parameters:
    - items: list of (length, quantity, id)
    - stock_specs: list of (length, cost, availability)

    Returns: solution minimizing total cost
    """

    from pulp import *

    # For each stock type, generate patterns
    all_patterns = []
    pattern_costs = []
    pattern_stock_type = []

    for stock_idx, (stock_length, stock_cost, availability) in enumerate(stock_specs):
        # Generate patterns for this stock length
        # (simplified - use proper pattern generation)
        patterns = generate_patterns_for_stock(items, stock_length)

        for pattern in patterns:
            all_patterns.append(pattern)
            pattern_costs.append(stock_cost)
            pattern_stock_type.append(stock_idx)

    # Solve with cost objective
    prob = LpProblem("Multi_Stock_Cutting", LpMinimize)

    n_patterns = len(all_patterns)
    x = [LpVariable(f"x_{j}", lowBound=0, cat='Integer')
         for j in range(n_patterns)]

    # Objective: minimize total cost
    prob += lpSum(pattern_costs[j] * x[j] for j in range(n_patterns))

    # Demand constraints
    n_items = len(items)
    for i in range(n_items):
        prob += lpSum(all_patterns[j][i] * x[j]
                     for j in range(n_patterns)) >= items[i][1]

    # Availability constraints
    for stock_idx in range(len(stock_specs)):
        if stock_specs[stock_idx][2] is not None:  # If availability limited
            prob += lpSum(x[j] for j in range(n_patterns)
                         if pattern_stock_type[j] == stock_idx) <= stock_specs[stock_idx][2]

    prob.solve(PULP_CBC_CMD(msg=0))

    return {
        'total_cost': value(prob.objective),
        'pattern_usage': [x[j].varValue for j in range(n_patterns)]
    }

def generate_patterns_for_stock(items, stock_length):
    """Generate feasible patterns for a given stock length"""
    # Simplified pattern generation
    patterns = []
    # Implementation similar to column generation pricing problem
    return patterns

挑战：余料管理

问题：

• 之前切割原料后留下的余料
• 希望先使用余料，再切割新原料
• 有各种长度余料的库存

解决方案：

def cutting_with_residuals(items, stock_length, residuals):
    """
    Cutting stock considering existing residual pieces

    Parameters:
    - items: list of (length, quantity, id)
    - stock_length: new stock length
    - residuals: list of (length, quantity) of leftover pieces

    Strategy:
    1. First try to satisfy demand from residuals
    2. Then cut new stock for remaining demand
    """

    # Step 1: Allocate residuals using FFD
    remaining_items = []

    for item_length, item_qty, item_id in items:
        qty_needed = item_qty

        # Try to use residuals
        for res_idx, (res_length, res_qty) in enumerate(residuals):
            if res_length >= item_length and res_qty > 0:
                use_qty = min(qty_needed, res_qty)
                residuals[res_idx] = (res_length, res_qty - use_qty)
                qty_needed -= use_qty

                if qty_needed == 0:
                    break

        if qty_needed > 0:
            remaining_items.append((item_length, qty_needed, item_id))

    # Step 2: Cut new stock for remaining items
    if remaining_items:
        solution = first_fit_decreasing(remaining_items, stock_length)
    else:
        solution = {'num_stocks': 0, 'stocks': []}

    return {
        'new_stocks_needed': solution['num_stocks'],
        'residuals_used': sum(r[1] for r in residuals if r[1] > 0),
        'solution': solution
    }

挑战：设置成本与模式复杂度

问题：

• 不同的切割模式需要不同的设置
• 需要权衡废料量与模式数量
• 倾向于选择更简单的模式

解决方案：

• 修改目标函数：最小化（原料数量 + α × 模式数量）
• 增加模式复杂度惩罚
• 限制不同模式的数量
• 为重复使用模式添加奖励

---

输出格式

切割库存解决方案报告

问题摘要：

• 材料：钢棒
• 原料长度：6000mm
• 锯缝宽度：5mm
• 物料总数：41 件（5 种不同长度）
• 所需总长度：51,400mm

解决方案：

• 方法：列生成（最优）
• 使用原料数：12
• 材料总量：72,000mm
• 已利用材料：51,400mm（71.4%）
• 废料总量：20,600mm（28.6%）
• 每根原料的平均废料：1,717mm

切割模式：

模式	使用次数	物料	废料	利用率
1	3	2×2300, 1×1200	195mm	96.8%
2	4	3×1500, 1×800	200mm	96.7%
3	2	4×1200, 1×600	595mm	90.1%
4	3	6×800	1,200mm	80.0%

详细切割清单：

Stock 1: A(2300) A(2300) C(1200) | Waste: 195mm
Stock 2: A(2300) A(2300) C(1200) | Waste: 195mm
Stock 3: A(2300) A(2300) C(1200) | Waste: 195mm
Stock 4: B(1500) B(1500) B(1500) D(800) | Waste: 200mm
...

材料成本分析：

• 每根原料成本：$45.00
• 材料总成本：$540.00
• 废料成本：$154.50（28.6%）
• 每件物料成本：$13.17

---

需要询问的问题

如果需要更多背景信息：

1. 要切割什么材料？（钢材、木材、管材、纸张、织物）
2. 标准原料长度是多少？
3. 需要哪些物料？（长度和数量清单）
4. 是否需要考虑锯片锯缝／切割宽度？
5. 是否有可优先使用的余料？
6. 是否有最小可用余料长度？
7. 哪项更重要：减少原料数量，还是降低废料百分比？
8. 需要最优解，还是快速获得一个较好的解即可？
9. 是否有多种成本不同的原料长度可供选择？
10. 这是一次性切割，还是重复生产？

---

相关技能

• 2d-cutting-stock：用于二维板材切割
• guillotine-cutting：用于受闸刀式切割约束的情况
• nesting-optimization：用于不规则形状排样
• trim-loss-minimization：用于一般性边角料损耗优化
• knapsack-problems：用于基于价值的切割优化
• column-generation：用于高级模式生成技术
• optimization-modeling：用于一般优化问题建模