ILP基礎とPuLP

🔥 Vibe プロンプト

「2つの製品を生産。原料と労働時間に制限あり。利益を最大化。」

整数線形計画法（ILP）とは？

ILP は線形計画法（LP）を拡張し、変数の一部または全部が整数値であることを要求します。現実の意思決定（0.7個の工場を建てる、0.5人雇う）に最適です。

| 構成要素 | 説明 | 例 | |---------|------|------| | 決定変数 | 制御できるもの | A製品の生産量（整数） | | 目的関数 | 最適化するもの | 利益を最大化 | | 制約条件 | 制限事項 | 原料≤100kg、労働時間≤80h | | 整数制約 | 整数値のみ | 生産量は整数（端数不可） |

LP vs ILP

| 項目 | LP | ILP | |------|-----|------| | 変数 | 連続値（0.5可） | 整数値（0,1,2…） | | 難易度 | 易（多項式時間） | 難（NP困難） | | 解法 | シンプレックス法 | 分枝限定法 | | 用途 | 配合、資源配分 | スケジューリング、配置 |

PuLPによる実装

import pulp

prob = pulp.LpProblem("工場生産計画", pulp.LpMaximize)

# 決定変数（整数 = 端数不可）
ProductA = pulp.LpVariable("製品A", lowBound=0, cat="Integer")
ProductB = pulp.LpVariable("製品B", lowBound=0, cat="Integer")

# 目的関数: 総利益を最大化
prob += 40 * ProductA + 30 * ProductB, "総利益"

# 制約条件
prob += 2 * ProductA + 1 * ProductB <= 100, "原料制約"
prob += 1 * ProductA + 2 * ProductB <= 80, "労働時間制約"

# 求解
prob.solve()

# 結果
print(f"\n{'='*45}")
print(f"求解状態: {pulp.LpStatus[prob.status]}")
print(f"{'='*45}")
print(f"製品A: {int(pulp.value(ProductA))} 個")
print(f"製品B: {int(pulp.value(ProductB))} 個")
print(f"総利益: ${pulp.value(prob.objective)}")

# 制約確認
print(f"\n制約確認:")
print(f"  原料: 2×{int(pulp.value(ProductA))}+1×{int(pulp.value(ProductB))} = {2*int(pulp.value(ProductA))+int(pulp.value(ProductB))} ≤ 100 ✅")
print(f"  労働: 1×{int(pulp.value(ProductA))}+2×{int(pulp.value(ProductB))} = {int(pulp.value(ProductA))+2*int(pulp.value(ProductB))} ≤ 80 ✅")

応用

| 産業 | 用途 | 変数タイプ | |------|------|----------| | 製造 | 製品ミックス最適化 | 整数（ロットサイズ） | | 物流 | 配送ルート計画 | バイナリ（行く/行かない） | | 金融 | ポートフォリオ選択 | バイナリ（選ぶ/選ばない） | | 小売 | 在庫発注最適化 | 整数（発注数） |

まとめ

| 概念 | 要点 | |------|------| | LP | 連続変数、多項式時間 | | ILP | 整数変数、NP困難、分枝限定法 | | PuLP | PythonのLP/ILPモデリングライブラリ | | CBC | デフォルトのオープンソースソルバー | | 変数タイプ | Continuous, Integer, Binary

まとめ

ILP は線形計画法に整数制約を加えたもの
分枝限定法 が ILP の主要な解法
PuLP は Python で ILP を解くためのライブラリ
実際の問題では、問題の規模が大きくなると求解時間が急増する

よくある問題と解決策

| 問題 | 原因 | 解決方法 | |------|------|---------| | 期待通りの結果が出ない | パラメータ設定ミス | デフォルト値と境界条件を確認 | | 実行が遅い | アルゴリズムの効率 | より効率的なデータ構造を使用 | | メモリ不足 | データ量過多 | バッチ処理を検討 | | デバッグが困難 | ログ不足 | 詳細なログ出力を追加 |

さらに学ぶには

公式ドキュメントを読む
GitHubのオープンソース例を参照
コミュニティディスカッションに参加
コードを修正して結果の変化を観察