Consideration of approach to bin packing problem

what is this

--Comparison of six formulation-based approaches to the bin-packing problem. ――Since it is one sample, it is hard to say that it is general, but for reference. --Solver A is COIN-OR's CBC, Solver B is a commercial solver.

Bin packing problem in question

I want to put 20 items of various sizes in 3 boxes as evenly as possible

result

Calculation time

Computation time per approach (milliseconds)

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

However, Solver A in Approach 4 is not the optimal solution, probably because of the MIPGAP settings. Everything else is optimal. (Approach 5 is a function approximation, but it happens to be an exact solution)

Outline of approach

--Approach 0: Minimize the sum of increments from the mean --Approach 1: Limit at the upper limit. (Search for the upper limit in a separate loop) --Approach 2: Limit at the upper limit. Add asymmetry constraints. (Search for the upper limit in a separate loop) --Approach 3: Minimize maximum value --Approach 4: Maximize the minimum value --Approach 5: Linear piecewise approximation of the square of the difference from the mean

Consideration

――It is the fastest to level with the constraint condition that is suppressed by the upper limit without setting the objective function. However, it is slow in total because it requires a loop to find the upper limit. ――Even if you put a constraint that breaks symmetry, it will be slow in some cases. --Minimization of the sum of increments from the average looks good. It seems that there is less symmetry than "minimize the maximum value" and "maximize the minimum value". --There is a difference in calculation time between "minimize maximum value" and "maximize minimum value". --If the convex quadratic function is approximated by piecewise linear, a more even solution may be obtained than the above approach, but it is slower.

Python program

Problem creation

python3


import numpy as np
from pulp import *
n1, n2 = 3, 20 #Number of boxes,Item count
np.random.seed(1)
a = np.random.randint(1,1000000,n2) #size
a
>>>
array([128038, 491756, 470925, 791625, 491264, 836490, 371404,  73350,
       117584,  21441, 229521, 413826, 966605, 925256, 436974, 293373,
       167303, 513301,  21759, 176486])

The most evenly divided are 2646029, 2646115, 2646137.

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

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

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

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

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

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

reference

-Let's use combinatorial optimization --Qiita -Python in optimization --Qiita -How to solve the bin packing problem --Qiita -What is Minisum or Minimax? --Qiita

that's all

Recommended Posts

Consideration of approach to bin packing problem
Illustration of the results of the knapsack problem
Consideration of approach to bin packing problem
How to solve the bin packing problem
Use the bin packing problem to reduce cloud usage fees