Pythonでの数理最適化入門

概要

本記事では python の数理最適化ライブラリや簡単なロジックの実装例、数理最適化を学習する際に参考になりそうな書籍を解説します。

はじめに

数理最適化とは 現実の問題を数式（数理モデル）として定義し、制約条件を満たしつつ、コストの最小化や利益が最大化されるような変数の値を求める手法 のことです。問題には非線形最適化問題、混合整数最適化問題、線形最適化問題の三つがあります。これら三つは包含関係にあり、 非線形最適化問題>混合整数最適化問題>線形最適化問題 の関係にあります。これらをまとめて汎用問題といいます。

ライブラリ

Python で数理最適化する際に活用するライブラリをいくつかご紹介します。

PuLP

もっとも一般的な数理最適化のライブラリです。混合整数最適化問題、線形最適化問題に適しています。混合整数最適化問題とは目的関数と制約条件は線形で、一部の変数が整数しかとらないものを含む問題です。線形最適化問題とは全ての変数が連続値を取る問題です。

Python-MIP

PuLP とほぼ同じだが、Python-MIP の方がよりオブジェクト指向的で直観的にコードを書くことが出来ます。その他にも様々な利点が存在します。詳しくこちらを参照してください。

mypulp

PuLP のラッパーモジュールです。

gurobipy

PuLP よりも高性能で混合整数最適化問題と二次最適化問題に適しています。

pymoo

多目的最適化に特化したライブラリです。詳しくはこちらを参照してください。

ロジックの実装例

PuLP を用いて線形計画問題を解いてみましょう。下記の問題を考えてみましょう。

材料AとBで製造できる製品XとYをたくさん作成したい。
Xを1kg作るのに、Aが1kg、Bが3kg必要である。
Yを1kg作るのに、Aが2kg、Bが1kg必要である。
また、XもYも1kg当りの価格は100円である。
材料Aは16kg、Bは18kgしかないときに、XとYの価格の合計が最大になるようにするには、
XとYをどれだけ作成すればよいか求めよ。

問題を数理モデルであらわすと下記のようになります。数理モデルを式で表現することを定式化するといいます。

変数: x,y \geq 0 \\ 目的関数: 100x+100y \\ 制約条件: x+2y \leq 16 \\ \hspace{50pt} 3x+y \leq 18 \\

この数理モデルをコードに落とし込むと

from pulp import *
m = LpProblem(sense=LpMaximize) # 数理モデル
x = LpVariable('x', lowBound=0) # 変数
y = LpVariable('y', lowBound=0) # 変数
m += 100 * x + 100 * y # 目的関数
m += x + 2 * y <= 16 # 材料Aの上限の制約条件
m += 3 * x + y <= 18 # 材料Bの上限の制約条件
m.solve() # ソルバーの実行
print(f"x={value(x)}, y={value(y)}") # 4, 6

のようになります。数理モデルをコードに起こす際は

数理モデルを定義
変数を定義
目的関数を定義
制約条件を定義
ソルバーを実行

の順でコーディングします。コードの実行結果は以下です。

Welcome to the CBC MILP Solver
Version: 2.10.3
Build Date: Dec 15 2019

solution /tmp/c1043875e60243f1aa73450426d5d62a-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 7 COLUMNS
At line 14 RHS
At line 17 BOUNDS
At line 18 ENDATA
Problem MODEL has 2 rows, 2 columns and 4 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Presolve 2 (0) rows, 2 (0) columns and 4 (0) elements
0  Obj -0 Dual inf 200 (2)
0  Obj -0 Dual inf 200 (2)
2  Obj 1000
Optimal - objective value 1000
Optimal objective 1000 - 2 iterations time 0.002
Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.00   (Wallclock seconds):       0.01

x=4.0, y=6.0

よって製品 X を 4、製品 Y を 6 個作成すると利益が最大になることが分かりました。線形計画問題は典型問題と呼ばれる問題の一種で、他にも様々な典型問題があります。ご興味のある方は組合せ最適化 - 典型問題と実行方法を参照してください。

参考になりそうな書籍・WEB ページ

数理最適化を学習する際に参考になりそうな書籍、WEB ページを列挙します。

参考文献

備考

Hakky ではエンジニアを募集中です！まずは話してみたいなどでも構いませんので、ぜひお気軽に採用ページからお問い合わせくださいませ。