Digital Reactor
数値計算・最適化

Yes/Noの意思決定を式に載せる：混合整数計画法（MIP）の定式化と解き方

Yes/Noの意思決定を式に載せる：混合整数計画法（MIP）の定式化と解き方

はじめに

生産計画やシフト作成の現場では、「この設備を導入するか」「この人をこのシフトに入れるか」といったYes/Noの判断が必ず絡みます。生産量のような連続値だけなら線形計画法（Linear Programming; LP）で解けますが、Yes/Noの選択が入った途端、変数を0か1に制限する必要が出てきます。こうして一部の変数に整数制約を課した最適化問題を扱う枠組みが、混合整数計画法（Mixed Integer Programming; MIP）です。0-1のバイナリ変数（{0,1}しか取らない変数）を使えば、設備投資の可否からトラックのルート割り当てまで、現実の制約付き意思決定を数式のまま厳密に扱えます。

対象読者:

  • 数理最適化に興味があるエンジニアやデータサイエンティスト
  • 経営や業務の場面で、複雑な条件下の意思決定を支援する手法を探している方
  • Pythonを用いて最適化問題を解く方法を学びたい方

記事のポイント:

  • MIPの定式化と、厳密解法（分枝限定法、カット平面法）の考え方
  • PythonとOR-Toolsによるナップサック問題の実装
  • ソルバーの計算を速くする工夫（定式化の見直し、初期解、パラメータ調整）
  • サプライチェーン最適化、生産計画の自動化、価格最適化での導入事例

MIPの定式化と厳密解法

目的関数・制約条件・整数変数で問題を書く

MIPの定式化に必要な要素は3つです。最小化または最大化したい指標（コストや利益など）を線形関数で表した目的関数、「需要を満たす」「予算内に収める」といった満たすべき条件を線形の等式・不等式で書いた制約条件、そして解くべき決定変数です。決定変数の一部または全部に「整数でなければならない」という整数条件を課します。

例えば「利益を最大化する生産計画」なら、目的関数は総利益、制約は生産能力や予算、決定変数は各製品の生産量です。もし「ある製品を生産するかしないか」のようなYes/Noの選択が含まれれば、その変数は0/1のバイナリ変数としてモデル化します。整数変数で意思決定を表せるため、純粋な線形計画では扱えない組合せ最適化的な問題（工場を建設するか否かの選択、スタッフをシフトに割り当てる問題など）も定式化できます。

分枝限定法とカット平面法

混合整数計画問題を厳密に解く代表的な手法が、分枝限定法とカット平面法です。両者を組み合わせた分枝カット法が、現在のMIPソルバーの基本戦略になっています。

分枝限定法は、解きにくい問題を小さな部分問題に分割していく手法です。まず整数制約を無視した緩和問題（通常は線形計画問題）を解き、その解が整数条件を満たしていなければ、ある整数変数について取り得る値ごとに問題を分枝します。各枝では整数制約の一部を固定した部分問題を解き、そこで得られる目的関数値の上界・下界を使って「これ以上探索しても既に得られている解より良くならない」枝を打ち切ります。この限定の操作で探索を大幅に省略できます。

カット平面法は、線形緩和問題の解が整数にならない場合に、その非整数解を排除する新たな制約（カット）を追加していく手法です。追加した不等式制約は、元の問題の整数解集合を削ることなく連続緩和の実行可能領域だけを狭めるので、以降の探索が効率化されます。古典的にはGomoryカットなどが有名で、全ての変数が整数なら、理論上はカット平面法のみで有限ステップで最適解に到達できることも示されています。実際には分枝限定法と組み合わせ、適宜カットを入れて緩和問題の精度を高めながら探索する分枝カット法として使われるのが一般的です。

これらのアルゴリズムにより、MIPソルバーは膨大な組合せの中から効率的に最適解を探せます。それでも計算複雑性の壁は残ります。0-1変数がn個あれば、可能な組合せは理論上最大で2^n通りです。問題規模が少し大きくなるだけで候補解の数は指数的に増え、最悪の場合、計算量は指数時間になります。MIPは一般にNP困難で、問題によっては厳密解の計算が現実的に不可能なものも存在します。このため、高度な枝刈り戦略、新しいカット生成手法、発見的手法の組み込みといった高速化の工夫が今も続けられています。

ナップサック問題をOR-Toolsで解く

定式化を数式に落とす

Pythonでの実装例として、小さな0-1ナップサック問題を題材にします。各品物の価値と重量が与えられたとき、重量制限内で価値の合計を最大化する品物の選び方を求める問題です。各品物を選ぶ（1）か選ばない（0）かを決めるので、典型的な0-1整数計画問題として定式化できます。

品物 i の価値を viv_i、重量を wiw_i、ナップサックの許容量（重量上限）を WWとします。決定変数 xix_i を「品物 i を選ぶ場合1、選ばない場合0」とするバイナリ変数とすると、ナップサック問題は次のMIPで表せます。

目的関数は、選択した品物の総価値の最大化です。

max⁡∑ivixi\max \sum_{i} v_i x_i

制約条件は、選んだ品物の総重量が許容量以内に収まることです。

∑iwixi≤W\sum_{i} w_i x_i \le W

各変数は、品物を選ぶか否かの0-1変数です。

xi∈{0,1}∀ix_i \in \{0,1\} \quad \forall i

価値と重量のリスト、容量 WW を入力とすれば、最適な品物の組合せが解として得られます。

CP-SATソルバーで最適解を求める

Pythonには、最適化モデルを記述してソルバーに渡すライブラリがいくつかあります。ここではオープンソースのOR-Toolsを使って、先ほどのナップサック問題を解きます。事前にpip install ortoolsでライブラリをインストールしておきます。

from ortools.sat.python import cp_model

# データの定義（例として価値と重量のリスト、および許容量）
values = [10, 40, 30, 50]    # 各品物の価値
weights = [5, 8, 7, 12]      # 各品物の重量
W = 20                       # ナップサックの許容量
n = len(values)

# MIPモデルの構築
model = cp_model.CpModel()
x = [model.NewBoolVar(f'x{i}') for i in range(n)]  # 0-1変数 x_i を作成

# 制約：重さの合計が許容量Wを超えない
model.Add(sum(weights[i] * x[i] for i in range(n)) <= W)

# 目的関数：価値の合計を最大化
model.Maximize(sum(values[i] * x[i] for i in range(n)))

# ソルバーで最適化計算を実行
solver = cp_model.CpSolver()
status = solver.Solve(model)

# 結果の表示
if status == cp_model.OPTIMAL:
    selected_items = [i for i in range(n) if solver.Value(x[i]) == 1]
    optimal_value = sum(values[i] for i in selected_items)
    print(f"選択された品物: {selected_items}, 最適価値: {optimal_value}")

このコードは、OR-ToolsのCP-SATソルバーでMIPを解いています。model.NewBoolVar()で0-1の整数変数を作成し、model.Add(...)で制約、model.Maximize(...)で目的関数を設定します。最後にソルバーを実行し、得られた解から選択された品物のリストとその総価値を出力します。この例では 選択された品物: [1, 3], 最適価値: 90 と出力され、価値90を達成するには品物1と3を選ぶのが最適だと分かります。

大規模問題でソルバーを速くする工夫

現実の大規模問題にMIPを適用するときは、ソルバーの性能をどれだけ引き出せるかが実用性を左右します。

いちばん差が出るのは定式化です。大きなM値を用いる制約（いわゆるBig-M）は緩和問題を緩くし、計算を遅くする原因になるため、可能な限り厳密な定式化を選びます。不要な変数や制約は削除し、変数の取り得る範囲（下限・上限）は狭めて与えると、ソルバーの探索範囲を減らせます。

良い実行可能解（feasible solution）をあらかじめ持っているなら、初期解としてソルバーに読み込ませます。分枝限定法の上界・下界が早期に詰まり、探索木を大幅に縮小できることがあります。

ソルバーのパラメータ調整も選択肢です。許容ギャップ（最適解に対してどこまでの誤差を許すか）やタイムリミットを設定すれば、厳密最適にこだわらず、ある程度のところで計算を打ち切って近似解を得られます。現在の主流ソルバーはマルチスレッドにも対応しており、CPUコア数を増やすとほぼ線形に探索が速くなる場合もあります。

数値誤差にも注意が要ります。ソルバー内部では浮動小数点演算が行われるため、厳密に整数解が出るはずの変数がごく僅かに0や1からずれた値を出力する場合があります（例：変数x=1.0000002）。これは丸め誤差によるもので、実質的には整数とみなして差し支えありません。

業界別の導入事例

MIPソルバーの導入効果は、各社から具体的な数字とともに公開されています。業界別に3つ挙げます。

業界企業/事例成果
製造業Suzano社（ブラジル、製紙）サプライチェーン最適化により、約7,600万レアル（約76億円相当）の新たなビジネス機会を創出。物流ネットワークの最適化により、コスト削減と収益向上を両立し、持続可能性の向上にも寄与。
食品業ヨックモック CREA社（日本、洋菓子）日々の生産計画立案にMIPソルバー（Gurobi）を導入。手作業で行っていた計算が自動化され、年間600時間の工数削減に成功。
小売業欧州の大手スーパーマーケットチェーン価格戦略にMIPを活用。価格最適化の計算時間が従来の30分から数秒に短縮。

いずれも、手作業やルールベースで行っていた計画業務を定式化に置き換えた例です。効果が工数削減や計算時間の短縮という測れる形で出ている点は、導入を検討するときの説得材料になります。

おわりに

混合整数計画法は、解法の理論も実装環境も整った手法です。まずはナップサック問題のような小さな例をOR-Toolsで解き、そこに現実の制約を一つずつ足して定式化を育てていくのが、実務に載せる近道になります。

関連記事

← 技術ブログ一覧へ