최적화에 관한 이야기

미니샘 문제란, 합계(샘:sum)를 최소화(미니:min) 하는 문제.

미니맥스 문제란 최대값(맥스:max)을 최소화(미니:min)하는 문제.

피난 계획 문제에 적용하면 다음과 같습니다.

미니 샘 문제 : 모든 피난 시간의 합계 최소화.

미니맥스 문제: 가장 도망치는 사람의 피난 시간 최소화.

일반적으로 수리 최적화 솔버에서는 다음을 말할 수 있습니다.

미니맥스 문제보다 미니섬 문제가 더 풀기 쉽다.

확인해 봅시다.

파이썬

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개의 상품 중에서 절반을 선택한다고 가정합니다.

미니 샘 문제 : 모든 사용자의 총 비용 합계 최소화

미니 맥스 문제 : 각 사용자의 최대 비용 감각 최소화

상품의 수를 바꾸면서 계산 시간을 보자.

파이썬

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

미니 샘 문제에 비해 미니 맥스 문제가 상당히 시간이 걸립니다.

미니맥스 문제가 시간이 걸리는 이유는?

미니샘 문제에 비해 미니맥스 문제는 최적해가 많이 있습니다.

솔버는 모든 가능성을 탐구합니다.

최적 해가 많으면 솔버가 효율적으로 계산할 수 없습니다.

미니 맥스 문제를 효율적으로 풀 수 없습니까?

경우에 따라서는, 빈 패킹 문제를 해결하는 방법 와 같이, 2 단계에 푸는 것이 빨리 풀 수 있는 일도 있습니다.

이상