Edited at

組合せ最適化ソルバーの威力

More than 1 year has passed since last update.


これなに

最適化問題を解くソルバーの威力(性能)をランダムで簡単な問題(ナップサック問題)を使ってみてみましょう。


ランダムなナップサック問題を作成

アイテム数 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 である最大重みマッチング問題でも、ソルバーの高性能が確認できます(重みマッチング問題における解法の比較)。

参考

以上





  1. ナップサック問題は、NP困難な問題で多項式オーダーの解法がないと考えられていますが、ソルバーでは効率的に解けます。 



  2. 厳密な最適解の目的関数の値に対して、比の差がε以下となる解を求めています。デフォルトでは、ε=0.0001のようです(参考 整数計画法メモ)。 



  3. 宇宙の原子の個数でさえ $10^{80}$ぐらいで、はるかに小さい。