Python-MIPによるモデル作成方法¶
Pythonで線形最適化をするには、Python-MIPライブラリーを使用します。 Python-MIPは「COIN-ORプロジェクトのPuLP」に触発されて開発されました。そのため、使い勝手はPuLPに似ています。
参考
Python-MIPのインストール¶
コマンドプロンプトで、pip install -U mipでできます。
M1/M2チップでPython-MIPをインストールする場合は、次を参照してください。
モデル作成の手順¶
モデル（
Model）の作成変数の作成
目的関数の設定
制約条件の追加
※ 3と4の順番は逆でも構いません。また、3や4が存在しなくても構いません。
問題とモデルの違い¶
問題には、2種類の意味があります。
解決したいと思っている課題（目標と現実の違い）。
答えを想定している問い。試験の問題など（最短路問題のように名前がついている問題の多くは、こちらの意味）。
「数理的アプローチによる問題解決」の問題は、前者になります。
一方で、モデルは問題をPCなどで扱えるように表現したものです。
問題とモデルの違いについては、変えることを考えると、わかりやすいかもしれません。
モデルを変えること：「変数や目的関数や制約条件」を捉え直すことです。解決したいと思っていることを変えることではありません。
問題を変えること：目標や現実の捉え方を変えることです。リフレーミングなどがあります（リフレーミング - wikipedia）。
モデルの作成¶
準備として、下記をimportしたとします。
from mip import Model, maximize, minimize, xsum
m = Model(モデルの名前)とすることで、モデルを作成します。モデルの名前は省略可能です。
モデルには、最小化と最大化の2種類あります。 Python-MIPでは、下記の2通りの指定方法があります。
モデルの作成時に指定
目的関数の設定時に指定
どちらを使っても良いのですが、目的関数で指定する方をお勧めします。 理由は、モデルの種類が、目的関数を見るだけで判断できるからです。 もし、モデルの作成時に指定すると「モデルと目的関数」の2箇所を見ないといけません。
目的関数でモデルの種類を指定する方法¶
最小化：
m.objective = minimize(式)とします。最大化：
m.objective = maximize(式)とします。
モデルの種類（最小化か最大化）は、m.senseで確認できます。
m.objective = 式の場合、モデルの種類はモデルの設定を用います。また、モデルで設定しないとデフォルトでは「最小化」になります。
通常は、minimizeかminimizeを明示した方がわかりやすいでしょう。
理由は、無指定だとモデルを見ないと、モデルの種類がはっきりしないからです。
変数作成¶
変数とは、意思決定の対象です。具体例を上げてみましょう。
自宅から学校への最短路を求めたい場合の変数：各経路を通るかどうか
生産額を最大化したい場合の変数：製品ごとの生産量
輸送費用を最小化したい場合の変数：経路ごとの輸送量
変数の種類は、以下の3種類あります。 Python-MIPでは、デフォルトで連続変数になります。 線形最適化では、連続変数だけ使います。
連続変数：実数値を表す変数です。
0-1変数：0または1のみを表す変数です。
整数変数：整数値を表す変数です。
変数の作成方法¶
Python-MIPでは、モデルオブジェクトを使って変数を作成します。
モデルオブジェクトをmとすると、m.add_var(...)またはm.add_var_tensor(...)で変数を作成します。
add_varの主な引数¶
add_varで変数を1つ作ります。主な引数は以下の通りです。
第1引数（
name）：変数名（デフォルトは''）第2引数（
lb）：変数の値のとりうる下限（デフォルトは0）第3引数（
ub）：変数の値のとりうる上限（デフォルトはmip.INF）第4引数（
obj）：目的関数の係数（デフォルトは0）第5引数（
var_type）：変数の種類（デフォルトはmip.CONTINUOUS）
※ 変数名は指定しなくても構いません。変数名を出力したい場合は指定します。
※ mip.INFはfloat('inf')と同じです。
※ mip.CONTINUOUSは連続変数を意味しています。
変数の作成例
m.add_var('x')：非負変数を作成します。非負変数とは、0から∞までの値を取れる変数です。m.add_var('y', lb=-INF)：自由変数を作成します。自由変数とは、-∞から∞までの値を取れる変数です。m.add_var('z', lb=0, ub=1)：上下限のある変数を作成します。範囲は、lbの値からubの値までです。
add_var_tensorの主な引数¶
引数は以下の通りです。
第1引数：形状（タプル）
第2引数：変数名
その他：
add_varの引数も使えます。
※ 第1引数と第2引数は省略できません。
1次元の場合：形状として
(3,)と指定すると、要素数3個の1次元配列になります。形状はタプルでないといけません。
(3)はタプルでないのでエラーになります。
2次元の場合：形状として
(2, 3)と指定すると、要素数6個（=2*3）の2次元配列になります。
目的関数の設定¶
目的関数とは、どうしたいかを決める関数です。具体例を上げてみましょう。
自宅から学校への最短路を求めたい場合の目的関数：経路の距離
生産額を最大化したい場合の目的関数：総生産額
輸送費用を最小化したい場合の目的関数：総輸送費用
目的関数は、モデル（以下ではm）の種類（最大化／最小化）に応じて、以下のように設定します。
最小化の場合：
m.objective = minimize(式)最大化の場合：
m.objective = maximize(式)
※ モデルの種類はモデルが管理しています。上記のように設定することでモデルが管理するモデルの種類が変更されます。
※ m.objective = 式とすると、モデルが管理するモデルの種類は変わりません。モデルの種類をわかりやすくするためには、上記の記述方法をお勧めします。
※ m += 式としても目的関数を設定します。しかし、これは制約条件の記述方法と間違えやすいです。m += minimize(式)はエラーになるので、上記の記述方法の方が間違いに気づきやすくなります。
※ モデルの種類は、m.senseで確認できます。
式の書き方¶
変数や定数を使った足し算や引き算が使えます。変数を使う掛け算は
2 * xのような定数と変数の掛け算だけ使えます。1 / xやx * xやx * yのような式は使えません。xが多次元配列の場合も掛け算できます。その場合、ブロードキャストして要素ごとに計算されます。ブロードキャストについては、「ブロードキャスト - PyQドキュメント」を参照ください。
xを変数のリスト（あるいは1次元配列）とします。そのリストの合計はxsum(x)のように記述します。「x[0]+x[1]+…+x[-1]」と同じですが、効率的に計算してくれます。xsumはsumと同じように使えますが、sumより高速に計算できます。
aを定数のリストとします。aとxの内積（a[0] * x[0]+a[1] * x[1]+…+a[-1] * x[-1]）は、xsum(a_i * x_i for a_i, x_i in zip(a, x))のように記述します。
xsumについて¶
xsumの代わりにsumを使っても、同様に合計できます。しかし、sumは非効率的なのでxsumを使うようにしましょう。
たとえば、xの要素数がnのとき、sum(x)はn**2に比例するメモリと計算時間を使います。
xsum(x)であれば、nに比例するメモリと計算時間で済みます。
xsumは「要素が式のイテラブル」でも使えます。たとえば、xsum(a_i * x_i for a_i, x_i in zip(a, x))のような記述が可能です。
制約条件の追加¶
制約条件とは、守らなければならないことを指定します。具体例を上げてみましょう。
自宅から学校への最短路を求めたい場合の制約条件：選んだ経路が、自宅から学校まで接続していること。
生産額を最大化したい場合の制約条件：使用する原料が、原料の在庫以下であること。
倉庫から工場への輸送費用を最小化したい場合の制約条件：倉庫から出荷する総量が供給量以下であること。工場への入荷する総量が需要量以上であること。
制約条件の書き方 制約条件は、以下の3種類の書き方ができます。式1と式2の片方は定数でも構いません。
m += 式1 >= 式2
m += 式1 == 式2
m += 式1 <= 式2
下記の3種類の書き方は実行エラーになります。
m += 式1 > 式2
m += 式1 < 式2
m += 式1 != 式2
※ m += 式はエラーにならずに、式を目的関数に設定します。注意しましょう。
多次元配列の制約条件¶
Python-MIPでは、下記のように1次元配列（ベクトル）や多次元配列（テンソル）を使って制約条件を記述できます。
m += x <= 10
上記は1つの制約条件ですが、下記のようにforで記述したのと同じ意味になります。
for x_i in x:
m += x_i <= 10
つまり、m += 多次元配列は、多次元配列の各要素に対して制約条件を追加します。
制約条件の書き方は非常にシンプルなルールですが、実に多彩な関係を表現できます。
Python-MIPでのソルバーの実行¶
m.optimize()を呼ぶことで、指定されたソルバー※を実行し結果が設定されます。
※ デフォルトのソルバーはCBCです。
ソルバーは、数理モデルを入力とし、最適解を計算して、結果を返すソフトウェアです。 結果は、モデルや変数や目的関数などのプロパティに設定されます。
m.optimizeのオプション¶
ソルバーを実行するときにオプションを指定できます。以下によく使うオプションを紹介します
max_seconds：ソルバーの実行時間の上限を秒で指定します。relax：Trueを設定すると、変数をすべて連続変数とみなします。
ステータスの確認¶
実行した結果のステータスコードは、m.statusで数値で確認できます。
ステータスの全種類は、list(mip.OptimizationStatus)で確認でき、以下の通りです。
[<OptimizationStatus.ERROR: -1>,
<OptimizationStatus.OPTIMAL: 0>,
<OptimizationStatus.INFEASIBLE: 1>,
<OptimizationStatus.UNBOUNDED: 2>,
<OptimizationStatus.FEASIBLE: 3>,
<OptimizationStatus.INT_INFEASIBLE: 4>,
<OptimizationStatus.NO_SOLUTION_FOUND: 5>,
<OptimizationStatus.LOADED: 6>,
<OptimizationStatus.CUTOFF: 7>,
<OptimizationStatus.OTHER: 10000>]
ソルバーの指定方法¶
単にPython-MIPをインストールしただけの場合、使えるソルバーはCBCだけです。 別途、Gurobi（有料）などをインストールし必要な設定を行うと、以下のようにソルバーを指定できます。
from mip import Model, CBC, GUROBI
for solver_name in [CBC, GUROBI]:
try:
m = Model(solver_name=solver_name)
except:
print(f'{solver_name}は使えません')
参考
変数や式や目的関数の値の確認¶
変数や式の値は、オブジェクト.xで確認できます。
目的関数の値はm.objective_valueで確認できます。
多次元配列の変数.astype(float)とすることで、その変数の値の多次元配列を取得できます。
