[PYTHON] Combinatorial optimization to investigate stars

what is this

--Investigate 1000 stars in a row with a photon rocket. --Let's find out if there are any aliens. However, not all stars can be examined. --The survey time varies from star to star. The total survey time of the stars to be surveyed should be within 10,000 days. --The discovery probability is estimated for each star. Maximize the sum of the discovery probabilities of the stars under investigation.

Try to solve

You can think of it as a knapsack problem. Let's solve it with Python. For mathematical optimization by Python, refer to the reference link.

python3

import numpy as np
from pulp import *
np.random.seed(1)
Number of stars= 1000
Survey time= np.random.randint(10,100,Number of stars)
Discovery probability= np.random.random(Number of stars)/100000
m = LpProblem(sense=LpMaximize)
x = [LpVariable('x%.4d'%i, cat=LpBinary) for i in range(Number of stars)]
m += lpDot(Discovery probability,x)
m += lpDot(Survey time,x) <= 10000
m.solve()
print(value(m.objective)) #Sum of discovery probabilities
>>>
0.0022822674119170536

In fact, rockets have a maximum range. Here, the maximum number of hops + 1 is mx, not simply the distance. Let's see what happens to the objective function when we change mx. The horizontal axis is mx and the vertical axis is the objective function.

python3

r = []
for mx in range(4,17):
    m = LpProblem(sense=LpMaximize)
    x = [LpVariable('x%.4d'%i, cat=LpBinary) for i in range(Number of stars)]
    m += lpDot(Discovery probability,x)
    m += lpDot(Survey time,x) <= 10000
    for i in range(Number of stars-mx+1):
        m += lpSum(x[i:i+mx]) >= 1 #Investigate at least one location within mx
    m.solve()
    r.append(value(m.objective))

%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(range(4,17),r)
plt.hlines(0.0022822674119170536,4,16);

Try to enlarge.

python3

plt.plot(range(4,17),r)
plt.hlines(0.0022822674119170536,4,16)
plt.xlim((9,16))
plt.ylim((0.00227,0.0023));

With the default free solver CBC, due to errors, the stricter constraints make the solution better.

The commercial solver solved more accurately.

Reference link -Python in optimization --Qiita

that's all