これなに
OR学会の機関誌10月号「学生たちのOR」特集から、適当に最適化の問題をピックアップしてPythonで解いてみたいと思います。
準備として、pandas, pulp, ortoolpy が必要です。環境構築は、組合せ最適化を使おうを参考にしてください。
最適計測プラン問題
論文「ピラミッドの最適計測プランの作成」の問題を使わせてもらいましょう。
候補点に何台かのスキャナを設置して、レーザーでスキャンしデータを取得したい。スキャナ台数を最小にし、取得データ量を最大化せよ。
考え方
論文では、2段階で解いていますが、面倒なので、設置コストを10倍にして、1回で解くことにしましょう。
Pythonで解く
まず、ランダムなデータを作成します。
python
import numpy as np
from pulp import *
from ortoolpy import addvar, addvars
n = 4 # 候補点数
np.random.seed(3)
a = np.random.rand(n, n).round(3)
a # データ量
>>>
array([[ 0.551, 0.708, 0.291, 0.511],
[ 0.893, 0.896, 0.126, 0.207],
[ 0.051, 0.441, 0.03 , 0.457],
[ 0.649, 0.278, 0.676, 0.591]])
python
d = np.random.randint(0, 2, (n, n))
d[np.diag_indices(n)] = 1
d # 計測可能性
>>>
array([[1, 1, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 1],
[0, 1, 0, 1]])
定式化して解きます。
python
m = LpProblem()
x = addvars(n, cat=LpBinary) # 変数
m += lpSum(x)*10 - lpDot(a.sum(1), x) # 目的関数
for i in range(n):
m += lpDot(d[:,i], x) >= 1 # 制約
m.solve()
[int(value(v)) for v in x]
>>>
[1, 0, 0, 1]
以上