1. はじめに
数理最適化は、与えられた制約条件の下で、最も効率的な解を見つけるためのアプローチであり、様々な分野で幅広く応用されています。特に、物流や製造、エネルギー管理、ポートフォリオ最適化といった領域では、資源の配分やコストの最小化、利益の最大化といった課題に対して有効な手段となります。
例えば、物流業界では、複数の倉庫から多くの顧客への配送ルートを最適化する「輸送問題」や、特定の条件下で商品の積載量を最大化する「ナップサック問題」などが数理最適化の代表的な例です。また、金融業界ではリスクとリターンのバランスを考慮した資産運用（ポートフォリオ最適化）も数理最適化によって効率的に行われています。
本記事では、google colabを使ってPython向けの数理最適化ライブラリ「mip」を用いて、こうした最適化問題をどのように解くことができるかを解説します。mipは、線形計画問題（LP）、整数計画問題（IP）、混合整数計画問題（MIP）といった様々な種類の問題を扱えるため、基礎から実践まで幅広く対応できます。また、mipの他にも最適化ライブラリとしてはPuLPやPyomoなどがありますが、本記事ではmipの特徴やメリットを活かした数理最適化の実践方法に焦点を当てて説明していきます。
2. 数理最適化の基礎
数理最適化とは
数理最適化は、数式を用いて現実の問題をモデル化し、与えられた制約条件の下で最適な解（目的関数の最大化または最小化）を見つけるための手法です。目的関数は、問題の目標を数値的に表現したものであり、制約条件はその目標を達成する際の制限事項やルールを示します。
例えば、製造業における生産計画では、製品の生産コストを最小化しながら需要を満たすことが求められます。この場合、目的関数は生産コストの最小化、制約条件は生産能力や需要量となります。数理最適化を用いることで、これらの条件を満たす最適な生産量を計算で求めることができます。
線形計画問題（LP）、整数計画問題（IP）、混合整数計画問題（MIP）の説明
数理最適化には、扱う変数や制約条件の性質によっていくつかの種類があります。以下に主要なものを紹介します。
線形計画問題（Linear Programming, LP）
線形計画問題は、目的関数と制約条件がすべて線形で表現される最適化問題です。変数は連続的な実数値を取り、目的関数と制約条件は一次式（変数の一次項のみ）で構成されます。LPは計算効率が高く、大規模な問題でも解くことが可能です。
例: 資源の配分問題で、複数の製品を生産する際の利益を最大化するために、各製品の生産量を決定する。
整数計画問題（Integer Programming, IP）
整数計画問題は、すべての変数が整数値を取るように制約された最適化問題です。特に0または1の値しか取らない場合を0-1整数計画問題と呼びます。変数の整数性により、問題は非線形性や組合せ的な複雑性を帯び、解くのが難しくなります。
例: 工場の稼働日数を最適化する問題で、各工場が稼働するか否かを決定する（0-1整数変数を使用）。
混合整数計画問題（Mixed Integer Programming, MIP）
混合整数計画問題は、連続変数と整数変数の両方を含む最適化問題です。これにより、より複雑で現実的な問題をモデル化できます。MIPはLPとIPの性質を兼ね備えており、解くのに高度なアルゴリズムと計算資源が必要です。
3. mipライブラリの紹介
mipライブラリとは
mip（Mixed Integer Programming）ライブラリは、Pythonで数理最適化問題を解くための強力なツールです。線形計画問題（LP）、整数計画問題（IP）、混合整数計画問題（MIP）を含む多様な最適化問題を解くために設計されており、GurobiやCBC（Coin-or branch and cut）といった高度なソルバーとの互換性を持つため、効率的に最適解を得ることができます。
mipはPythonのオブジェクト指向設計を活かし、シンプルかつ直感的にモデルを構築できる点が特徴です。また、商用利用も可能なオープンソースライブラリであるため、教育機関や企業において幅広く活用されています。
他の最適化ライブラリ（PuLP、Pyomo）との比較
数理最適化のためのPythonライブラリには、mipの他にも代表的なものとしてPuLPやPyomoがあります。以下にこれらのライブラリとの比較を示します。
| ライブラリ | 特徴 | 適した問題 |
|---|---|---|
| mip | 直感的な設計、Gurobiなどのソルバーと連携可能 | LP、IP、MIP |
| PuLP | シンプルで学習しやすい、LPに特化 | 主にLP |
| Pyomo | 数理モデルの記述力が高い、大規模問題にも対応 | LP、IP、MIP、非線形問題 |
PuLPは主に線形計画問題（LP）向けの軽量なライブラリで、簡単なLPをすぐに試したい場合に向いていますが、整数計画や混合整数計画にはやや制約があります。
Pyomoは、Pythonで非常に強力なモデリング機能を提供し、LPやMIPに加えて、非線形最適化にも対応しています。ただし、記述が複雑になりやすく、学習コストが高いのが難点です。
これに対して、mipはLPからMIPまで幅広く対応しつつ、比較的簡潔な記述で問題を定式化できるため、入門から実用的な最適化まで幅広く活用できるバランスの良いライブラリです。
4. 環境構築
Google Colabでは、必要なパッケージをpipでインストールできます。mipライブラリも同様にpipコマンドを用いて簡単にインストール可能です。
mipライブラリのインストール
Google Colabのセルで以下のコマンドを実行してください。
!pip install mip
このコマンドを実行することで、mipライブラリがColab環境にインストールされます。インストール完了後、再起動の指示が表示されたらしたがってノートブックを再起動してください。
5. 基本的な使い方
ここでは、Google Colab上でmipライブラリを使用して基本的な最適化問題を定式化し、解く方法について説明します。例題として、簡単な線形計画問題を解いてみます。
例題：簡単な線形計画問題の定式化
製品A、製品Bを製造する工場があり、以下の条件を満たす製造計画を立てたいとします。
- 製品Aの利益は1,000円、製品Bの利益は3,500円
- 製品Aと製品Bの製造にはそれぞれ1時間と3時間の作業が必要
- 総作業時間は10時間以内
- この場合、「総利益を最大化する」ことが目的関数となり、作業時間の制約が制約条件となります。
手順1: ライブラリのインポートとモデルの作成
まず、mipライブラリをインポートし、最大化問題として最適化モデルを作成します。
from mip import Model, xsum, maximize, BINARY
# モデルを初期化
model = Model()
手順2: 変数の定義
製品Aと製品Bの製造量を示す変数を定義します。ここでは、製品Aの製造量をx、製品Bの製造量をyとします。
# 変数を定義（変数を非負の値に制約、整数型で指定）
x = model.add_var(name="x", lb=0, var_type="I")
y = model.add_var(name="y", lb=0, var_type="I")
手順3: 目的関数の定義
次に、製品Aと製品Bの総利益を最大化するための目的関数を設定します。利益は製品Aが1,000円、製品Bが3,500円です。
# 目的関数を設定
model.objective = maximize(x * 1000 + y * 3500)
手順4: 制約条件の定義
ここでは、製品A(作業時間:1時間)と製品B(作業時間:3時間)の製造に必要な総作業時間の合計が10時間以内であるという制約を追加します。
# 制約条件を追加
model += x + 3 * y <= 10
手順5: 問題の解法と結果の取得
設定が完了したら、optimize()メソッドを使って最適化を実行し、結果を取得します。
# 最適化を実行
model.optimize()
# 結果の表示
if model.num_solutions:
print(f"製品Aの製造量: {x.x}")
print(f"製品Bの製造量: {y.x}")
print(f"最大利益: {model.objective_value}")
出力
製品Aの製造量: 1.0
製品Bの製造量: 3.0
最大利益: 11500.0
上記のコードにより、製品Aと製品Bの最適な製造量と、それに対応する最大利益が表示されます。
解説
- add_varメソッドで変数を定義し、lb=0で非負の制約を追加しています。
- 目的関数と制約条件は、+=演算子を使用してモデルに追加します。
- optimize()メソッドで最適化を実行し、解が存在する場合に変数の値や目的関数値を取得します。
6. 実践的な例題
ナップサック問題とは
ナップサック問題は、与えられた容量の中で選ぶべきアイテムを決定し、価値の合計を最大化する最適化問題です。この問題は、「容量制約のある中での選択」というシンプルな設定にもかかわらず、実用的な応用が多いことで知られています。例えば、次のような場面で応用されています。
- 物流業界：限られたスペースにどの商品を詰めるべきかを決定する問題
- 投資計画：予算制約の下で、どのプロジェクトに資金を割り当てるかを決定する問題
- バックパックの荷造り：限られたバックパックの容量に、どの物品を持っていくか決める問題
ナップサック問題には、選択肢が連続値や整数値の場合や、複数の制約条件がある場合など、さまざまなバリエーションがあり、それぞれが異なる難しさと解法の特徴を持っています。本記事では、シンプルな0-1ナップサック問題（各アイテムを「選ぶか選ばないか」を決定する問題）に焦点を当てて解説します。
ナップサック問題を解説
問題設定
次のような条件でナップサック問題を解きます。
- 容量：ナップサックの最大容量は15kgです
- アイテム：以下の6種類のアイテムがあり、それぞれの重さと価値が設定されています
- 選択できるアイテムの数：アイテムは１種類につき１つのみで、同じアイテムを複数選択することはできません
| アイテム名 | 重さ(kg) | 価値(円) |
|---|---|---|
| アイテム１ | 1 | 1000 |
| アイテム２ | 3 | 3500 |
| アイテム３ | 4 | 5000 |
| アイテム４ | 5 | 6200 |
| アイテム５ | 6 | 7800 |
| アイテム６ | 8 | 10000 |
この問題の目的は、ナップサックに入れるアイテムの価値を最大化することです。選択できるアイテムの重さの合計が15kgを超えないようにしながら、価値が最大になる組み合わせを求めます。
コード
Google Colab上で以下のコードを実行すると、mipライブラリを使用してナップサック問題を解くことができます。
ライブラリのインポートとモデルの作成、変数の設定
from mip import Model, xsum, maximize, BINARY
# モデルの作成（最大化問題）
model = Model()
# アイテムのデータ
weights = [1, 3, 4, 5, 6, 8] # 各アイテムの重さ
values = [1000, 3500, 5000, 6200, 7800, 10000] # 各アイテムの価値
n = len(weights) # アイテムの数
# バイナリ変数の定義（選ぶ:1、選ばない:0）
x = [model.add_var(var_type=BINARY) for i in range(n)]
目的関数の定義
# 目的関数を設定（選択したアイテムの価値の合計を最大化）
model.objective = maximize(xsum(values[i] * x[i] for i in range(n)))
制約条件の定義
# ナップサックの容量制約（選択したアイテムの重さの合計 <= 15）
model += xsum(weights[i] * x[i] for i in range(n)) <= 15
問題の解法と結果の取得
# 最適化を実行
model.optimize()
# 結果の表示
if model.num_solutions:
print("選択するアイテム:")
for i in range(n):
if x[i].x >= 0.99: # 変数が1に近い場合、そのアイテムを選択
print(f"アイテム {i+1} (重さ: {weights[i]}kg, 価値: {values[i]}円)")
print(f"最大価値: {model.objective_value}円")
出力
選択するアイテム:
アイテム 3 (重さ: 4kg, 価値: 5000円)
アイテム 4 (重さ: 5kg, 価値: 6200円)
アイテム 5 (重さ: 6kg, 価値: 7800円)
最大価値: 19000.0円
7. まとめ
本記事では、Pythonのmipライブラリを用いて数理最適化の基本的な考え方から実践的な例題までを解説しました。数理最適化は、物流や製造、金融といった幅広い分野で効率的なリソース配分や意思決定を支える重要な技術です。
ナップサック問題のように、選択の最適化は単純な構造でも非常に有用で、拡張性も高い問題です。mipライブラリを活用することで、ナップサック問題以外の複雑な最適化にも対応できるようになります。Pythonのmipライブラリはシンプルでありながら強力なツールであるため、ぜひ様々なシナリオで活用してみてください。
最後にここまで読んでいただき、ありがとうございました。