[PYTHON] Food Desert Problem-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 numpy, 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).

Food desert problem

Let me use the problem of the paper "Analysis of Food Desert Problems in Nagasaki City".

Place a fresh food store so that everyone can attend and minimize the number of places. The general public must be within 5000m and the elderly must be within 1500m.

Way of thinking

Facility placement problem without capacity restrictions.

Solve with Python

First, create random data.

python

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

nc, n1, n2 = 4, 2, 2 #Number of candidate points, number of general public areas, number of elderly areas
np.random.seed(2)
dist1 = np.random.randint(4000, 6000, (nc, n1))
dist1 #Distance from the candidate point to the general public area
>>>
array([[5192, 4527],
       [4493, 5608],
       [5558, 4299],
       [4466, 5099]])

python

dist2 = np.random.randint(1000, 2000, (nc, n1))
dist2 #Distance from the candidate point to the elderly area
>>>
array([[1360, 1263],
       [1674, 1433],
       [1607, 1587],
       [1725, 1047]])

Formulate and solve.

python

m = LpProblem()
x = addvars(n, cat=LpBinary) #variable
m += lpSum(x) #Objective function
for i in range(n1):
    m += lpDot(dist1[i] <= 5000, x) >= 1 #Constraint
for i in range(n2):
    m += lpDot(dist2[i] <= 1500, x) >= 1 #Constraint
m.solve()
[int(value(v)) for v in x]
>>>
[1, 1, 0, 0]

that's all