Optimal measurement plan --From the October issue of the OR magazine

what is this

OR Society October issue of the journal ["** Students' OR **" special feature](http://www.orsj.or.jp/ From e-library / elcorsj.html # 6110), I would like to pick up the optimization problem appropriately and solve it with Python. As a preparation, you need pandas, pulp, ortoolpy. [Use combinatorial optimization](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721#%E3%82%BD%E3%83%95%E3%83%88%] Please refer to E3% 81% AE% E3% 82% A4% E3% 83% B3% E3% 82% B9% E3% 83% 88% E3% 83% BC% E3% 83% AB).

Optimal measurement plan problem

Let me use the problem of the paper "Creating an optimal measurement plan for the pyramid".

I want to install several scanners at the candidate points and scan them with a laser to acquire data. Minimize the number of scanners and maximize the amount of acquired data.

Way of thinking

In the paper, it is solved in two steps, but it is troublesome, so let's increase the installation cost by 10 times and solve it in one step.

Solve with Python

First, create random data.

python


import numpy as np
from pulp import *
from ortoolpy import addvar, addvars

n = 4 #Candidate points
np.random.seed(3)
a = np.random.rand(n, n).round(3)
a #amount of data
>>>
array([[ 0.551,  0.708,  0.291,  0.511],
       [ 0.893,  0.896,  0.126,  0.207],
       [ 0.051,  0.441,  0.03 ,  0.457],
       [ 0.649,  0.278,  0.676,  0.591]])

python


d = np.random.randint(0, 2, (n, n))
d[np.diag_indices(n)] = 1
d #Measurable
>>>
array([[1, 1, 1, 0],
       [1, 1, 0, 1],
       [1, 0, 1, 1],
       [0, 1, 0, 1]])

Formulate and solve.

python


m = LpProblem()
x = addvars(n, cat=LpBinary) #variable
m += lpSum(x)*10 - lpDot(a.sum(1), x) #Objective function
for i in range(n):
    m += lpDot(d[:,i], x) >= 1 #Constraint
m.solve()
[int(value(v)) for v in x]
>>>
[1, 0, 0, 1]

that's all

Recommended Posts

Optimal measurement plan --From the October issue of the OR magazine
Ambulance placement problem --From the October issue of the OR magazine
Food Desert Problem-From the October issue of the OR magazine
Optimizing boarding strategies for aircraft-from the October issue of the OR bulletin
Existence from the viewpoint of Python
Learning notes from the beginning of Python 1
Omit BOM from the beginning of the string
Learning notes from the beginning of Python 2