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

image

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

image

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

The commercial solver solved more accurately.

image

Reference link -Python in optimization --Qiita

that's all

Recommended Posts

Combinatorial optimization to investigate stars
Use combinatorial optimization
Combinatorial optimization to find the hand of "Millijan"
Grouping by combinatorial optimization
Grouping games with combinatorial optimization
Introduction to Nonlinear Optimization (I)
Combinatorial optimization with quantum annealing
An introduction to Bayesian optimization
Solving "cubes in cubes" by combinatorial optimization
Solving 4-color problems with combinatorial optimization
Maximize restaurant sales with combinatorial optimization
Go see whales with combinatorial optimization
Pave the road with combinatorial optimization
Determine recorded programs by combinatorial optimization
The power of combinatorial optimization solvers
Design of experiments and combinatorial optimization
Solving game theory with combinatorial optimization
Combinatorial optimization techniques seen in puzzles
Divide into teams by combinatorial optimization
Think about menus by combinatorial optimization