混合整数計画法（MIP）の理論と実践 - デジタルリアクタ合同会社

Contents

はじめに
MIPの基本と解法のポイント
- MIPの基本概念と定式化
- 分枝限定法とカット平面法
モデル実装のポイント（Python）
事例と成果のポイント
おわりに

はじめに

混合整数計画法（Mixed Integer Programming; MIP）は、数理最適化問題の一種であり、一部の変数に整数制約を課した最適化問題を指します。線形計画問題（Linear Programming; LP）では変数は連続値（実数）を取りますが、MIPでは「いくつかの変数は整数でなければならない」といった制約を加えることで、より複雑な状況をモデル化できます。特に、0-1のバイナリ変数（{0,1}しか取らない変数）を使用することで、「ある設備を導入するかしないか」や「トラックをこのルートに割り当てるか否か」など、Yes/Noの意思決定を数式に組み込むことができます。このバイナリ変数の導入により表現力が飛躍的に高まり、現実の様々な制約付き意思決定問題を厳密に表現できる点がMIPの大きな魅力です。

この記事を書いたひと

デジタルリアクタ合同会社代表
望月優輝 / Yuki Mochizuki

機械学習・統計、数値計算などの領域を軸としたソフトウェアエンジニアリングを専門としています。スタートアップからグローバル企業まで、さまざまなスケールの企業にて、事業価値に直結する計算システムを設計・構築してきました。主に機械学習の応用分野において、出版・発表、特許取得等の実績があり、また、IT戦略やデータベース技術等の情報処理に関する専門領域の国家資格を複数保有しています。九州大学理学部卒業。日本ITストラテジスト協会正会員。

対象読者:

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

記事のポイント:

MIPの基本的な概念、定式化、および解法（分枝限定法、カット平面法）を解説
PythonとOR-Toolsを用いたMIPモデルの実装例（ナップサック問題）を紹介
MIPソルバーの性能を引き出すためのポイント（モデル化の工夫、初期解の提供、パラメータ調整など）を解説
サプライチェーン最適化、生産計画の自動化、価格最適化など、MIPの具体的な適用事例を紹介

MIPの基本と解法のポイント

MIPの基本概念と定式化

MIPは、数理最適化問題として以下の形式で定式化されます。

目的関数: 最小化または最大化したい指標（コスト、利益など）を線形関数で表現します。
制約条件: 問題が満たすべき条件を線形の等式、不等式で表します（例：「需要を満たす」「予算内に収める」など）。
決定変数: 解くべき変数を表します。一部または全部の変数に対し「整数でなければならない」という整数条件を課します。

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

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

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

分枝限定法: 解きにくい問題を小さな部分問題に分割していく手法です。まず、整数制約を無視した緩和問題（通常は線形計画問題）を解き、その解が整数解を満たしていなければ、ある整数変数について取り得る値ごとに問題を分枝します。各枝では整数制約の一部を固定した部分問題を解きますが、このとき得られる目的関数値の上界、下界を利用して、「それ以上探索しても既に得られている解より良くならない」枝を限定することで探索を大幅に省略します。
カット平面法: 線形緩和問題の解が整数解にならない場合に、その非整数解を排除する新たな制約（カット）を追加していく手法です。追加された不等式制約は、元の問題の整数解集合を削ることなく、連続緩和の解可能領域を狭め、以降の探索を効率化します。古典的にはGomoryカットなどが有名で、理論上は全ての変数が整数の場合、カット平面法のみで有限ステップで最適解に到達できることも示されています。実際には分枝限定法と組み合わせ、適宜カットを入れることで緩和問題の精度を高めながら探索を行う分枝カット法として用いられるのが一般的です。

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

モデル実装のポイント（Python）

問題設定とモデル構築例

ここでは、Pythonを用いた混合整数計画モデルの具体例として、シンプルな0-1ナップサック問題を題材にします。ナップサック問題は、「各品物の価値と重量」が与えられたときに、重量制限内で価値の合計を最大化するような品物の選び方を求める問題です。これは、典型的な0-1整数計画問題（各品物を選ぶ（1）か選ばない（0）か）に定式化できます。

モデル定式化：
品物 i の価値を $v_i$ 、重量を $w_i$ 、ナップサックの許容量（重量上限）を $W$ とします。決定変数 $x_i$ を「品物 i を選ぶ場合1、選ばない場合0」とするバイナリ変数とすると、ナップサック問題は次のMIPで表せます。

目的関数（選択した品物の総価値を最大化）：

 $\max \sum_{i} v_i x_i$

制約条件（選んだ品物の総重量が許容量以内）：

 $\sum_{i} w_i x_i \le W$

変数（各品物を選ぶか否かの整数変数）：

 $x_i \in \{0,1\} \quad \forall i$

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

PythonによるMIPモデル実装例

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）。これは丸め誤差によるもので、実質的には整数とみなして差し支えありません。

事例と成果のポイント

混合整数計画法は、既に多くの企業や研究機関で導入され、その効果が報告されています。以下に業界別の具体的な事例を紹介します。

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

これらの事例は、適切にモデル化しソルバーを活用すれば、MIPが高い投資対効果を生み出すことを示しています。

おわりに

混合整数計画法（MIP）は、理論と実践が密接に結びついた強力なツールです。データサイエンティストやエンジニアの方は、ぜひ一度小さな最適化問題からMIPソルバーを使ってみて、その有効性を実感してください。

お気軽にご相談ください！

弊社のデジタル技術を活用し、貴社のDXをサポートします。

基本的な設計や実装支援はもちろん、機械学習・データ分析・3D計算などの高度な技術が求められる場面でも、最適なソリューションをご提案します。

初回相談は無料で受け付けております。困っていること、是非お聞かせください。

サービスの詳細はこちら

お問い合わせフォームへ