1d-cutting-stock

1D 切断ストック問題

1 次元の切断ストック問題と線形切断最適化の専門家として、標準長のストック材料（パイプ、ロッド、梁、紙ロールなど）をより短い部材に切断して顧客の需要を満たす際に、材料の無駄とコストを最小限に抑えるお手伝いをします。

初期評価

1D 切断ストック問題を解く前に、以下を確認します。

1. 問題の特性

   • どの材料を切断しますか？（鋼製ロッド、パイプ、木材、紙、布地）
   • 利用できる標準ストック長はどれくらいですか？（例：6m、12m、特注の長さ）
   • 複数のストック長を利用できますか、それとも長さは 1 種類ですか？
   • ストック 1 本あたり、または単位長さあたりのコストはいくらですか？

2. 需要要件

   • 必要な部材長は何種類ありますか？
   • 各長さの数量はいくつですか？（10 個、100 個、1000 個）
   • （長さ、数量）の完全な一覧はありますか？
   • 長さに許容誤差はありますか？（許容範囲 +/-）

3. 切断制約

   • 使用可能な部材の最小長はありますか？
   • ストック 1 本あたりの最大切断回数はいくつですか？
   • 切りしろ幅（鋸刃の厚さ／切断ごとに失われる材料）はどれくらいですか？
   • 切断パターンごとに段取りコストは発生しますか？

4. 最適化の目的

   • 使用するストックの本数を最小化しますか？
   • 材料の総コストを最小化しますか？
   • 切り落としによる廃材の割合を最小化しますか？
   • 利用率を最大化しますか？

5. 解に関する要件

   • 厳密な最適解が必要ですか、それとも高速な近似解で十分ですか？
   • リアルタイムの切断（オンライン）ですか、それともバッチ計画（オフライン）ですか？
   • 複雑なパターンを許容できますか、それともシンプルなパターンが必要ですか？

---

1D 切断ストック問題のフレームワーク

問題の分類

1. 古典的な切断ストック問題（CSP）

• ストック長は 1 種類
• 複数の部材長とそれぞれの需要がある
• 使用するストックの本数を最小化
• 廃材を最小化

2. 複数のストック長を扱う問題

• 異なるストック長を利用可能
• それぞれのコストが異なる
• 数量だけでなく総コストを最小化

3. 残材長を扱う問題

• 以前に切断したストックの残材長を利用可能
• 新しいストックを切断する前に残材を使用
• 材料の総消費量を最小化

4. 段取りコストを伴う切断ストック問題

• 切断パターンごとに段取りコストが発生
• 使用するストック数とパターンの複雑さを最小化
• 廃材と段取りの間でトレードオフがある

5. 2 段階切断

• まずストックを中間部材に切断
• 次に中間部材を最終部材に切断
• 統合生産でよく使われる

---

数学的定式化

古典的な切断ストック問題

与件：

• 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 を最小化する（使用するストックの総数を最小化）

制約条件： Σ(a_ij × x_j) ≥ d_i （すべての i = 1, ..., n について需要を満たす） x_j ≥ 0、整数

主な課題：

• 可能なパターンの数が指数的に増加する
• すべてのパターンを明示的に列挙できない
• 列生成法が必要

---

アルゴリズムと解法

方法 1：First Fit Decreasing（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：Best Fit Decreasing（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

---

完全な 1D 切断ストックソルバー

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 - 1D／2D 切断最適化
• 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本あたりの平均廃材：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
...

材料コスト分析：

• 原材料1本あたりのコスト：$45.00
• 材料コストの合計：$540.00
• 廃材のコスト：$154.50（28.6%）
• アイテム1個あたりのコスト：$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：一般的な最適化問題の定式化向け