これなに
最適化問題を解くソルバーの威力(性能)をランダムで簡単な問題(ナップサック問題)を使ってみてみましょう。
ランダムなナップサック問題を作成
アイテム数 n のナップサック問題1を作成します。最適解が総アイテム数の8割くらいになるように調整しています。
python
import numpy as np
from pulp import *
def make(n):
np.random.seed(1)
w = 1 + np.random.rand(n)
p = w + np.random.randn(n)*0.1
m = LpProblem(sense=LpMaximize)
v = [LpVariable('x%d'%i, cat=LpBinary) for i in range(n)]
m += lpDot(p, v)
m += lpDot(w, v) <= int(n*1.25)
return v, m
計算時間を調べる
アイテム数を変えながら、計算時間を見てみましょう。最適化ソルバーはGUROBI 6.51を用いています。
python
v, m = make(10000)
%timeit -n 3 m.solve(GUROBI_CMD())
sum(value(x) for x in v)
>>>
3 loops, best of 3: 222 ms per loop
8254.0
python
v, m = make(20000)
%timeit -n 3 m.solve(GUROBI_CMD())
sum(value(x) for x in v)
>>>
3 loops, best of 3: 486 ms per loop
16470.0
python
v, m = make(50000)
%timeit -n 3 m.solve(GUROBI_CMD())
sum(value(x) for x in v)
>>>
3 loops, best of 3: 1.38 s per loop
41237.0
python
v, m = make(100000)
%timeit -n 3 m.solve(GUROBI_CMD())
sum(value(x) for x in v)
>>>
3 loops, best of 3: 2.64 s per loop
82458.0
まとめ
n 個のアイテムがあったときに、選択の仕方の可能性数は、$2^n$ 通りあります。また、この計算時間は厳密解を求めるまでの時間なので、この可能性を(ほぼ)すべて調べています2。
| アイテム数 | 計算時間(秒) | 解の可能性数 |
|---|---|---|
| 10000 | 0.22 | $2.00 * 10^{3010}$ |
| 20000 | 0.49 | $3.98 * 10^{6020}$ |
| 50000 | 1.38 | $3.16 * 10^{15051}$ |
| 100000 | 2.64 | $9.99 * 10^{30102}$ |
- 解の可能性数は、アイテム数に対して指数的に増えていきます。しかし、計算時間は、線形に近いです。
- 10の3万乗3という、途方もない組合せを調べるのに、3秒もかかっていません。
最近のソルバーが、如何に高性能かがわかるかと思います。ただし、組合せ最適化の問題の種類や定式化の仕方によっては、性能が著しく悪くなることもありますので、注意が必要です。
ナップサック問題は NP困難ですが、クラスが P である最大重みマッチング問題でも、ソルバーの高性能が確認できます(重みマッチング問題における解法の比較)。
参考
- 組合せ最適化を使おう
- 宮代先生の整数計画法メモ
- ナップサック問題関連
- ソルバー関連
以上