[PYTHON] Berücksichtigung des Ansatzes zum Problem der Behälterverpackung

Was ist das

• Vergleich von sechs formulierungsbasierten Ansätzen zum Problem der Behälterverpackung. ――Da es sich um ein Beispiel handelt, ist es schwer zu sagen, dass es allgemein ist, aber als Referenz. --Solver A ist der CBC von COIN-OR und Solver B ist ein kommerzieller Solver.

Problem beim Packen des Zielbehälters

Ich möchte 20 Artikel in verschiedenen Größen so gleichmäßig wie möglich in 3 Kartons legen

Ergebnis

Berechnungszeit

Berechnungszeit pro Ansatz (Millisekunden)

Solver A in Ansatz 4 ist jedoch wahrscheinlich aufgrund der MIPGAP-Einstellungen nicht die optimale Lösung. Alles andere ist optimal. (Ansatz 5 ist eine Funktionsnäherung, aber es ist zufällig eine exakte Lösung)

Überblick über den Ansatz

--Ansatz 0: Minimieren Sie die Summe der Inkremente aus dem Durchschnitt

• Ansatz 1: Grenze an der Obergrenze. (Suche nach der Obergrenze in einer separaten Schleife)
• Ansatz 2: Grenze an der Obergrenze. Fügen Sie Asymmetrieeinschränkungen hinzu. (Suche nach der Obergrenze in einer separaten Schleife)
• Ansatz 3: Minimieren Sie den Maximalwert
• Ansatz 4: Maximieren Sie den Mindestwert
• Ansatz 5: Lineare Teilungsnäherung des Quadrats der Differenz vom Mittelwert

Erwägung

――Es ist am schnellsten, die Einschränkungsbedingung zu erreichen, die durch die Obergrenze unterdrückt wird, ohne die Zielfunktion festzulegen. Insgesamt ist es jedoch langsam, da eine Schleife erforderlich ist, um die Obergrenze zu ermitteln. ――Selbst wenn Sie eine Einschränkung festlegen, die die Symmetrie unterbricht, ist diese in einigen Fällen langsam.

• Die Minimierung der Summe der Inkremente aus dem Durchschnitt sieht gut aus. Es scheint weniger symmetrisch zu sein als "Maximalwert minimieren" und "Minimalwert maximieren".
• Es gibt einen Unterschied in der Berechnungszeit zwischen "Minimalwert minimieren" und "Minimalwert maximieren".
• Wenn die konvexe quadratische Funktion durch eine segmentale Linearität angenähert wird, kann eine gleichmäßigere Lösung erhalten werden als der obige Ansatz, sie ist jedoch langsamer.

Python-Programm

Problemstellung

python3

import numpy as np
from pulp import *
n1, n2 = 3, 20 #Anzahl an Boxen,Stückzahl
np.random.seed(1)
a = np.random.randint(1,1000000,n2) #Größe
a
>>>
array([128038, 491756, 470925, 791625, 491264, 836490, 371404,  73350,
       117584,  21441, 229521, 413826, 966605, 925256, 436974, 293373,
       167303, 513301,  21759, 176486])

Die gleichmäßigsten sind 2646029, 2646115, 2646137.

Ansatz 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])

Ansatz 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])

Ansatz 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])

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

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

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

Referenz

• Verwenden wir die Kombinationsoptimierung --Qiita
• Python in der Optimierung - Qiita
• So lösen Sie das Problem beim Verpacken von Behältern - Qiita
• Was ist Mini Sam oder Mini Max? --Qiita

das ist alles