As a solution to the knapsack problem in "Use combinatorial optimization", "[Greedy algorithm](https://ja.wikipedia. org / wiki /% E8% B2% AA% E6% AC% B2% E6% B3% 95) is a good way, not optimal. "
Actually, I wondered what it was, so I'll check it.
--The number of items is 100. --The item size should be a uniform random number of (0.1, 1.0). --The value of an item is created by multiplying its size by a lognormal random number. --Change the capacity of the knapsack in 0.1 increments and solve it repeatedly. --The result is illustrated in matplotlib.
python
%matplotlib inline
import math, numpy as np, matplotlib.pyplot as plt
from pulp import *
np.random.seed(1)
n = 100 #Item count
siz = np.random.uniform(0.1, 1.0, n)
prf = siz * np.random.lognormal(1, 0.1, n)
eff = prf / siz
siz, prf, eff = np.array([siz, prf, eff]).T[eff.argsort()].T
r1, r2, p1, p2 = [], [], [], []
In the greedy method, we will investigate in order of efficiency (value / size) and put in so as not to exceed the capacity.
python
for sz in range(math.ceil(sum(siz)*10)):
v, r, rm = 0, [], sz / 10
for i in range(len(siz)-1, -1, -1):
r.append(int(rm < siz[i]))
if r[-1] == 0:
rm -= siz[i]
v += prf[i]
r1.append(list(reversed(r)))
p1.append(v)
plt.imshow(np.array(r1).T, cmap='gray')
――It took a few milliseconds to solve 538 times. ――Vertical corresponds to items in order of efficiency. The side corresponds to the capacity of the knapsack x 10. --Black represents the selected item and white represents the unselected item. --The greedy algorithm is packed in order of efficiency, so the boundaries are relatively clear.
Let's solve it as a mixed integer optimization problem with pulp.
python
m = LpProblem(sense=LpMaximize)
v = [LpVariable('v%d'%i, cat=LpBinary) for i in range(len(siz))]
m += lpDot(prf, v)
e = lpDot(siz, v) <= 1
m += e
r = []
for sz in range(math.ceil(sum(siz)*10)):
e.changeRHS(sz / 10)
m.solve()
r2.append([1 - int(value(x)) for x in v])
p2.append(value(m.objective))
plt.imshow(np.array(r2).T, cmap='gray')
--Solved 538 times, 16 seconds with Gurobi 6.5.1, 58 seconds with default CBC. ――The mixture of black and white near the boundary indicates that it is best to choose an inefficient one as a whole.
Graph the value of the greedy solution divided by the value of the exact solution. The vertical is the ratio, and the horizontal is the capacity of the knapsack x 10.
python
plt.ylim((0, 1.1))
plt.plot(np.array(p1[2:]) / np.array(p2[2:]))
If the capacity is small and the number of items that can be entered is small, there will be some error, but if there are a certain number of items, you can see that the accuracy is quite good.
It was in H22.Math.Prog.No.9.pdf I tried the roaring method.
python
r3,p3 = [],[]
for sz in range(math.ceil(sum(siz)*10)):
v, r, ca, rm = 0, [], sz / 10, sum(siz)
for i in range(len(siz)):
r.append(int(not(0 < rm-siz[i] <= ca and siz[i] <= ca)))
rm -= siz[i]
if r[-1] == 0:
ca -= siz[i]
v += prf[i]
r3.append(r)
p3.append(v)
plt.imshow(np.array(r3).T, cmap='gray');
You can see that the greedy method was above the boundary, but the roaring method was missing below the boundary. Looking at the performance, it feels worse than the greedy algorithm.
python
plt.ylim((0, 1.1))
plt.plot(np.array(p3[2:]) / np.array(p2[2:]));
that's all
Recommended Posts