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)

Solveur A Solveur B
Approche 0 38000
Approche 1 13400
Approche 2 41200
Approche 3 48600
Approche 4 (79)
Approche 5 694000

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)

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.

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

c'est tout

Recommended Posts

Prise en compte de l'approche du problème d'emballage en bac
Illustration des résultats du problème du sac à dos
Prise en compte de l'approche du problème d'emballage en bac
Comment résoudre le problème d'emballage du bac
Utilisez le problème d'emballage des bacs pour réduire les frais d'utilisation du cloud