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

Recommended Posts

Go see whales with combinatorial optimization
Grouping games with combinatorial optimization
Combinatorial optimization with quantum annealing
Maximize restaurant sales with combinatorial optimization
Pave the road with combinatorial optimization
Solving game theory with combinatorial optimization
Let's stack books flat with combinatorial optimization
Solving nurse scheduling problems with combinatorial optimization
Python with Go
Use combinatorial optimization
Create an academic society program with combinatorial optimization
Solving school district organization problems with combinatorial optimization
Solving the N Queen problem with combinatorial optimization
Solving the N Queens problem with combinatorial optimization
Road installation with optimization
Grouping by combinatorial optimization
Getting Started with Optimization
Try function optimization with Optuna
Operate Db2 container with Go
Getting Started with Go Assembly
Combinatorial optimization to investigate stars
Bit full search with Go
Connect to Postgresql with GO
Restore disjointed photos with optimization!
Hot reload with Go + Air
General-purpose global optimization with Z3
Try implementing perfume with Go
Adjust hyperparameters with Bayesian optimization
Solving Knapsack Problems with Google's OR-Tools-Practicing the Basics of Combinatorial Optimization Problems