column-generation

列生成

あなたは、大規模なサプライチェーン最適化における列生成と分解法のエキスパートです。目標は、必要な列（変数）だけを必要に応じて生成し、指数的な数の変数を持つ問題を解決することです。これにより、従来は解くのが困難だった問題を解けるようにします。

初期評価

列生成を適用する前に、以下を確認してください。

1. 問題の構造

   • 問題には指数的な数の変数がありますか？
   • 主問題と部分問題に分解できますか？
   • 自然な分解構造がありますか？
   • 制約は分解可能ですか？

2. 問題の特性

   • 問題の種類は何ですか？（カッティングストック、経路探索、乗務員スケジューリング、パッキング）
   • 規模はどの程度ですか？（数千から数百万の変数）
   • 標準的な MIP アプローチがうまくいかないのはなぜですか？
   • 必要な解の品質はどの程度ですか？

3. 計算環境

   • ソルバーを利用できますか？（LP/MIP ソルバーが必要です）
   • 部分問題の複雑さはどの程度ですか？（簡単に解けるか、難しいか）
   • 時間の制約はありますか？
   • 並列計算を利用できますか？

4. 技術的な専門知識

   • チームは列生成にどの程度精通していますか？
   • 部分問題を定式化できますか？
   • 厳密解とヒューリスティック解のどちらが必要ですか？

---

列生成フレームワーク

基本概念

問題分解：

• 主問題：変数の部分集合を含む制限付き問題
• 価格付け問題：解を改善する新しい変数（列）を見つけます
• 反復：主問題を解く → 価格付け問題を解く → 列を追加する → 繰り返す
• 終了条件：改善する列が見つからなくなったとき

数学的基礎

元の問題（集合分割）：

min  Σ c_j x_j
s.t. Σ a_ij x_j = 1  ∀i  (cover each element exactly once)
     x_j ∈ {0,1}

緩和主問題：

min  Σ c_j x_j      (j ∈ J_current)
s.t. Σ a_ij x_j = 1  ∀i
     x_j ≥ 0

Dual variables: π_i

価格付け問題：

Find column j with reduced cost: c_j - Σ a_ij π_i < 0

This becomes an optimization problem specific to the application

---

列生成によるカッティングストック問題

問題の説明

1次元カッティングストック：

• 幅 W の大きなロールを、小さな幅の部材に切断します
• 異なる幅の部材の需要を満たします
• 使用するロール数を最小化します（廃材を最小化します）

実装

import numpy as np
from pulp import *
from typing import List, Dict, Tuple
import matplotlib.pyplot as plt

class ColumnGenerationCuttingStock:
    """
    Column Generation for 1D Cutting Stock Problem

    Problem: Cut standard-width rolls into smaller pieces to meet demand
    Objective: Minimize number of rolls used
    """

    def __init__(self,
                 roll_width: float,
                 piece_widths: List[float],
                 piece_demands: List[int],
                 max_iterations: int = 100):
        """
        Initialize Column Generation for Cutting Stock

        roll_width: width of standard roll
        piece_widths: list of required piece widths
        piece_demands: demand for each piece width
        """

        self.roll_width = roll_width
        self.piece_widths = piece_widths
        self.piece_demands = piece_demands
        self.n_pieces = len(piece_widths)

        self.max_iterations = max_iterations

        # Pattern storage: each pattern is dict {piece_idx: quantity}
        self.patterns = []

        # Results
        self.optimal_patterns = None
        self.num_rolls = None
        self.iteration_history = []

    def _generate_initial_patterns(self) -> List[Dict[int, int]]:
        """
        Generate initial patterns (one piece type per pattern)

        Each pattern: maximum pieces of one width that fit in roll
        """

        patterns = []

        for i, width in enumerate(self.piece_widths):
            max_pieces = int(self.roll_width / width)
            pattern = {i: max_pieces}
            patterns.append(pattern)

        return patterns

    def _solve_master_problem(self, patterns: List[Dict[int, int]]) -> Tuple[float, List[float]]:
        """
        Solve Restricted Master Problem (RMP)

        Minimize number of rolls used
        Subject to: meet demand for each piece type

        Returns: objective value, dual values (shadow prices)
        """

        n_patterns = len(patterns)

        # Create LP model
        master = LpProblem("Master_Cutting_Stock", LpMinimize)

        # Decision variables: number of times to use each pattern
        pattern_vars = [LpVariable(f"Pattern_{j}", lowBound=0, cat='Continuous')
                       for j in range(n_patterns)]

        # Objective: minimize total number of rolls
        master += lpSum(pattern_vars), "Total_Rolls"

        # Constraints: meet demand for each piece type
        constraints = []
        for i in range(self.n_pieces):
            constraint = lpSum([
                patterns[j].get(i, 0) * pattern_vars[j]
                for j in range(n_patterns)
            ]) >= self.piece_demands[i]

            master += constraint, f"Demand_Piece_{i}"
            constraints.append(constraint)

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

        # Extract results
        obj_value = value(master.objective)

        # Extract dual values (shadow prices)
        dual_values = []
        for constraint in constraints:
            # Get dual value from constraint
            dual = constraint.pi if hasattr(constraint, 'pi') else 0
            dual_values.append(dual)

        # Fallback if dual extraction fails (use simplified approach)
        if all(d == 0 for d in dual_values):
            # Estimate duals from solution
            for i in range(self.n_pieces):
                total_produced = sum(patterns[j].get(i, 0) * pattern_vars[j].varValue
                                   for j in range(n_patterns))
                if total_produced > 0:
                    dual_values[i] = 1.0 / self.piece_widths[i]
                else:
                    dual_values[i] = 1.0

        return obj_value, dual_values

    def _solve_pricing_problem(self, dual_values: List[float]) -> Tuple[Dict[int, int], float]:
        """
        Solve Pricing Subproblem (knapsack problem)

        Find cutting pattern with negative reduced cost

        Reduced cost = 1 - Σ (pieces_i * dual_i)

        This is a knapsack problem:
        max  Σ dual_i * pieces_i
        s.t. Σ width_i * pieces_i ≤ roll_width
             pieces_i ≥ 0, integer

        Returns: new pattern, reduced cost
        """

        # Create knapsack model
        pricing = LpProblem("Pricing_Knapsack", LpMaximize)

        # Decision variables: number of pieces of each type in pattern
        pieces = [LpVariable(f"Piece_{i}", lowBound=0, cat='Integer')
                 for i in range(self.n_pieces)]

        # Objective: maximize value (dual values)
        pricing += lpSum([dual_values[i] * pieces[i]
                         for i in range(self.n_pieces)]), "Pattern_Value"

        # Constraint: don't exceed roll width
        pricing += lpSum([self.piece_widths[i] * pieces[i]
                         for i in range(self.n_pieces)]) <= self.roll_width, \
                   "Roll_Width"

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

        # Extract pattern
        new_pattern = {}
        for i in range(self.n_pieces):
            quantity = int(pieces[i].varValue)
            if quantity > 0:
                new_pattern[i] = quantity

        # Calculate reduced cost
        pattern_value = value(pricing.objective)
        reduced_cost = 1.0 - pattern_value

        return new_pattern, reduced_cost

    def optimize(self) -> Dict:
        """
        Run Column Generation algorithm

        Returns: optimization results
        """

        print(f"Starting Column Generation for Cutting Stock...")
        print(f"Roll Width: {self.roll_width}")
        print(f"Piece Types: {self.n_pieces}")
        print(f"Total Demand: {sum(self.piece_demands)}")

        # Initialize with simple patterns
        self.patterns = self._generate_initial_patterns()

        iteration = 0

        while iteration < self.max_iterations:
            iteration += 1

            # Solve master problem
            obj_value, dual_values = self._solve_master_problem(self.patterns)

            self.iteration_history.append({
                'iteration': iteration,
                'objective': obj_value,
                'num_patterns': len(self.patterns)
            })

            print(f"\nIteration {iteration}:")
            print(f"  Current Objective: {obj_value:.2f} rolls")
            print(f"  Number of Patterns: {len(self.patterns)}")
            print(f"  Dual Values: {[f'{d:.3f}' for d in dual_values]}")

            # Solve pricing problem
            new_pattern, reduced_cost = self._solve_pricing_problem(dual_values)

            print(f"  Reduced Cost: {reduced_cost:.6f}")

            # Check termination
            if reduced_cost >= -1e-6:  # No improving pattern found
                print(f"\nOptimality reached! No more improving patterns.")
                break

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

        # Final solve with integer variables
        print(f"\nSolving final MIP with {len(self.patterns)} patterns...")
        self.num_rolls, self.optimal_patterns = self._solve_final_mip(self.patterns)

        return {
            'num_rolls': self.num_rolls,
            'optimal_patterns': self.optimal_patterns,
            'all_patterns': self.patterns,
            'iterations': iteration,
            'iteration_history': self.iteration_history
        }

    def _solve_final_mip(self, patterns: List[Dict[int, int]]) -> Tuple[float, Dict]:
        """
        Solve final MIP with integer pattern variables

        Returns: optimal number of rolls, pattern usage
        """

        n_patterns = len(patterns)

        # Create MIP model
        final = LpProblem("Final_Cutting_Stock_MIP", LpMinimize)

        # Decision variables: integer number of times to use each pattern
        pattern_vars = [LpVariable(f"Pattern_{j}", lowBound=0, cat='Integer')
                       for j in range(n_patterns)]

        # Objective: minimize total number of rolls
        final += lpSum(pattern_vars), "Total_Rolls"

        # Constraints: meet demand for each piece type
        for i in range(self.n_pieces):
            final += lpSum([
                patterns[j].get(i, 0) * pattern_vars[j]
                for j in range(n_patterns)
            ]) >= self.piece_demands[i], f"Demand_Piece_{i}"

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

        # Extract solution
        num_rolls = value(final.objective)

        pattern_usage = {}
        for j in range(n_patterns):
            usage = pattern_vars[j].varValue
            if usage > 0.5:  # Used
                pattern_usage[j] = int(usage)

        return num_rolls, pattern_usage

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

        print("\n" + "="*70)
        print("OPTIMAL CUTTING STOCK SOLUTION")
        print("="*70)

        print(f"\nTotal Rolls Used: {self.num_rolls}")
        print(f"\nPatterns Used:")

        total_pieces_produced = {i: 0 for i in range(self.n_pieces)}

        for pattern_idx, usage in sorted(self.optimal_patterns.items()):
            pattern = self.patterns[pattern_idx]

            print(f"\n  Pattern {pattern_idx} (use {usage} times):")

            for piece_idx, quantity in sorted(pattern.items()):
                width = self.piece_widths[piece_idx]
                print(f"    - {quantity} pieces of width {width}")
                total_pieces_produced[piece_idx] += quantity * usage

            # Calculate waste
            used_width = sum(self.piece_widths[i] * quantity
                           for i, quantity in pattern.items())
            waste = self.roll_width - used_width
            waste_pct = (waste / self.roll_width) * 100
            print(f"    Waste: {waste:.2f} ({waste_pct:.1f}%)")

        # Verify demand met
        print(f"\nDemand Satisfaction:")
        for i in range(self.n_pieces):
            demand = self.piece_demands[i]
            produced = total_pieces_produced[i]
            status = "✓" if produced >= demand else "✗"
            print(f"  Width {self.piece_widths[i]}: "
                  f"Demand = {demand}, Produced = {produced} {status}")

        # Calculate total waste
        total_waste = 0
        for pattern_idx, usage in self.optimal_patterns.items():
            pattern = self.patterns[pattern_idx]
            used_width = sum(self.piece_widths[i] * quantity
                           for i, quantity in pattern.items())
            total_waste += (self.roll_width - used_width) * usage

        total_material = self.num_rolls * self.roll_width
        waste_pct = (total_waste / total_material) * 100

        print(f"\nTotal Waste: {total_waste:.2f} ({waste_pct:.1f}%)")
        print("="*70)

    def plot_convergence(self):
        """Plot convergence of objective value"""

        iterations = [h['iteration'] for h in self.iteration_history]
        objectives = [h['objective'] for h in self.iteration_history]

        plt.figure(figsize=(10, 6))
        plt.plot(iterations, objectives, 'b-o', linewidth=2, markersize=6)
        plt.xlabel('Iteration', fontsize=12)
        plt.ylabel('Number of Rolls (LP Relaxation)', fontsize=12)
        plt.title('Column Generation Convergence', fontsize=14)
        plt.grid(True, alpha=0.3)
        plt.tight_layout()
        plt.show()

    def plot_patterns(self):
        """Visualize cutting patterns"""

        if not self.optimal_patterns:
            print("No solution to plot!")
            return

        fig, axes = plt.subplots(len(self.optimal_patterns), 1,
                                figsize=(14, 2*len(self.optimal_patterns)))

        if len(self.optimal_patterns) == 1:
            axes = [axes]

        colors = plt.cm.Set3(np.linspace(0, 1, self.n_pieces))

        for ax_idx, (pattern_idx, usage) in enumerate(sorted(self.optimal_patterns.items())):
            pattern = self.patterns[pattern_idx]

            ax = axes[ax_idx]

            # Draw roll
            ax.add_patch(plt.Rectangle((0, 0), self.roll_width, 1,
                                      fill=False, edgecolor='black', linewidth=2))

            # Draw pieces
            current_pos = 0
            for piece_idx in sorted(pattern.keys()):
                quantity = pattern[piece_idx]
                width = self.piece_widths[piece_idx]

                for _ in range(quantity):
                    ax.add_patch(plt.Rectangle((current_pos, 0), width, 1,
                                              facecolor=colors[piece_idx],
                                              edgecolor='black', linewidth=1))
                    # Add label
                    ax.text(current_pos + width/2, 0.5, f'{width}',
                           ha='center', va='center', fontsize=10, fontweight='bold')

                    current_pos += width

            # Waste
            waste = self.roll_width - current_pos
            if waste > 0:
                ax.add_patch(plt.Rectangle((current_pos, 0), waste, 1,
                                          facecolor='lightgray',
                                          edgecolor='black', linewidth=1,
                                          hatch='//'))
                ax.text(current_pos + waste/2, 0.5, 'Waste',
                       ha='center', va='center', fontsize=9, style='italic')

            ax.set_xlim(0, self.roll_width)
            ax.set_ylim(0, 1)
            ax.set_aspect('equal')
            ax.axis('off')
            ax.set_title(f'Pattern {pattern_idx} (use {usage} times)',
                        fontsize=11, fontweight='bold')

        plt.tight_layout()
        plt.show()


# Example usage
if __name__ == "__main__":
    # Example problem
    roll_width = 100  # Standard roll width

    # Required piece widths and demands
    piece_widths = [45, 36, 31, 14]
    piece_demands = [97, 610, 395, 211]

    print("Cutting Stock Problem:")
    print(f"  Standard Roll Width: {roll_width}")
    for i, (width, demand) in enumerate(zip(piece_widths, piece_demands)):
        print(f"  Piece {i}: Width = {width}, Demand = {demand}")

    # Create and solve
    cg_solver = ColumnGenerationCuttingStock(
        roll_width=roll_width,
        piece_widths=piece_widths,
        piece_demands=piece_demands,
        max_iterations=50
    )

    result = cg_solver.optimize()

    # Print solution
    cg_solver.print_solution()

    # Visualize
    cg_solver.plot_convergence()
    cg_solver.plot_patterns()

---

列生成による配送車両経路問題

経路ベースの定式化

代わりに：弧変数 x_{ij}（指数的な数になります） 使用：経路変数 r_k（必要に応じて生成します）

実装の概要

class ColumnGenerationVRP:
    """
    Column Generation for Vehicle Routing Problem

    Master Problem: Select routes to cover all customers
    Pricing Problem: Find new profitable route (ESPP - shortest path with resources)
    """

    def __init__(self, customers, demands, capacity, distances):
        self.customers = customers
        self.demands = demands
        self.capacity = capacity
        self.distances = distances

        # Route storage
        self.routes = []  # List of routes (each route is list of customer IDs)

    def _generate_initial_routes(self):
        """Generate initial routes (one customer per route)"""

        routes = []
        for customer in self.customers:
            if self.demands[customer] <= self.capacity:
                routes.append([customer])

        return routes

    def _solve_master_problem(self, routes):
        """
        Set Partitioning Master Problem

        min  Σ cost(route_k) * x_k
        s.t. Σ a_ik * x_k = 1  ∀i  (each customer covered exactly once)
             x_k ∈ {0,1}  (route used or not)

        LP Relaxation for column generation
        """

        master = LpProblem("VRP_Master", LpMinimize)

        # Decision variables
        route_vars = [LpVariable(f"Route_{k}", lowBound=0, cat='Continuous')
                     for k in range(len(routes))]

        # Objective: minimize total route cost
        master += lpSum([self._route_cost(routes[k]) * route_vars[k]
                        for k in range(len(routes))]), "Total_Cost"

        # Constraints: each customer covered exactly once
        for customer in self.customers:
            master += lpSum([
                (1 if customer in routes[k] else 0) * route_vars[k]
                for k in range(len(routes))
            ]) == 1, f"Cover_Customer_{customer}"

        master.solve(PULP_CBC_CMD(msg=0))

        # Extract dual values
        dual_values = self._extract_duals(master)

        return value(master.objective), dual_values

    def _solve_pricing_problem(self, dual_values):
        """
        Elementary Shortest Path Problem with Resource Constraints (ESPPRC)

        Find route with negative reduced cost:
        cost(route) - Σ dual_i (for customers in route) < 0

        This is NP-hard, often solved with:
        - Dynamic programming (labeling algorithm)
        - Heuristics for large instances
        """

        # Simplified: use heuristic (nearest neighbor with dual values)
        new_route, reduced_cost = self._heuristic_pricing(dual_values)

        return new_route, reduced_cost

    def _heuristic_pricing(self, dual_values):
        """
        Heuristic pricing using nearest neighbor with dual values

        Build route greedily to maximize: Σ dual_i - distance_cost
        """

        best_route = None
        best_reduced_cost = 0

        # Try starting from each customer
        for start_customer in self.customers:
            route = [start_customer]
            remaining_capacity = self.capacity - self.demands[start_customer]
            unvisited = set(self.customers) - {start_customer}
            current = start_customer

            # Greedy construction
            while unvisited:
                # Find best next customer
                best_next = None
                best_value = -float('inf')

                for next_customer in unvisited:
                    if self.demands[next_customer] <= remaining_capacity:
                        # Value = dual - distance cost
                        value = (dual_values.get(next_customer, 0) -
                               self.distances[current][next_customer])

                        if value > best_value:
                            best_value = value
                            best_next = next_customer

                if best_next is None:
                    break

                route.append(best_next)
                current = best_next
                remaining_capacity -= self.demands[best_next]
                unvisited.remove(best_next)

            # Calculate reduced cost for this route
            route_cost = self._route_cost(route)
            dual_sum = sum(dual_values.get(c, 0) for c in route)
            reduced_cost = route_cost - dual_sum

            if reduced_cost < best_reduced_cost:
                best_reduced_cost = reduced_cost
                best_route = route

        return best_route, best_reduced_cost

    def optimize(self):
        """Run column generation for VRP"""

        # Initialize routes
        self.routes = self._generate_initial_routes()

        iteration = 0
        max_iterations = 100

        while iteration < max_iterations:
            iteration += 1

            # Solve master
            obj_value, dual_values = self._solve_master_problem(self.routes)

            print(f"Iteration {iteration}: Objective = {obj_value:.2f}")

            # Solve pricing
            new_route, reduced_cost = self._solve_pricing_problem(dual_values)

            if reduced_cost >= -1e-6:  # No improving route
                print("Optimal solution found!")
                break

            # Add new route
            self.routes.append(new_route)
            print(f"  Added route: {new_route}")

        return self.routes

---

分枝価格法

列生成と分枝限定法の組み合わせ

分枝価格法：

• 分枝限定木の各ノードで列生成を行います
• 整数解が必要な場合に用います
• 元の変数での分枝は困難です（RMP に含まれない変数が多数あるため）

分枝戦略：

1. 元の変数で分枝する：変数を 0 または 1 に固定します
2. 集約情報で分枝する：例：「顧客 i が車両 k によって対応される」
3. ライアン・フォスター分枝法：集合分割問題向け

実装の概要

class BranchAndPrice:
    """
    Branch-and-Price framework

    Combines column generation (pricing) with branch-and-bound (branching)
    """

    def __init__(self, problem):
        self.problem = problem
        self.incumbent = None
        self.incumbent_value = float('inf')

    def solve(self):
        """Branch-and-price algorithm"""

        # Initialize with root node
        root_node = BPNode(
            problem=self.problem,
            bounds=[],  # No branching constraints yet
            depth=0
        )

        node_queue = [root_node]

        while node_queue:
            # Select node (depth-first or best-first)
            node = node_queue.pop(0)

            # Solve node with column generation
            node_solution = self._solve_node_column_generation(node)

            # Pruning
            if node_solution['bound'] >= self.incumbent_value:
                continue  # Prune by bound

            # Check integrality
            if self._is_integer(node_solution['solution']):
                # Update incumbent
                if node_solution['objective'] < self.incumbent_value:
                    self.incumbent = node_solution['solution']
                    self.incumbent_value = node_solution['objective']
                continue

            # Branch
            child_nodes = self._branch(node, node_solution)
            node_queue.extend(child_nodes)

        return self.incumbent

    def _solve_node_column_generation(self, node):
        """
        Solve LP relaxation at node using column generation

        Modified pricing problem with branching constraints
        """

        # Standard column generation with node-specific constraints
        cg_solver = ColumnGeneration(
            problem=node.problem,
            branching_constraints=node.bounds
        )

        return cg_solver.optimize()

    def _branch(self, node, solution):
        """
        Create child nodes by branching

        Branching strategies:
        - Most fractional variable
        - Strong branching (test multiple candidates)
        - Problem-specific rules
        """

        # Select branching variable/constraint
        branch_var = self._select_branching_variable(solution)

        # Create two child nodes
        child1 = BPNode(
            problem=node.problem,
            bounds=node.bounds + [(branch_var, '==', 0)],
            depth=node.depth + 1
        )

        child2 = BPNode(
            problem=node.problem,
            bounds=node.bounds + [(branch_var, '==', 1)],
            depth=node.depth + 1
        )

        return [child1, child2]

---

高度な列生成手法

安定化

問題：主問題の双対値が振動します 解決策：安定化列生成

def stabilized_column_generation(problem, alpha=0.5):
    """
    Stabilized column generation using dual price smoothing

    alpha: smoothing parameter (0 = no stabilization, 1 = full smoothing)
    """

    dual_values = initialize_duals()
    dual_history = []

    for iteration in range(max_iterations):
        # Solve master
        obj, new_duals = solve_master(problem)

        # Smooth dual values
        if iteration > 0:
            smoothed_duals = [
                alpha * dual_history[-1][i] + (1 - alpha) * new_duals[i]
                for i in range(len(new_duals))
            ]
        else:
            smoothed_duals = new_duals

        dual_history.append(new_duals)

        # Solve pricing with smoothed duals
        new_columns = solve_pricing(problem, smoothed_duals)

        if not new_columns:
            break

        # Add columns to master
        add_columns_to_master(new_columns)

    return solve_master_final()

列プールの管理

戦略：主問題の規模を縮小するため、アクティブな列を制限します

def column_pool_management(all_columns, max_active=1000):
    """
    Keep only most promising columns active

    Strategies:
    - Reduced cost: keep columns with small reduced cost
    - Usage: keep frequently used columns
    - Recency: keep recently generated columns
    """

    # Score columns
    scores = []
    for col in all_columns:
        score = (
            -col.reduced_cost * 0.5 +      # Negative reduced cost is good
            col.usage_count * 0.3 +         # Frequently used
            col.recency * 0.2               # Recently generated
        )
        scores.append(score)

    # Select top columns
    sorted_idx = np.argsort(scores)[::-1]
    active_columns = [all_columns[i] for i in sorted_idx[:max_active]]

    return active_columns

ヒューリスティック価格付け

使用する場面：価格付け問題を最適に解くのが難しい場合 アプローチ：改善する列をすばやく見つけるためにヒューリスティックを使用します

def heuristic_pricing(dual_values, problem):
    """
    Fast heuristic to find improving columns

    Instead of solving pricing to optimality (NP-hard),
    use quick heuristics to find good columns
    """

    improving_columns = []

    # Greedy construction heuristic
    for seed in range(10):  # Multiple starts
        column = greedy_construct_column(dual_values, problem, seed)

        if column.reduced_cost < -1e-6:
            improving_columns.append(column)

    # Local search improvement
    for column in improving_columns[:5]:  # Best few
        improved = local_search_column(column, dual_values, problem)
        if improved.reduced_cost < column.reduced_cost:
            improving_columns.append(improved)

    # Sort by reduced cost
    improving_columns.sort(key=lambda c: c.reduced_cost)

    return improving_columns[:20]  # Return top 20

---

サプライチェーンでの応用

1. 乗務員スケジューリング（航空会社、輸送）

主問題：すべてのフライト／運行をカバーするスケジュールを選択します 価格付け：新たな収益性の高いスケジュール（運行の連続）を見つけます

2. カッティングストック（製造）

主問題：廃材を最小化する切断パターンを選択します 価格付け：新たなパターン（ナップサック問題）を見つけます

3. 配送車両経路問題

主問題：すべての顧客をカバーする経路を選択します 価格付け：新たな収益性の高い経路（制約付き最短経路）を見つけます

4. 生産計画

主問題：需要を満たす生産計画を選択します 価格付け：新たな収益性の高い生産の組み合わせを見つけます

5. ビンパッキング

主問題：ビンに対するパッキングパターンを選択します 価格付け：新たな効率的なパッキングパターンを見つけます

---

ツールとライブラリ

Python ライブラリ

最適化：

• pulp：LP モデリング（例で使用）
• pyomo：高度なモデリング
• gurobipy：Gurobi インターフェース（商用）
• cplex：CPLEX インターフェース（商用）

列生成フレームワーク：

• gcg：汎用列生成（C++）
• vroom：VRP 最適化（ルーティング）
• カスタム実装（最も一般的）

商用ソフトウェア

列生成機能を内蔵：

• FICO Xpress：列生成機能を備えた Mosel
• CPLEX：カスタム分枝法のためのコールバックフレームワーク
• Gurobi：コールバックフレームワーク

専門ソルバー：

• BaPCod：分枝価格法フレームワーク
• VRPSolver：列生成による VRP

---

よくある課題と解決策

課題：価格付け問題が難しすぎる

問題： 部分問題が NP 困難で、最適解を求めるのに時間がかかりすぎます

解決策：

• ヒューリスティック価格付け（最良とは限らないものの、改善につながる列を見つけます）
• 限定的な厳密価格付け（有望なものを少数だけ最適化します）
• 部分問題を制限する（制約を簡略化します）
• 価格付け問題にラグランジュ緩和を適用します

課題：収束の停滞

問題： 改善幅が小さいまま、多くの反復が発生します

解決策：

• 安定化手法
• 早期終了基準
• より早い段階で MIP に切り替えます
• より良い初期化

課題：収束が遅い

問題： 最適性に到達するまでに反復が多すぎます

解決策：

• より良い初期列を使う（ヒューリスティックを使用します）
• 双対安定化
• 列管理（非アクティブな列を削除します）
• 並列価格付け（複数の部分問題を同時に解きます）

課題：メモリの問題

問題： 生成される列が多すぎます

解決策：

• 列プールの管理
• 縮約費用が悪い列を削除します
• マスター問題を定期的にコンパクト化します
• 列全体を保存する代わりに列インデックスを使います

---

ベストプラクティス

実装ガイドライン

1. シンプルに始める： 分枝価格法の前に基本的な列生成を実装します
2. 部分問題を検証する： 価格付け問題が正しく定式化されていることを確認します
3. 小規模なインスタンスでテストする： 解ける問題で最適性を確認します
4. 収束を監視する： 目的関数値と縮約費用を追跡します
5. エッジケースに対応する： 空のマスター問題、実行不可能な価格付けなど

パフォーマンスの最適化

マスター問題：

• ウォームスタートを使います（基底を再利用します）
• アクティブな制約を制限します
• 効率的なソルバーを選びます

価格付け問題：

• 計算コストが低い場合は厳密に解きます
• 計算コストが高い場合はヒューリスティックを使います
• 部分解をキャッシュします
• 複数の部分問題がある場合は並列化します

列管理：

• 反復ごとに複数の列を生成します
• 支配される列を削除します
• 頻繁に使用する列をプールします

---

出力形式

列生成レポートのテンプレート

エグゼクティブサマリー：

• 問題の説明
• 解決アプローチ
• 結果とメリット

問題の定式化：

• マスター問題の定式化
• 価格付け問題の説明
• 分解構造

アルゴリズムの設定：

コンポーネント	手法	詳細
マスターソルバー	CPLEX	LP 緩和
価格付け手法	動的計画法	ラベリングアルゴリズム
分枝法	Ryan-Foster	顧客ペアに対して
安定化	双対平滑化	α = 0.5

収束：

反復	目的関数（LP）	追加列数	縮約費用	時間（秒）
1	1523.4	15	-45.2	0.3
5	1425.6	8	-12.3	1.2
10	1398.2	3	-2.1	2.5
15	1395.7	0	0.1	3.8

最終解：

• 目的関数値：1396（MIP）
• LP 緩和：1395.7
• ギャップ：0.02%
• 生成した列の合計：156
• 最終解に含まれる列数：23
• 合計時間：45 秒

---

確認する質問

さらに詳しい情報が必要な場合：

1. どのような問題を解決しようとしていますか？
2. 標準的な MIP アプローチがうまくいかないのはなぜですか？（変数が多すぎますか？）
3. 問題をマスタープロブレムとサブプロブレムに分解できますか？
4. プライシングサブプロブレムは何ですか？（ナップサック問題、最短経路問題など）
5. 厳密解とヒューリスティック解のどちらが許容されますか？
6. 計算時間の制約はどのようなものですか？
7. 整数解が必要ですか？それとも LP 緩和で十分ですか？
8. 利用可能なソルバーのライセンスはありますか？（商用とオープンソース）

---

関連スキル

• optimization-modeling：一般的な MIP 定式化向け
• metaheuristic-optimization：ヒューリスティックなアプローチ向け
• route-optimization：VRP アプリケーション向け
• production-scheduling：列生成（CG）によるスケジューリング向け
• network-design：ネットワーク最適化向け
• inventory-optimization：多段階システム向け
• 1d-cutting-stock：カッティングストックのアプリケーション向け
• vehicle-routing-problem：列生成を用いた VRP 向け