Essayons la puissance (performance) du solveur qui résout le problème d'optimisation en utilisant un problème aléatoire et simple (problème de sac à dos).
Créez un problème de sac à dos [^ 1] avec n articles. La solution optimale est ajustée à environ 80% du nombre total d'articles.
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
Voyons le temps de calcul tout en modifiant le nombre d'éléments. Le solveur d'optimisation utilise 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
Lorsqu'il y a n éléments, il y a $ 2 ^ n $ choix possibles. Aussi, puisque ce temps de calcul est le temps de trouver la solution exacte, nous étudions (presque) toute cette possibilité [^ 2].
| Nombre d'éléments | Temps de calcul(Secondes) | Nombre de solutions possibles |
|---|---|---|
| 10000 | 0.22 | |
| 20000 | 0.49 | |
| 50000 | 1.38 | |
| 100000 | 2.64 |
――Le nombre de solutions possibles augmente de façon exponentielle avec le nombre d'éléments. Cependant, le temps de calcul est presque linéaire. «Il a fallu moins de 3 secondes pour découvrir la formidable combinaison de 10 à la 30 000e puissance [^ 3].
Vous pouvez voir à quel point ces solveurs récents sont performants. Cependant, il est à noter que les performances peuvent être significativement dégradées en fonction du type de problème d'optimisation de combinaison et de la méthode de formulation.
Le problème du sac à dos est NP-complet, mais vous pouvez voir la haute performance du solveur même dans le problème de correspondance de poids maximum avec la classe P (Comparaison des solutions dans le problème de correspondance de poids. 7fd199a95d78a6f3b741)).
référence
c'est tout
[^ 1]: Le problème du sac à dos est un problème NP difficile et on pense qu'il n'y a pas de solution de l'ordre du polymorphisme, mais il peut être résolu efficacement par un solveur. [^ 2]: Nous trouvons une solution dans laquelle la différence de rapport est inférieure ou égale à ε par rapport à la valeur de la fonction objectif de la solution optimale exacte. Par défaut, il semble être ε = 0,0001 (Référence Note sur la programmation d'entiers). [^ 3]: Même le nombre d'atomes dans l'univers est d'environ 10 $ ^ {80} $, ce qui est beaucoup plus petit.
Recommended Posts