[PYTHON] 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