knapsack-problems

ナップサック問題

ナップサック最適化問題と資源配分の専門家です。目標は、容量制約を満たしながら、重量、容積、その他の資源制限を守りつつ、価値や利益を最大化する最適なアイテムの組み合わせを選ぶことです。

初期評価

ナップサック問題を解く前に、次の点を把握してください。

1. 問題の種類

   • 0/1 ナップサックですか？（各アイテムは選ぶか選ばないかのどちらか）
   • 有界ナップサックですか？（各アイテムの数量に上限がある）
   • 非有界ナップサックですか？（各アイテムの数量に制限がない）
   • 複数ナップサックですか？（複数の容器／資源がある）
   • 多次元ナップサックですか？（重量と容積など、複数の制約がある）

2. アイテムと価値

   • アイテムの種類はいくつですか？（10 種、100 種、1000 種）
   • アイテムの価値（利益、効用、優先度）は何ですか？
   • アイテムのコスト（重量、容積、価格）は何ですか？
   • アイテム間に依存関係や競合はありますか？

3. 容量制約

   • 制約は単一（重量のみ）ですか、それとも複数（重量＋容積）ですか？
   • 容量の上限（重量容量、容積容量、予算）はいくらですか？
   • 容量の異なるナップサックが複数ありますか？

4. 最適化の目標

   • 合計価値を最大化しますか？
   • 要件を満たしながら合計コストを最小化しますか？
   • 多目的最適化（価値と重量など）ですか？

5. 特別な要件

   • 必ず含めるアイテムはありますか？
   • 割り当て数に制約のあるアイテムカテゴリはありますか？
   • すべて含めるか、まったく含めないかのいずれかとなるアイテムグループはありますか？

---

ナップサック問題のフレームワーク

問題の分類

1. 0/1 ナップサック

• 各アイテムは最大 1 回だけ選択できます
• 二択の決定：含めるか、除外するか
• 最も一般的なバリエーションです
• 適用例：プロジェクトの選択、価値を考慮した貨物の積載

2. 有界ナップサック

• 各アイテムの数量に上限があります
• 決定事項：各アイテムをいくつ選ぶか（0 から max_qty まで）
• 0/1 ナップサックを一般化したものです
• 適用例：ポートフォリオの選択、在庫の選択

3. 非有界ナップサック

• 各アイテムの種類ごとに数量に制限がありません
• 容量が許す限り選択できます
• 適用例：切り出し在庫問題、コイン問題、資源の購入

4. 複数ナップサック

• 複数の容器／ビンを利用できます
• 合計価値を最大化するようにアイテムをナップサックに割り当てます
• 適用例：複数車両への積載、複数倉庫への配分

5. 多次元ナップサック

• 複数の容量制約（重量、容積、コストなど）があります
• より現実的ですが、解くのはより困難です
• 適用例：貨物の積載、複数資源を考慮したプロジェクトの選択

6. 二次ナップサック

• アイテムの価値が、ほかにどのアイテムを選ぶかによって変わります
• 相乗効果や競合を表します
• 適用例：製品の組み合わせ販売、ポートフォリオ最適化

---

数学的定式化

基本的な 0/1 ナップサック

決定変数：

• 各アイテム i に対して x_i ∈ {0, 1}
• アイテム i が選択される場合は x_i = 1、そうでない場合は 0

目的関数： Σ (v_i × x_i) を最大化

ここで、v_i = アイテム i の価値

制約条件： Σ (w_i × x_i) ≤ W

ここで：

• w_i = アイテム i の重量
• W = ナップサックの容量

計算量：

• NP 完全
• 動的計画法を用いた擬多項式時間アルゴリズムがあります

多次元ナップサック

目的関数： Σ (v_i × x_i) を最大化

制約条件： すべての制約 j = 1, 2, ..., m について、Σ (w_ij × x_i) ≤ W_j

ここで：

• w_ij = アイテム i が消費する資源 j の量
• W_j = 資源 j の容量
• m = 資源の種類数

---

アルゴリズムと解法

0/1 ナップサックの動的計画法

def knapsack_01_dynamic(values, weights, capacity):
    """
    Solve 0/1 Knapsack using Dynamic Programming

    Optimal solution with O(n*W) time complexity

    Parameters:
    - values: list of item values
    - weights: list of item weights
    - capacity: knapsack capacity

    Returns: maximum value and selected items
    """

    n = len(values)

    # Create DP table
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    # Build DP table bottom-up
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Option 1: Don't take item i-1
            dp[i][w] = dp[i-1][w]

            # Option 2: Take item i-1 (if it fits)
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                              dp[i-1][w - weights[i-1]] + values[i-1])

    # Backtrack to find selected items
    selected = []
    w = capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:
            selected.append(i-1)  # Item i-1 was selected
            w -= weights[i-1]

    selected.reverse()

    return {
        'max_value': dp[n][capacity],
        'selected_items': selected,
        'total_weight': sum(weights[i] for i in selected)
    }

# Example
values = [60, 100, 120]
weights = [10, 20, 30]
capacity = 50

result = knapsack_01_dynamic(values, weights, capacity)
print(f"Maximum value: {result['max_value']}")
print(f"Selected items: {result['selected_items']}")
print(f"Total weight: {result['total_weight']}")

省メモリ版

def knapsack_01_space_optimized(values, weights, capacity):
    """
    Space-optimized DP solution

    Uses O(W) space instead of O(n*W)
    """

    n = len(values)
    dp = [0] * (capacity + 1)

    for i in range(n):
        # Traverse backwards to avoid using updated values
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[capacity]

0/1 ナップサックの分枝限定法

import heapq

def knapsack_branch_and_bound(values, weights, capacity):
    """
    Solve 0/1 Knapsack using Branch and Bound

    More efficient for problems where DP is too slow
    Good for large capacity values

    Parameters:
    - values: list of item values
    - weights: list of item weights
    - capacity: knapsack capacity

    Returns: optimal solution
    """

    n = len(values)

    # Sort items by value/weight ratio (descending)
    items = [(values[i]/weights[i], values[i], weights[i], i) for i in range(n)]
    items.sort(reverse=True)

    class Node:
        def __init__(self, level, value, weight, bound, items_taken):
            self.level = level
            self.value = value
            self.weight = weight
            self.bound = bound
            self.items_taken = items_taken

        def __lt__(self, other):
            return self.bound > other.bound  # Max heap (best bound first)

    def calculate_bound(node):
        """Calculate upper bound of maximum value for this node"""
        if node.weight >= capacity:
            return 0

        bound = node.value
        j = node.level + 1
        remaining_capacity = capacity - node.weight

        # Add items greedily (fractional allowed for bound)
        while j < n and remaining_capacity >= items[j][2]:
            bound += items[j][1]
            remaining_capacity -= items[j][2]
            j += 1

        # Add fraction of next item if any capacity remains
        if j < n and remaining_capacity > 0:
            bound += (remaining_capacity / items[j][2]) * items[j][1]

        return bound

    # Initialize
    best_value = 0
    best_items = []

    # Priority queue (max heap by bound)
    root = Node(-1, 0, 0, 0, [])
    root.bound = calculate_bound(root)
    pq = []
    heapq.heappush(pq, root)

    # Branch and bound search
    while pq:
        node = heapq.heappop(pq)

        if node.bound <= best_value:
            continue  # Prune this branch

        level = node.level + 1
        if level >= n:
            continue

        # Branch 1: Include item at level
        ratio, value, weight, orig_idx = items[level]
        if node.weight + weight <= capacity:
            new_items = node.items_taken + [orig_idx]
            new_value = node.value + value
            new_weight = node.weight + weight

            if new_value > best_value:
                best_value = new_value
                best_items = new_items

            child = Node(level, new_value, new_weight, 0, new_items)
            child.bound = calculate_bound(child)

            if child.bound > best_value:
                heapq.heappush(pq, child)

        # Branch 2: Exclude item at level
        child = Node(level, node.value, node.weight, 0, node.items_taken[:])
        child.bound = calculate_bound(child)

        if child.bound > best_value:
            heapq.heappush(pq, child)

    return {
        'max_value': best_value,
        'selected_items': sorted(best_items),
        'total_weight': sum(weights[i] for i in best_items)
    }

貪欲法による近似

def knapsack_greedy_approximation(values, weights, capacity):
    """
    Greedy approximation for 0/1 Knapsack

    Fast but not optimal
    Good for quick solutions or large problems

    Strategy: Sort by value/weight ratio, take best items first
    """

    n = len(values)

    # Calculate value/weight ratios
    items = [(values[i]/weights[i], values[i], weights[i], i) for i in range(n)]
    items.sort(reverse=True)

    total_value = 0
    total_weight = 0
    selected = []

    for ratio, value, weight, idx in items:
        if total_weight + weight <= capacity:
            selected.append(idx)
            total_value += value
            total_weight += weight

    return {
        'total_value': total_value,
        'selected_items': sorted(selected),
        'total_weight': total_weight
    }

有界ナップサック

def bounded_knapsack(values, weights, quantities, capacity):
    """
    Solve Bounded Knapsack Problem

    Each item type has limited quantity available

    Parameters:
    - values: list of item values
    - weights: list of item weights
    - quantities: list of maximum quantities for each item
    - capacity: knapsack capacity

    Returns: optimal solution with quantities
    """

    n = len(values)

    # Expand to 0/1 knapsack by duplicating items
    expanded_values = []
    expanded_weights = []
    item_map = []

    for i in range(n):
        for j in range(quantities[i]):
            expanded_values.append(values[i])
            expanded_weights.append(weights[i])
            item_map.append(i)

    # Solve as 0/1 knapsack
    result = knapsack_01_dynamic(expanded_values, expanded_weights, capacity)

    # Convert back to quantities
    item_quantities = [0] * n
    for selected_idx in result['selected_items']:
        original_item = item_map[selected_idx]
        item_quantities[original_item] += 1

    return {
        'max_value': result['max_value'],
        'item_quantities': item_quantities,
        'total_weight': result['total_weight']
    }

# Example
values = [10, 40, 30, 50]
weights = [5, 4, 6, 3]
quantities = [3, 2, 1, 4]  # Max quantity of each item
capacity = 20

result = bounded_knapsack(values, weights, quantities, capacity)
print(f"Maximum value: {result['max_value']}")
print(f"Item quantities: {result['item_quantities']}")

非有界ナップサック

def unbounded_knapsack(values, weights, capacity):
    """
    Solve Unbounded Knapsack Problem

    Unlimited quantity of each item type

    Applications: Cutting stock, coin change, resource purchasing

    Parameters:
    - values: list of item values
    - weights: list of item weights
    - capacity: knapsack capacity

    Returns: maximum value and quantities of each item
    """

    n = len(values)

    # DP array: dp[w] = max value with capacity w
    dp = [0] * (capacity + 1)

    # For backtracking
    used_item = [-1] * (capacity + 1)

    for w in range(1, capacity + 1):
        for i in range(n):
            if weights[i] <= w:
                new_value = dp[w - weights[i]] + values[i]
                if new_value > dp[w]:
                    dp[w] = new_value
                    used_item[w] = i

    # Backtrack to find quantities
    quantities = [0] * n
    w = capacity

    while w > 0 and used_item[w] != -1:
        i = used_item[w]
        quantities[i] += 1
        w -= weights[i]

    return {
        'max_value': dp[capacity],
        'item_quantities': quantities,
        'total_weight': capacity - w
    }

# Example: Cutting steel rods
# Rod lengths and their values
values = [1, 5, 8, 9, 10, 17, 17, 20]  # Value of each length
weights = [1, 2, 3, 4, 5, 6, 7, 8]     # Length of each cut
capacity = 20  # Total rod length

result = unbounded_knapsack(values, weights, capacity)
print(f"Maximum value: {result['max_value']}")
print(f"Cuts to make: {result['item_quantities']}")

多次元ナップサック

def multidimensional_knapsack(values, constraints, capacities):
    """
    Solve Multidimensional Knapsack Problem

    Multiple resource constraints (e.g., weight AND volume)

    Parameters:
    - values: list of item values
    - constraints: 2D list where constraints[i][j] = resource j used by item i
    - capacities: list of capacity limits for each resource

    Returns: approximate solution using greedy + local search

    Note: Exact solution is NP-hard and computationally expensive
    """

    n = len(values)
    m = len(capacities)  # Number of constraints

    # Greedy initialization
    def calculate_efficiency(item_idx):
        """Calculate efficiency ratio for item"""
        # Use minimum slack across all resources
        min_slack = float('inf')
        for j in range(m):
            if constraints[item_idx][j] > 0:
                slack = capacities[j] / constraints[item_idx][j]
                min_slack = min(min_slack, slack)
        return values[item_idx] / min_slack if min_slack > 0 else 0

    # Sort by efficiency
    items = [(calculate_efficiency(i), i) for i in range(n)]
    items.sort(reverse=True)

    # Greedy selection
    selected = [False] * n
    used = [0] * m

    for efficiency, idx in items:
        # Check if item fits all constraints
        fits = True
        for j in range(m):
            if used[j] + constraints[idx][j] > capacities[j]:
                fits = False
                break

        if fits:
            selected[idx] = True
            for j in range(m):
                used[j] += constraints[idx][j]

    # Calculate solution value
    total_value = sum(values[i] for i in range(n) if selected[i])

    return {
        'total_value': total_value,
        'selected_items': [i for i in range(n) if selected[i]],
        'resource_usage': used
    }

# Example: Cargo loading with weight AND volume constraints
values = [10, 40, 30, 50, 35, 25]  # Item values
constraints = [
    # [weight, volume] for each item
    [5, 10],   # Item 0
    [4, 15],   # Item 1
    [6, 12],   # Item 2
    [3, 8],    # Item 3
    [5, 14],   # Item 4
    [4, 10]    # Item 5
]
capacities = [20, 50]  # [max weight, max volume]

result = multidimensional_knapsack(values, constraints, capacities)
print(f"Maximum value: {result['total_value']}")
print(f"Selected items: {result['selected_items']}")
print(f"Resource usage: Weight={result['resource_usage'][0]}, Volume={result['resource_usage'][1]}")

複数ナップサック問題

def multiple_knapsack(values, weights, knapsack_capacities):
    """
    Solve Multiple Knapsack Problem

    Assign items to multiple knapsacks to maximize total value

    Parameters:
    - values: list of item values
    - weights: list of item weights
    - knapsack_capacities: list of capacities for each knapsack

    Returns: assignment of items to knapsacks
    """

    from pulp import *

    n = len(values)
    m = len(knapsack_capacities)

    # Create problem
    prob = LpProblem("Multiple_Knapsack", LpMaximize)

    # Decision variables: x[i,j] = 1 if item i assigned to knapsack j
    x = LpVariable.dicts("assign",
                        [(i, j) for i in range(n) for j in range(m)],
                        cat='Binary')

    # Objective: maximize total value
    prob += lpSum([values[i] * x[i,j]
                   for i in range(n) for j in range(m)]), "Total_Value"

    # Constraint 1: Each item assigned to at most one knapsack
    for i in range(n):
        prob += lpSum([x[i,j] for j in range(m)]) <= 1, f"Item_{i}"

    # Constraint 2: Knapsack capacity constraints
    for j in range(m):
        prob += (lpSum([weights[i] * x[i,j] for i in range(n)]) <=
                knapsack_capacities[j]), f"Capacity_{j}"

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

    # Extract solution
    assignments = [[] for _ in range(m)]
    total_value = 0

    for i in range(n):
        for j in range(m):
            if x[i,j].varValue and x[i,j].varValue > 0.5:
                assignments[j].append(i)
                total_value += values[i]

    return {
        'total_value': total_value,
        'assignments': assignments,
        'status': LpStatus[prob.status]
    }

# Example: Assign items to 3 trucks
values = [15, 10, 8, 20, 12, 18, 9, 14]
weights = [5, 3, 2, 6, 4, 5, 2, 4]
truck_capacities = [10, 12, 8]  # 3 trucks

result = multiple_knapsack(values, weights, truck_capacities)
print(f"Total value: {result['total_value']}")
for i, assignment in enumerate(result['assignments']):
    print(f"Truck {i+1}: Items {assignment}")

---

完全なナップサックソルバー

class KnapsackSolver:
    """
    Comprehensive Knapsack Problem Solver

    Supports multiple knapsack variants
    """

    def __init__(self):
        self.items = []
        self.capacity = None
        self.solution = None

    def add_item(self, value, weight, item_id=None, max_quantity=1, volume=None):
        """
        Add item to knapsack problem

        Parameters:
        - value: item value/profit
        - weight: item weight/cost
        - item_id: item identifier
        - max_quantity: maximum quantity (for bounded knapsack)
        - volume: item volume (for multidimensional)
        """

        if item_id is None:
            item_id = f"Item_{len(self.items)}"

        self.items.append({
            'id': item_id,
            'value': value,
            'weight': weight,
            'max_quantity': max_quantity,
            'volume': volume,
            'ratio': value / weight if weight > 0 else float('inf')
        })

    def solve_01_knapsack(self, capacity, algorithm='dp'):
        """
        Solve 0/1 Knapsack

        Parameters:
        - capacity: knapsack capacity
        - algorithm: 'dp' (dynamic programming) or 'bb' (branch-and-bound)

        Returns: optimal solution
        """

        self.capacity = capacity

        values = [item['value'] for item in self.items]
        weights = [item['weight'] for item in self.items]

        if algorithm == 'dp':
            result = knapsack_01_dynamic(values, weights, capacity)
        elif algorithm == 'bb':
            result = knapsack_branch_and_bound(values, weights, capacity)
        else:
            raise ValueError(f"Unknown algorithm: {algorithm}")

        # Enhance result with item details
        self.solution = {
            'type': '0/1 Knapsack',
            'max_value': result['max_value'],
            'total_weight': result['total_weight'],
            'capacity': capacity,
            'utilization': (result['total_weight'] / capacity * 100) if capacity > 0 else 0,
            'items': [self.items[i] for i in result['selected_items']],
            'selected_indices': result['selected_items']
        }

        return self.solution

    def solve_bounded_knapsack(self, capacity):
        """Solve Bounded Knapsack"""

        values = [item['value'] for item in self.items]
        weights = [item['weight'] for item in self.items]
        quantities = [item['max_quantity'] for item in self.items]

        result = bounded_knapsack(values, weights, quantities, capacity)

        self.solution = {
            'type': 'Bounded Knapsack',
            'max_value': result['max_value'],
            'total_weight': result['total_weight'],
            'capacity': capacity,
            'utilization': (result['total_weight'] / capacity * 100) if capacity > 0 else 0,
            'item_quantities': result['item_quantities']
        }

        return self.solution

    def solve_unbounded_knapsack(self, capacity):
        """Solve Unbounded Knapsack"""

        values = [item['value'] for item in self.items]
        weights = [item['weight'] for item in self.items]

        result = unbounded_knapsack(values, weights, capacity)

        self.solution = {
            'type': 'Unbounded Knapsack',
            'max_value': result['max_value'],
            'total_weight': result['total_weight'],
            'capacity': capacity,
            'utilization': (result['total_weight'] / capacity * 100) if capacity > 0 else 0,
            'item_quantities': result['item_quantities']
        }

        return self.solution

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

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

        print("=" * 70)
        print(f"KNAPSACK SOLUTION: {self.solution['type']}")
        print("=" * 70)
        print(f"Maximum Value: {self.solution['max_value']}")
        print(f"Total Weight: {self.solution['total_weight']}")
        print(f"Capacity: {self.solution['capacity']}")
        print(f"Utilization: {self.solution['utilization']:.1f}%")
        print()

        if 'items' in self.solution:
            print("Selected Items:")
            for item in self.solution['items']:
                print(f"  {item['id']}: Value={item['value']}, Weight={item['weight']}")

        elif 'item_quantities' in self.solution:
            print("Item Quantities:")
            for i, qty in enumerate(self.solution['item_quantities']):
                if qty > 0:
                    item = self.items[i]
                    print(f"  {item['id']}: Quantity={qty}, "
                          f"Total Value={item['value']*qty}, "
                          f"Total Weight={item['weight']*qty}")


# Example usage
if __name__ == "__main__":
    print("Example 1: 0/1 Knapsack")
    print("-" * 50)

    solver = KnapsackSolver()

    # Add items (value, weight)
    solver.add_item(60, 10, "Item_A")
    solver.add_item(100, 20, "Item_B")
    solver.add_item(120, 30, "Item_C")
    solver.add_item(80, 15, "Item_D")
    solver.add_item(90, 18, "Item_E")

    # Solve 0/1 knapsack
    solution = solver.solve_01_knapsack(capacity=50, algorithm='dp')
    solver.print_solution()

    print("\n" + "=" * 70 + "\n")

    print("Example 2: Bounded Knapsack")
    print("-" * 50)

    solver2 = KnapsackSolver()

    # Add items with quantities
    solver2.add_item(10, 5, "Small_Box", max_quantity=3)
    solver2.add_item(40, 4, "Medium_Box", max_quantity=2)
    solver2.add_item(30, 6, "Large_Box", max_quantity=1)
    solver2.add_item(50, 3, "Premium_Box", max_quantity=4)

    solution2 = solver2.solve_bounded_knapsack(capacity=20)
    solver2.print_solution()

---

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

プロジェクトの選択

def project_portfolio_selection(projects, budget, max_projects=None):
    """
    Select optimal project portfolio given budget constraint

    Knapsack where:
    - Items = projects
    - Value = NPV or expected return
    - Weight = project cost
    """

    solver = KnapsackSolver()

    for project in projects:
        solver.add_item(
            value=project['npv'],
            weight=project['cost'],
            item_id=project['name']
        )

    solution = solver.solve_01_knapsack(capacity=budget, algorithm='dp')

    return solution

貨物積載の価値最適化

def optimize_cargo_value(cargo_items, weight_limit, volume_limit):
    """
    Maximize cargo value given weight and volume constraints

    Multidimensional knapsack with 2 constraints
    """

    values = [item['value'] for item in cargo_items]
    constraints = [[item['weight'], item['volume']] for item in cargo_items]
    capacities = [weight_limit, volume_limit]

    solution = multidimensional_knapsack(values, constraints, capacities)

    return solution

---

よくある課題と解決策

課題：問題規模が大きい

問題：

• 数千個のアイテム
• DP テーブルが大きすぎる
• 計算時間が過剰にかかる

解決策：

• DP の代わりに分枝限定法を使用する
• 高速に解を求めるため、貪欲近似を適用する
• FPTAS（完全多項式時間近似方式）を使用する
• アイテム数を減らして反復的に解く
• 独立した部分問題に並列計算を適用する

課題：制約が複数ある

問題：

• 重量と容積の制約
• 予算とスペースの制限
• 複雑な実行可能性のチェック

解決策：

• 多次元ナップサック問題として定式化する
• 効率比を用いた貪欲法のヒューリスティクスを適用する
• 整数計画法ソルバー（Gurobi、CPLEX）
• 制約プログラミング
• メタヒューリスティクス（遺伝的アルゴリズム、焼きなまし法）

---

出力形式

ナップサック解レポート

問題：

• 種類：0/1 ナップサック
• アイテム数：20
• 容量：100 lbs
• 最適化：価値を最大化

解：

• 最大価値：$2,450
• 総重量：98 lbs（容量の98%を使用）
• 選択されたアイテム数：12

選択されたアイテム：

アイテム ID	価値	重量	価値／重量比
A001	$300	10 lbs	30.0
A005	$500	15 lbs	33.3
B003	$400	18 lbs	22.2
...	...	...	...

選択されなかったアイテム：

• アイテム C002、C005、D001（容量が不足）
• 残された機会価値：$850

---

質問事項

1. ナップサック問題の種類は何ですか？（0/1、上限制約付き、上限制約なし、複数）
2. 何を最適化しますか？（価値、利益、効用）
3. 制約は何ですか？（重量、容積、予算）
4. アイテムはいくつありますか？それぞれの価値とコストはいくらですか？
5. 必ず含めるアイテムや特別な要件はありますか？
6. これは一度限りの判断ですか、それとも繰り返し発生する問題ですか？
7. 解をどれくらいの速さで計算する必要がありますか？

---

関連スキル

• optimization-modeling：一般的な最適化問題向け
• 2d-bin-packing：価値の最適化を伴わない空間充填向け
• 3d-bin-packing：3D の充填問題向け
• pallet-loading：積載の最適化向け
• multi-objective-optimization：複数の最適化基準向け