[PYTHON] 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)

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