45
53

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2016-08-19

これなに

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

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

アイテム数 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}$ぐらいで、はるかに小さい。

45
53
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
45
53

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?