[PYTHON] Go see whales with combinatorial optimization

what is this

You are going to see whales during the summer vacation. Use Combinatorial Optimization (http://qiita.com/SaitoTsutomu/items/bfbf4c185ed7004b5721) to think about which of the eight points to choose.

Display point information in python

import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addbinvars
n = 8 #points
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 represents the ** name ** of the point, Prob represents the ** probability of seeing a whale **, and Time represents the ** time ** (minutes) required to move and observe the point.

Problem 1

Maximize the sum of the probabilities ** within the total time ** 140 minutes **

Answer 1

It will be Knapsack problem, so let's solve it quickly.

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])

result

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

The expected number of times you can see whales is 0.45. However, the probability of seeing it more than once is 0.381.

Problem # 2

Maximize the probability of seeing more than once within the total time ** 140 minutes **

Answer 2

The probability of never seeing it is $ \ prod_i {(1-Prob_i)} $. As it is, it is non-linear, but let's linearize it using $ \ log $ (which is a monotonic function).

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])

result

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

The probability of seeing it more than once has increased slightly from 0.381 to 0.383.

that's all