Python MIPについて現役エンジニアが解説【初心者向け】

初心者向けにPython MIPについて解説しています。MIPを使うことで最適化問題の答えを導き出すことができます。MIPライブラリのインストール方法とナップザック問題による使用例を見ていきましょう。

TechAcademyマガジンは受講者数No.1のオンラインプログラミングスクールTechAcademy [テックアカデミー]が運営。初心者向けに解説した記事を公開中。現役エンジニアの方はこちらをご覧ください。

Python MIPについて、TechAcademyのメンター(現役エンジニア)が実際のコードを使用して初心者向けに解説します。そもそもPythonについてよく分からないという方は、Pythonとは何なのか解説した記事を読むとさらに理解が深まります。

 

なお本記事は、TechAcademyのオンラインブートキャンプPython講座の内容をもとに紹介しています。

 

田島悠介

今回は、Pythonに関する内容だね!

大石ゆかり

どういう内容でしょうか?

田島悠介

MIPについて詳しく説明していくね!

大石ゆかり

お願いします!

目次

 

Python MIPとは

Python MIPパッケージはPythonで混合整数計画問題(MIP)をモデル化したツールです。混合整数計画問題とは、整数値を取る変数と実数値を取る変数が混在している整数計画問題のことをいいます。

特徴としては、CFFIを使ってソルバーのライブラリを直接呼び出しているため速度が早いことです。Pythonで最適化問題を解くときに使われるライブラリの一つです。

 

[PR] Pythonで挫折しない学習方法を動画で公開中

Python MIPの使い方

PythonのMIPライブラリは以下のpipコマンドでインストールできます。

pip install mip

モデルの作成は以下の1行で行います。

model = mip.Model()

add_ver()メソッドを使えば決定変数がモデルに追加されるようになります。

x = model.add_var()

また、以下の書き方で目的変数のベクトルを簡単に作成することができます。

y = [model.add_var(var_type=mip.BINARY) for i in range(10)]

さらに目的関数を設定するには、model.objectiveで設定できます。

model.objective = mip.xsum(c[i]*x[i] for i in range(n))

最後に以下の1行で問題の最適化を行います。

model.optimize()

次の項目で実際にサンプルコードを使って最適化問題を解いてみましょう

 

実際に使ってみよう

それでは、サンプルコードを動かしてみましょう。

今回は最適化問題の定番のナップザック問題を解いてみます。ナップザック問題とは、制限された荷物の重さの中で最大の価値になるような組み合わせを解く問題です。

以下のコードを適当なディレクトリに保存します。

from mip import Model, xsum, maximize, BINARY

# 重さ
w = [2, 1, 3, 2, 1, 4]
# 価値
v = [3, 2, 6, 1, 3, 8]

# 限度:10kg
W = 10
r = range(len(w))

m = Model('knapsack')
x = [m.add_var(var_type=BINARY) for i in r]
m.objective = maximize(xsum(v[i] * x[i] for i in r))

m += xsum(w[i] * x[i] for i in r) <= W m.optimize() selected = [i for i in r if x[i].x >= 0.99]
max_weight = sum([v[i] for i in selected])
max_conbo = [w[i] for i in selected]
print('最大価値:{} / 組み合わせ:{}'.format(max_weight, max_conbo))

このソースコードを実行すると、以下の実行結果が出力されます。最適な組み合わせのリスト番号とその最大価値を出力しています。

最大価値:20.0 / 組み合わせ:[0, 2, 4, 5]

 

まとめ

今回はPythonでMIPを使う方法を紹介しました。日本語のドキュメントがあまり多くはありませんが、公式ドキュメントにはサンプルコードにはいくつかサンプルコードが紹介されているので試してみるといいでしょう。

 

監修してくれたメンター

メンター 三浦

モバイルゲームを運用している会社のエンジニアをしています。趣味でWEB開発やクラウドコンピューティングもやっており、ソフトもハードもなんでもやります。

TechAcademyジュニアではPythonロボティクスコースを担当しています。好きな言語はpython, Node.js

 

大石ゆかり

内容分かりやすくて良かったです!

田島悠介

ゆかりちゃんも分からないことがあったら質問してね!

大石ゆかり

分かりました。ありがとうございます!

 

TechAcademyでは、初心者でも最短4週間でPythonを使った人工知能(AI)や機械学習の基礎を習得できるオンラインブートキャンプPython講座を開催しています。

挫折しない学習方法を知れる説明動画や、現役エンジニアとのビデオ通話とチャットサポート、学習用カリキュラムを体験できる無料体験も実施しているので、ぜひ参加してみてください。