LoginSignup
16

More than 5 years have passed since last update.

ミニサムとかミニマックスって何ですか?

Last updated at Posted at 2016-02-06

最適化にまつわる話

  • ミニサム問題とは、合計(サム:sum)を最小化(ミニ:min)する問題。
  • ミニマックス問題とは、最大値(マックス:max)を最小化(ミニ:min)する問題。

避難計画問題に当てはめると、次のようになります。

  • ミニサム問題: 全員の避難時間の合計の最小化。
  • ミニマックス問題: 最も逃げ遅れる人の避難時間の最小化。

一般に数理最適化ソルバーでは、次のことが言えます。

  • ミニマックス問題よりミニサム問題の方が解きやすい。

確かめてみましょう。

python
import numpy as np, pandas as pd, matplotlib.pyplot as plt
from pulp import *
商品数 = 1000
ユーザ数 = 100
np.random.seed(1)
a = pd.DataFrame(np.random.rand(商品数, ユーザ数),
                 index=['商品%d'%i for i in range(商品数)],
                 columns=['ユーザ%d'%j for j in range(ユーザ数)])
a['Var'] = [LpVariable('v%d'%i, lowBound=0) for i in range(商品数)]
ユーザ0 ユーザ1 ユーザ2 ユーザ3 ユーザ4 ... ユーザ99
商品0 0.417022 0.720324 0.000114 0.302333 0.146756 ... 0.186260
... ... ... ... ... ... ... ...
商品999 0.950176 0.556653 0.915606 0.641566 0.390008 0.485991 0.604310

1000個の商品に対して。100人のユーザがバラバラの費用感を持っているとします。
下記の問題に対して、1000個の商品の中から、半分を選ぶとします。

  • ミニサム問題: 全ユーザの費用感の合計の最小化
  • ミニマックス問題: 各ユーザの費用感の最大値の最小化

商品の数を変えながら、計算時間を見てみましょう。

python
it = [100, 200, 500, 1000] # 商品数リスト
tm = []
for n in it:
    b = a[:n]
    # ミニサム問題
    m1 = LpProblem() # 最小化問題(ミニ)
    m1 += lpDot(b.T[:-1].sum(), b.Var) # 合計(サム)
    m1 += lpSum(b.Var) <= int(n * 0.5)
    m1.solve()
    # ミニマックス問題
    m2 = LpProblem() # 最小化問題(ミニ)
    y = LpVariable('y', lowBound=0)
    # y >= max(ユーザj の価値)
    for j in range(ユーザ数): m2 += y >= lpDot(b.ix[:, j], b.Var)
    m2 += y # 合計(マックス)
    m2 += lpSum(b.Var) <= int(n * 0.5)
    m2.solve()
    tm.append((m1.solutionTime, m2.solutionTime))

plt.plot(it, tm)
plt.legend(['ミニサム問題','ミニマックス問題'], loc='upper left')
plt.show()

image

ミニサム問題に比べて、ミニマックス問題の方が、かなり時間がかかります。

ミニマックス問題が時間がかかるのは、何故?

  • ミニサム問題に比べて、ミニマックス問題は、最適解がたくさんあります。
  • ソルバーでは、全ての可能性を探索しています。
  • 最適解がたくさんあると、ソルバーが効率よく計算できません。

ミニマックス問題を効率よく解けないの?

場合によっては、ビンパッキング問題の解き方のように、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
16