소개

"조합 최적화를 사용합시다."에서 냅삭 문제의 해법으로서, "탐욕법은 좋은 방법인 최적이 아니다"라고 말했습니다.

사실, 어떨까라고 생각했기 때문에 확인해 보겠습니다.

무작위 문제를 파이썬으로 해결

아이템은 100개로 합니다.

아이템의 크기는 (0.1, 1.0)의 균일 난수로 합니다.

아이템의 값은 크기에 로그 정규 난수를 곱하여 생성됩니다.

냅삭의 용량을 0.1 단위로 바꾸어 반복 풀어줍니다.

결과는 matplotlib로 표시됩니다.

데이터 준비

파이썬

%matplotlib inline
import math, numpy as np, matplotlib.pyplot as plt
from pulp import *
np.random.seed(1)
n = 100 # アイテム数
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 = [], [], [], []

근사 해법 (탐욕법) 결과

탐욕법에서는 효율(가치/크기)의 좋은 순서로 조사해 가고 용량을 초과하지 않도록 넣습니다.

파이썬

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

538회 풀어 몇 밀리초였습니다.

세로는 효율적인 순서의 아이템에 대응합니다. 옆은, 냅삭의 용량×10에 대응합니다.

블랙이 선택한 아이템, 화이트가 선택되지 않은 아이템을 나타냅니다.

탐욕법은 효율적인 순서로 포장되므로 비교적 경계가 명확합니다.

엄밀한 해법의 결과

pulp에서 혼합 정수 최적화 문제로 풀어 봅시다.

파이썬

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

538회 풀어 Gurobi 6.5.1에서 16초, 기본 CBC에서는 58초였습니다.

경계 부근에서 흰색과 검정이 섞여 있는 것은 효율적이지 않은 것을 선택하는 것이 전체적으로 최적인 것을 나타냅니다.

탐욕법의 정확성

탐욕법의 해의 값을 엄밀해의 값으로 나눈 것을 그래프화합니다. 세로가 비로, 가로가 냅삭의 용량×10입니다.

파이썬

plt.ylim((0, 1.1))
plt.plot(np.array(p1[2:]) / np.array(p2[2:]))

용량이 작고, 들어가는 아이템수가 적으면, 다소, 오차가 있습니다만, 어느 정도의 아이템수가 있으면, 꽤 정밀도가 좋은 것을 알 수 있습니다.

추기(吝嗇法)

H22.Math.Prog.No.9.pdf 에 있던 吝嗇法을 시험해 보았습니다.

파이썬

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

탐욕법은 경계 위로 튀어나왔지만, 吝嗇法은 경계 아래에 빠진 것이 있음을 알 수 있습니다.
성능을 보면 탐욕법보다 나쁜 느낌입니다.

파이썬

plt.ylim((0, 1.1))
plt.plot(np.array(p3[2:]) / np.array(p2[2:]));

이상