組合せ最適化で鯨を見に行く

これなに

あなたは、夏休みに鯨を見に行くことになりました。組合せ最適化を使って、8か所のポイントのどこを選べばよいか考えてみましょう。

pythonでポイント情報の表示

import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addbinvars
n = 8 # ポイント数
np.random.seed(639)
df = pd.DataFrame(np.random.rand(n,2).round(2)*[0.2,100], columns=['Prob','Time'])
df.insert(0,'Place', [chr(i+65) for i in range(n)])
print(df)

	Place	Prob	Time
0	A	0.082	57.0
1	B	0.182	93.0
2	C	0.184	89.0
3	D	0.108	51.0
4	E	0.104	5.0
5	F	0.152	83.0
6	G	0.178	83.0
7	H	0.156	16.0

Placeがポイントの名称を、Probが鯨を見れる確率を、Timeがポイントへの移動と観測にかかる時間(分)を表しています。

問題その1

総時間 140分以内で確率の和を最大化せよ

答えその1

ナップサック問題になりますので、ササっと解いてみましょう。

python

m = LpProblem(sense=LpMaximize)
df['Var'] = addbinvars(n)
m += lpDot(df.Prob,df.Var)
m += lpDot(df.Time,df.Var) <= 140
m.solve()
df['Val'] = df.Var.apply(value)
print('%s found. Ave prob. = %.3f, Any prob. = %.3f'%(LpStatus[m.status],
      df[df.Val>0].Prob.sum(), 1-(1-df[df.Val>0].Prob).prod()))
print(df[df.Val>0])

結果

Optimal found. Ave prob. = 0.450, Any prob. = 0.381
  Place   Prob  Time    Var  Val
0     A  0.082  57.0  v0001  1.0
3     D  0.108  51.0  v0004  1.0
4     E  0.104   5.0  v0005  1.0
7     H  0.156  16.0  v0008  1.0

鯨を見れる回数の期待値は、0.45回になりました。でも、1回以上見れる確率は0.381です。

問題その2

総時間 140分以内で1回以上見れる確率を最大化せよ

答えその2

1回も見れない確率は、$\prod_i{(1- Prob_i)}$ です。このままでは、非線形ですが、(単調関数である)$\log$を使って線形化しましょう。

python

m = LpProblem(sense=LpMaximize)
df['Var'] = addbinvars(n)
m += -lpDot(np.log(1-df.Prob),df.Var)
m += lpDot(df.Time,df.Var) <= 140
m.solve()
df['Val'] = df.Var.apply(value)
print('%s found. Ave prob. = %.3f, Any prob. = %.3f'%(LpStatus[m.status],
      df[df.Val>0].Prob.sum(), 1-(1-df[df.Val>0].Prob).prod()))
print(df[df.Val>0])

結果

Optimal found. Ave prob. = 0.444, Any prob. = 0.383
  Place   Prob  Time    Var  Val
2     C  0.184  89.0  v0011  1.0
4     E  0.104   5.0  v0013  1.0
7     H  0.156  16.0  v0016  1.0

1回以上見れる確率が、0.381から0.383にちょっと増えました。

以上