[PYTHON] What is Minisum or Minimax?

Talk about optimization

--The mini-sum problem is a problem that minimizes the sum (sum: sum) (mini: min). --The minimax problem is a problem that minimizes the maximum value (max: max) (mini: min).

When applied to the evacuation planning problem, it is as follows.

--Minisam problem: Minimizing the total evacuation time for everyone. --Minimax problem: Minimizing the evacuation time of the person who is the most late.

In general, with a mathematical optimization solver, the following can be said.

--The minisum problem is easier to solve than the minimax problem.

Let's check.

python


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

For 1000 items. Suppose 100 users have different sense of cost. Suppose you choose half of 1000 products for the following problems.

--Minisum problem: Minimizing the total cost of all users --Minimax problem: Minimize the maximum cost feeling for each user

Let's look at the calculation time while changing the number of products.

python


it = [100, 200, 500, 1000] #Product number list
tm = []
for n in it:
    b = a[:n]
    #Minisum problem
    m1 = LpProblem() #Minimization problem(mini)
    m1 += lpDot(b.T[:-1].sum(), b.Var) #total(Sam)
    m1 += lpSum(b.Var) <= int(n * 0.5)
    m1.solve()
    #Minimax problem
    m2 = LpProblem() #Minimization problem(mini)
    y = LpVariable('y', lowBound=0)
    # y >= max(Value of user j)
    for j in range(Number of users): m2 += y >= lpDot(b.ix[:, j], b.Var)
    m2 += y #total(Max)
    m2 += lpSum(b.Var) <= int(n * 0.5)
    m2.solve()
    tm.append((m1.solutionTime, m2.solutionTime))

plt.plot(it, tm)
plt.legend(['Minisum problem','Minimax problem'], loc='upper left')
plt.show()

image

The minimax problem takes considerably longer than the minisum problem.

Why does the minimax problem take so long?

--Compared to the minisum problem, the minimax problem has many optimal solutions. --Solver is exploring all possibilities. --If there are many optimal solutions, the solver cannot calculate efficiently.

Can't you solve the minimax problem efficiently?

In some cases, it may be faster to solve in two steps, such as How to solve a bin packing problem.

that's all

Recommended Posts