Prise en compte de l'approche du problème d'emballage en bac

Qu'est-ce que c'est

--Comparaison de six approches basées sur la formulation du problème de l'emballage en bac. ―― Puisqu'il s'agit d'un échantillon, il est difficile de dire qu'il est général, mais à titre de référence. --Solver A est le CBC de COIN-OR, et Solver B est un solveur commercial.

Problème d'emballage du bac cible

Je veux mettre 20 articles de différentes tailles dans 3 boîtes aussi uniformément que possible

résultat

Temps de calcul

Temps de calcul par approche (millisecondes)

Cependant, le solveur A dans Approach 4 n'est pas la solution optimale, probablement en raison des paramètres MIPGAP. Tout le reste est optimal. (L'approche 5 est une approximation de fonction, mais il se trouve que c'est une solution exacte)

Aperçu de l'approche

--Approach 0: minimise la somme des incréments de la moyenne --Approach 1: Limite à la limite supérieure. (Recherchez la limite supérieure dans une boucle séparée) --Approach 2: Limite à la limite supérieure. Ajoutez des contraintes d'asymétrie. (Recherchez la limite supérieure dans une boucle séparée)

• Approche 3: minimiser la valeur maximale --Approach 4: Maximiser la valeur minimale
• Approche 5: Approximation par division linéaire du carré de la différence par rapport à la moyenne

Considération

――Il est le plus rapide à niveler avec la condition de contrainte qui est supprimée par la limite supérieure sans définir la fonction objectif. Cependant, il est lent au total car il nécessite une boucle pour trouver la limite supérieure. ――Même si vous mettez une contrainte qui rompt la symétrie, elle sera lente dans certains cas.

• La minimisation de la somme des incréments par rapport à la moyenne semble bonne. Il semble qu'il y ait moins de symétrie que «minimiser la valeur maximale» et «maximiser la valeur minimale». --Il y a une différence de temps de calcul entre «minimiser la valeur maximale» et «maximiser la valeur minimale».
• Si la fonction quadratique convexe est approchée par un segment linéaire, une solution plus uniforme peut être obtenue que l'approche ci-dessus, mais elle est plus lente.

Programme Python

Création de problème

python3

import numpy as np
from pulp import *
n1, n2 = 3, 20 #Nombre de boîtes,Nombre d'éléments
np.random.seed(1)
a = np.random.randint(1,1000000,n2) #Taille
a
>>>
array([128038, 491756, 470925, 791625, 491264, 836490, 371404,  73350,
       117584,  21441, 229521, 413826, 966605, 925256, 436974, 293373,
       167303, 513301,  21759, 176486])

Les plus répartis sont 2646029, 2646115, 2646137.

Approche 0

python3

m = LpProblem()
x = [[LpVariable('x%.1d%.2d'%(i,j), cat=LpBinary)
      for j in range(n2)] for i in range(n1)]
y = [LpVariable('y%.1d'%i) for i in range(n1)]
z = LpVariable('z', lowBound=0)
m += z
for j in range(n2):
    m += lpSum(x[i][j] for i in range(n1)) == 1
for i in range(n1):
    m += y[i] == lpDot(a, x[i])
    m += y[i] - sum(a)/n1 <= z
%time m.solve()
print(LpStatus[m.status])

Approche 1

python3

m = LpProblem()
x = [[LpVariable('x%.1d%.2d'%(i,j), cat=LpBinary)
      for j in range(n2)] for i in range(n1)]
y = [LpVariable('y%.1d'%i) for i in range(n1)]
for j in range(n2):
    m += lpSum(x[i][j] for i in range(n1)) == 1
for i in range(n1):
    m += y[i] == lpDot(a, x[i])
    m += y[i] <= 2646137
%time m.solve()
print(LpStatus[m.status])

Approche 2

python3

m = LpProblem()
x = [[LpVariable('x%.1d%.2d'%(i,j), cat=LpBinary)
      for j in range(n2)] for i in range(n1)]
y = [LpVariable('y%.1d'%i) for i in range(n1)]
for j in range(n2):
    m += lpSum(x[i][j] for i in range(n1)) == 1
for i in range(n1):
    m += y[i] == lpDot(a, x[i])
    m += y[i] <= 2646137
    if i:
        m += y[i-1] <= y[i]
%time m.solve()
print(LpStatus[m.status])

Approche 3

python3

m = LpProblem()
x = [[LpVariable('x%.1d%.2d'%(i,j), cat=LpBinary)
      for j in range(n2)] for i in range(n1)]
y = [LpVariable('y%.1d'%i) for i in range(n1)]
z = LpVariable('z') # max
m += z
for j in range(n2):
    m += lpSum(x[i][j] for i in range(n1)) == 1
for i in range(n1):
    m += y[i] == lpDot(a, x[i])
    m += y[i] <= z
%time m.solve()
print(LpStatus[m.status], value(m.objective))

Approche 4

python3

m = LpProblem(sense=LpMaximize)
x = [[LpVariable('x%.1d%.2d'%(i,j), cat=LpBinary)
      for j in range(n2)] for i in range(n1)]
y = [LpVariable('y%.1d'%i) for i in range(n1)]
z = LpVariable('z') # min
m += z
for j in range(n2):
    m += lpSum(x[i][j] for i in range(n1)) == 1
for i in range(n1):
    m += y[i] == lpDot(a, x[i])
    m += y[i] >= z
%time m.solve()
print(LpStatus[m.status], value(m.objective))

Approche 5

python3

mean = sum(a)/n1
m = LpProblem()
x = [[LpVariable('x%.1d%.2d'%(i,j), cat=LpBinary)
      for j in range(n2)] for i in range(n1)]
y = [LpVariable('y%.1d'%i) for i in range(n1)] # sum
z = [LpVariable('z%.1d'%i) for i in range(n1)] # diff
w = [LpVariable('w%.1d'%i) for i in range(n1)] # cost
m += lpSum(w)
for j in range(n2):
    m += lpSum(x[i][j] for i in range(n1)) == 1
for i in range(n1):
    m += y[i] == lpDot(a, x[i])
    m += z[i] >=  (y[i]-mean)
    m += z[i] >= -(y[i]-mean)
    m += w[i] >= 0.2 * z[i]
    m += w[i] >= 0.5 * z[i] - 7.5
    m += w[i] >=       z[i] - 25
%time m.solve()
print(LpStatus[m.status], value(m.objective))

référence

• Utilisons l'optimisation des combinaisons --Qiita
• Python dans l'optimisation --Qiita
• Comment résoudre le problème d'emballage du bac --Qiita
• Qu'est-ce que Mini Sam ou Mini Max? --Qiita

c'est tout