Zenn
🧮

Python-MIP入門

2025/04/01に公開
Python
数理最適化
tech

1 始めに

この記事はPython-MIPの初歩について解説したものになります。
今回このモジュールについて勉強する機会があり、自分用の備忘録としてまとめてみました。

mipモジュールはドキュメント[1]のトップページで以下のように紹介されています。

原文 :

Python-MIP is a collection of Python tools for the modeling and solution of Mixed-Integer Linear programs (MIPs). Its syntax was inspired by Pulp, but our package also provides access to advanced solver features like cut generation, lazy constraints, MIP starts and solution pools.

ChatGPT翻訳 :

Python-MIP は、混合整数線形計画問題（MIP）のモデル化と解法のための Python ツール群です。その構文は Pulp に影響を受けていますが、本パッケージではカット生成、遅延制約、MIP スタート、ソリューションプールなどの高度なソルバー機能にもアクセスできます。

まずは入門というところで、公式ドキュメントのQuick Startをみながら内容の一部を自分用に再編しました。どなたかの参考になれば幸いです。

2 Quick Start(自分用)

2.1 問題定義

今回は、以下の線形計画問題を解こうと思います。
問題は「高校数学の美しい物語」[2]というサイトに掲載されているものを使用しました。

\begin{aligned} \text{maximize} \quad & 4x + 5y \\ \text{subject to} \quad & x \geq 0, \\ & y \geq 0, \\ & x + y \leq 3, \\ & x + 2y \leq 4. \end{aligned}

2.2 モデル定義

まずはモジュールをインポートします。

import mip

次に、問題を解くためのモデルを定義します。

model = mip.Model(name="sample_problem", solver_name=mip.CBC)

引数solver_nameでは、求解時に使用するソルバーを指定します。
引数nameはモデルの名前を付けています。
省略も可能で、名前を参照することもできます。

print(model.name)
# 'sample_problem'

2.3 変数追加

使用する変数を定義します。

I = [1, 2]
x = {}
for i in I:
    x[i] = model.add_var(name=f"x_{i}", var_type=mip.CONTINUOUS)

add_varメソッドによって変数を追加します。
このメソッドは作成された変数オブジェクトを返しますので、上記のようにxという辞書に変数を登録して、
後に参照しやすくすることができます。
モデルインスタンスから取得することも可能です。

print(x[1] is model.vars["x_1"], x[1] is model.var_by_name("x_1"))
# True True

定義された変数の数は、以下のように2つの方法で取得できます。

print(len(model.vars), model.num_cols)
# 2 2

add_varメソッドの引数について解説します

  • name : 変数を取得するときの名前。省略可。
  • lb : 変数の下限であり、変数の範囲がこの値以上に制限される。デフォルトは0。
  • ub : 変数の上限であり、変数の範囲がこの値以下(未満ではない)に制限される。デフォルトはinf。
  • var_type : 変数の型。mip.CONTINUOUS、mip.BINARY、mip.INTEGERか、それぞれの頭文字の文字列で指定可能。

ここで定義される変数は、Varクラスのインスタンスになります。
add_varの引数で使用した値はインスタンスからもアクセス可能です。

print(x[1].name, x[1].lb, x[1].ub, x[1].var_type)
# x_1 0.0 inf C

ちなみに、x[1].ubの値（デフォルト値を使用したもの）はPythonのfloat型の最大値と等しいようです。

import sys
print(sys.float_info.max == x[1].ub)
# True

他にも変数からは以下属性にアクセスできます。

  • model : 変数が登録されているモデル。
  • x : 数理最適化問題の解。まだ求解していない場合はNone。
print(x[1].model is model, x[1].x)
# True None

2.4 制約追加

変数の制約を追加します。
制約は2つありますが、それぞれ違う方法で書いてみます。

a = {}
a[1, 1], a[1, 2] = 1, 1
a[2, 1], a[2, 2] = 1, 2

b = {}
b[1] = 3
b[2] = 4

model += a[1, 1] * x[1] + a[1, 2] * x[2] <= b[1], "constr_1"
model.add_constr(mip.xsum(a[2, i] * x[i] for i in I) <= b[2], name="constr_2")

+=演算子またはadd_constrメソッドによって変数を追加します。
それぞれ制約の名前を指定することができますが、どちらの方法でも名前は省略可能です。

次のように2つの方法でモデルインスタンスから制約を取得できます。

constr_2 = model.constr_by_name("constr_2")
print(model.constrs["constr_2"] is model.constr_by_name("constr_2"))
# True

制約はConstrクラスのインスタンスになります。
制約の内容はLinExprオブジェクトによって表現され、Constrオブジェクトのexpr属性から確認できます。

print(
    type(constr_2),
    type(3 * x[1] + 4 * x[2] <= 3),
    type(constr_2.expr),
    constr_2.expr,
    sep = "\n"
)
# <class 'mip.entities.Constr'>
# <class 'mip.entities.LinExpr'>
# <class 'mip.entities.LinExpr'>
# + x_1 + 2.0x_2  <= 4.0

name属性で制約名にアクセスすることも可能です。

print(constr_2.name)
# constr_2

定義された制約の数はこのように2つの方法で取得できます。

print(len(model.constrs), model.num_rows)
# 2 2

2.5 目的関数・最大最小化定義

目的関数と最大最小化のどちらをするのかを定義します。

c = {}
c[1] = 4
c[2] = 5
model.objective = mip.xsum(c[i] * x[i] for i in I)
model.sense = mip.MAXIMIZE
print(model.objective)
# + 4.0x_1 + 5.0x_2

目的関数はLinExprオブジェクトで定義されます。

2.6 最適化実施

最適化を実施します。

status = model.optimize()
print(status, status.value)
# OptimizationStatus.OPTIMAL 0

最適化はoptimizeメソッドによって実行します。
帰り値はmip.OptimizationStatusクラスであり、最適化実行終了時のステータスを示しています。
今回表示されたOptimizationStatus.OPTIMALは最適解が発見できたことを表しています。
ステータス一覧配下となります。

  • 基本ステータス
    • ERROR = -1 : エラー発生
    • OPTIMAL = 0 : 最適解が計算された
    • INFEASIBLE = 1 : 実行可能解が存在しなかった。
    • UNBOUNDED = 2 : 目的関数に現れる1つ以上の変数が束縛制約に含まれず、最適目的値が非有界となった。
  • 整数変数を持つ場合のステータス
    • FEASIBLE = 3 : 探索中に整数の実行可能解が見つかったが、これが最適解かどうかを結論づける前に探索が終了した。
    • INT_INFEASIBLE = 4 : 緩和線形問題には実行可能解が存在するが、整数解が存在しない。
    • NO_SOLUTION_FOUND = 5 : 最適化の過程で整数解が見つからなかった。
  • その他ステータス
    • LOADED = 6 : 問題は読み込みされたが、最適化は実行されなかった
    • CUTOFF = 7 : 現在のカットオフには実行可能な解が存在しなかった。

2.7 結果確認

最適化の実行結果、変数・目的変数の値がどのようになったか確認してみます。

for i in I:
    print(f"var_idx :{i},  value : {x[i].x}")
print(f"objective_value : {model.objective_value}")
# var_idx :1,  value : 2.0
# var_idx :2,  value : 1.0
# objective_value : 13.0

目的関数の値は以下の方法でも確認可能です。

print(model.objective.x)
# 13.0

2.8　その他

LinExprオブジェクトで役に立ちそうな属性をまとめておきます。

  • model : このオブヘクトが参照するモデル。変数がない場合はNone。
  • sense : 制約の場合、その等式・不等式（=,<,>)。等式・不等式でなければ空文字。
  • violation : 式中の変数の値が利用可能な場合、現在の変数の値に対する制約の違反量。利用可能でない場合はNone

3 最後に

以上、自分なりにPython-MIPについてまとめてみました。
簡略化してしまったところも多くあるので、機会があればまた別の記事でご紹介できればと思います。

4 参考資料

[1] Python-MIPドキュメント : https://www.python-mip.com/
[2] 高校数学の美しい物語 領域における最大・最小問題（線形計画法）: https://manabitimes.jp/math/930

Discussion