[PYTHON] Illustration of the results of the knapsack problem

Introduction

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.

Solve random problems in Python

--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.

Data preparation

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 = [], [], [], []

Result of approximate solution (greedy algorithm)

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

figure_1-1.png

――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.

Result of exact solution

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

napsack.png

--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.

Accuracy of greedy algorithm

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:]))

image

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.

Postscript (stingy method)

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

image.png

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

image.png

that's all

Recommended Posts