-*- mode: Org; fill-column: 90; coding: utf-8; -*-
Разбить предложенный массив из весов рулонов на машины двух типов (22.2 и 27.6, превышать эту нагрузку нельзя), таким образом, чтобы удельная загрузка была максимальной и все рулоны были разложены по машинам.
В качестве подсказки укажем, что стоит попробовать использовать солверы SCIP, GUROBI, CPLEX и тд.
SCIP - Apache 2.0
- https://github.com/scipopt/scip
- reuirement:
- Apache License 2.0 https://github.com/scipopt/soplex
- MIT License https://github.com/scipopt/PySCIPOpt
- (optional) https://github.com/scipopt/papilo
GUROBI - proprietary?
CPLEX - Proprietary
COIN-OR - GPL and Eclipse Public License v 2.0 https://github.com/coin-or/CyLP https://en.wikipedia.org/wiki/COIN-OR
OR-Tools - Apache License 2.0 https://github.com/google/or-tools (uses SCIP)
weight |
---|
8.78 |
8.77 |
8.77 |
8.76 |
8.74 |
8.73 |
8.72 |
8.7 |
8.63 |
8.63 |
8.62 |
8.62 |
8.62 |
8.61 |
8.6 |
8.57 |
8.57 |
8.53 |
8.53 |
8.5 |
8.49 |
8.49 |
8.47 |
8.44 |
8.42 |
8.41 |
8.39 |
8.38 |
8.37 |
8.33 |
8.31 |
8.31 |
8.28 |
8.27 |
8.27 |
8.26 |
8.2 |
8.15 |
8.12 |
8.12 |
7.85 |
7.14 |
7.13 |
7.06 |
6.31 |
6.3 |
6.03 |
6.02 |
5.81 |
5.78 |
5.76 |
5.76 |
5.75 |
5.74 |
5.64 |
5.31 |
5.31 |
import pandas as pd
def pd2org(df_to_table):
return tabulate(df_to_table, headers=df_to_table.columns, tablefmt='orgtbl')
df = pd.DataFrame(data, columns=['col'])
# df['acidity'] = df.acidity.str.extract('(?P<digit>([-+])?\d+(.\d+)?)')['digit'].astype(float)
import numpy as np
weights = np.array(data).flatten()
pd2org(df.describe())
col | |
---|---|
count | 57 |
mean | 7.79263 |
std | 1.15286 |
min | 5.31 |
25% | 7.13 |
50% | 8.37 |
75% | 8.6 |
max | 8.78 |
Является задачей по упаковке в контейнеры. NP-трудна.
use as few boxes as possible
cutting stock problem
- https://en.wikipedia.org/wiki/Bin_packing_problem
- https://scipbook.readthedocs.io/en/latest/bpp.html
min (i)sum((j)sum(xij)/(j)sum(xij))
si for xi
- (i)sum(s_i*x_ij) <= b_j*y_j, for every j. where y_j = (j)sum(xij)/(j)sum(xij)
- (j)sum(xij) = 1 for every i - only in one container
- x_ij - a boolean variable that indicates whether item i is packaed in bin j
- y_j - a boolean variable if bin j is used
- s_i - size of i item
- b_j - capacity of j
- i = 1..n
- j = 1..u
minimize: sum(y_j) - minimization of the number of bins used
subject to:
- (j)sum(x_ij) = 1, for every i.
- (i)sum(s_i*x_ij) <= b_j*y_j, for every j. where y_j = (j)sum(xij)/(j)sum(xij)
- x_ij <= y_j, for every i and j. - ????????
- x_ij ∈ {0,1}
- y_ ∈ {0,1}
where
- force the placement of each item in one bin
- the upper limit on the bins contents, as well as the fact that items cannot be packed in a bin that is not in use
- xi - a boolean variable that indicates whether item is included in the knapsack
- n - the total number of items,
- si - the size of item
- C - the capacity of the knapsack
The problem:
- max (i..n)∑
? = 22.2 27.6
x1 + x2 + x3 < n
sum(x1 + x2 + x3 + …) = count(n)
f= sum( x1 + x2 + x3)
def BinPackingExample():
B = 9
w = [2,3,4,5,6,7,8]
q = [4,2,6,6,2,2,2]
s=[]
for j in range(len(w)):
for i in range(q[j]):
s.append(w[j])
return s,B
def FFD(s, B):
"""heuristic - pack to containers
:return [[8], [8], [7, 2], [7, 2], [6, 3], ...]"""
remain = [B]
sol = [[]]
for item in sorted(s, reverse=True):
for j,free in enumerate(remain):
if free >= item:
remain[j] -= item
sol[j].append(item)
break
else:
sol.append([item])
remain.append(B-item)
return sol
s, B = BinPackingExample()
print(s, B)
print(FFD(s, B))
[2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 8, 8] 9 [[8], [8], [7, 2], [7, 2], [6, 3], [6, 3], [5, 4], [5, 4], [5, 4], [5, 4], [5, 4], [5, 4], [2, 2]]
from pyscipopt import Model
from pyscipopt import Model, quicksum, multidict
def bpp(s,B):
" "
n = len(s)
U = len(FFD(s,B))
model = Model("bpp")
x,y = {},{}
# Variables - binary
for i in range(n):
for j in range(U):
x[i,j] = model.addVar(vtype="B", name="x(%s,%s)"%(i,j))
for j in range(U):
y[j] = model.addVar(vtype="B", name="y(%s)"%j)
# Constraints
# Each item must be in exactly one bin.
for i in range(n):
model.addCons(quicksum(x[i,j] for j in range(U)) == 1, "Assign(%s)"%i)
# The amount packed in each bin cannot exceed its capacity.
for j in range(U):
model.addCons(quicksum(s[i]*x[i,j] for i in range(n)) <= B*y[j], "Capac(%s)"%j)
for j in range(U):
for i in range(n):
model.addCons(x[i,j] <= y[j], "Strong(%s,%s)"%(i,j))
model.setObjective(quicksum(y[j] for j in range(U)), "minimize")
model.data = x,y
return model
def solveBinPacking(s,B):
n = len(s)
U = len(FFD(s,B))
model = bpp(s,B)
x,y = model.data
model.optimize()
bins = [[] for i in range(U)]
for (i,j) in x:
if model.getVal(x[i,j]) > .5:
bins[j].append(s[i])
for i in range(bins.count([])):
bins.remove([])
for b in bins:
b.sort()
bins.sort()
return bins
print(solveBinPacking(s, B))
presolving: (round 1, exhaustive) 0 del vars, 0 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 349 upgd conss, 0 impls, 505 clqs (round 2, fast) 0 del vars, 0 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 26 chg coeffs, 349 upgd conss, 0 impls, 505 clqs (0.0s) probing: 51/325 (15.7%) - 0 fixings, 0 aggregations, 0 implications, 0 bound changes (0.0s) probing aborted: 50/50 successive totally useless probings (0.0s) symmetry computation started: requiring (bin +, int -, cont +), (fixed: bin -, int +, cont -) (0.0s) symmetry computation finished: 29 generators found (max: 1500, log10 of symmetry group size: 18.1) (symcode time: 0.00) (round 3, exhaustive) 0 del vars, 0 del conss, 51 add conss, 0 chg bounds, 0 chg sides, 26 chg coeffs, 349 upgd conss, 0 impls, 573 clqs (round 4, exhaustive) 0 del vars, 0 del conss, 51 add conss, 0 chg bounds, 0 chg sides, 26 chg coeffs, 397 upgd conss, 0 impls, 573 clqs presolving (5 rounds: 5 fast, 4 medium, 4 exhaustive): 0 deleted vars, 0 deleted constraints, 51 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 26 changed coefficients 0 implications, 573 cliques presolved problem has 325 variables (325 bin, 0 int, 0 impl, 0 cont) and 400 constraints 13 constraints of type <knapsack> 384 constraints of type <setppc> 3 constraints of type <orbitope> transformed objective value is always integral (scale: 1) Presolving Time: 0.02 time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl. 0.0s| 1 | 0 | 605 | - | 7312k | 0 | 325 | 431 | 397 | 0 | 0 | 42 | 0 | 1.244444e+01 | -- | Inf | unknown 0.1s| 1 | 0 | 671 | - | 7360k | 0 | 325 | 431 | 38 | 0 | 0 | 42 | 0 | 1.300000e+01 | -- | Inf | unknown 0.1s| 1 | 0 | 700 | - | 7432k | 0 | 325 | 75 | 44 | 8 | 1 | 45 | 0 | 1.300000e+01 | -- | Inf | unknown 0.1s| 1 | 0 | 731 | - | 7556k | 0 | 325 | 73 | 53 | 17 | 2 | 45 | 0 | 1.300000e+01 | -- | Inf | unknown 0.1s| 1 | 0 | 751 | - | 7765k | 0 | 325 | 73 | 60 | 24 | 3 | 45 | 0 | 1.300000e+01 | -- | Inf | unknown 0.1s| 1 | 0 | 764 | - | 8055k | 0 | 325 | 73 | 67 | 31 | 4 | 45 | 0 | 1.300000e+01 | -- | Inf | unknown 0.1s| 1 | 0 | 780 | - | 8453k | 0 | 325 | 76 | 75 | 39 | 5 | 48 | 0 | 1.300000e+01 | -- | Inf | unknown 0.1s| 1 | 0 | 796 | - | 9233k | 0 | 325 | 76 | 81 | 45 | 6 | 48 | 0 | 1.300000e+01 | -- | Inf | unknown 0.1s| 1 | 0 | 809 | - | 9528k | 0 | 325 | 76 | 85 | 49 | 7 | 48 | 0 | 1.300000e+01 | -- | Inf | unknown 0.1s| 1 | 0 | 823 | - | 10M | 0 | 325 | 78 | 90 | 54 | 8 | 50 | 0 | 1.300000e+01 | -- | Inf | unknown 0.1s| 1 | 0 | 837 | - | 11M | 0 | 325 | 78 | 93 | 57 | 9 | 50 | 0 | 1.300000e+01 | -- | Inf | unknown 0.2s| 1 | 0 | 851 | - | 11M | 0 | 325 | 79 | 98 | 62 | 10 | 51 | 0 | 1.300000e+01 | -- | Inf | unknown r 0.2s| 1 | 0 | 851 | - |shifting| 0 | 325 | 79 | 98 | 62 | 10 | 51 | 0 | 1.300000e+01 | 1.300000e+01 | 0.00%| unknown 0.2s| 1 | 0 | 851 | - | 11M | 0 | 325 | 79 | 98 | 62 | 10 | 51 | 0 | 1.300000e+01 | 1.300000e+01 | 0.00%| unknown SCIP Status : problem is solved [optimal solution found] Solving Time (sec) : 0.16 Solving Nodes : 1 Primal Bound : +1.30000000000000e+01 (1 solutions) Dual Bound : +1.30000000000000e+01 Gap : 0.00 % [[2, 3, 4], [2, 6], [2, 7], [2, 7], [3, 5], [4, 5], [4, 5], [4, 5], [4, 5], [4, 5], [6], [8], [8]]
import numpy as np
def BinPackingExample():
B = 9
w = [2,3,4,5,6,7,8]
q = [4,2,6,6,2,2,2]
s=[]
for j in range(len(w)):
for i in range(q[j]):
s.append(w[j])
return s,B
def FFD(s, B):
"""heuristic - pack to containers
:return [[8], [8], [7, 2], [7, 2], [6, 3], ...]"""
remain = [B]
sol = [[]]
for item in sorted(s, reverse=True):
for j,free in enumerate(remain):
if free >= item:
remain[j] -= item
sol[j].append(item)
break
else:
sol.append([item])
remain.append(B-item)
return sol
# s, B = BinPackingExample()
# print(s, B)
# print(FFD(s, B))
from pyscipopt import Model
from pyscipopt import Model, quicksum, multidict
def bpp(s,bes):
" "
# - patch
B=np.min(bes) # min
# print("Bmin", B)
n = len(s)
U = len(FFD(s,B))
# - patch
b_per = U //len(bes)
Bs = np.array([[x]*b_per for x in bes]).flatten()
if U > Bs.shape[0]:
Bs = np.append(Bs, (U - Bs.shape[0])*[bes[-1]])
# print("Bs, U", Bs, U)
# quit()
model = Model("bpp")
x,y = {},{}
# Variables - binary
for i in range(n):
for j in range(U):
x[i,j] = model.addVar(vtype="B", name="x(%s,%s)"%(i,j))
for j in range(U):
y[j] = model.addVar(vtype="B", name="y(%s)"%j)
# Constraints
# Each item must be in exactly one bin.
for i in range(n):
model.addCons(quicksum(x[i,j] for j in range(U)) == 1, "Assign(%s)"%i)
# The amount packed in each bin cannot exceed its capacity.
for j in range(U):
B = Bs[j-1]
model.addCons(quicksum(s[i]*x[i,j] for i in range(n)) <= B*y[j], "Capac(%s)"%j)
for j in range(U):
for i in range(n):
model.addCons(x[i,j] <= y[j], "Strong(%s,%s)"%(i,j))
model.setObjective(quicksum(y[j] for j in range(U)), "minimize")
model.data = x,y
return model, U,
def solveBinPacking(s,bes):
n = len(s)
# U = len(FFD(s,B))
model, U = bpp(s,bes)
x,y = model.data
# quit()
# print("y",y)
model.optimize()
# quit()
# print("x",[print(model.getVal(x[v])) for v in x])
bins = [[] for i in range(U)]
for (i,j) in x:
if model.getVal(x[i,j]) > .5:
bins[j].append(s[i])
# -- counts bins
# for x in bes
# b1 = 0
# b2 = 0
# for i, b in enumerate(bins):
# if len(b) > 0:
# if i <= U/2:
# b1+=1
# else:
# b2+=1
# print(b1,b2)
# for i in range(bins.count([])):
# bins.remove([])
# for b in bins:
# b.sort()
# bins.sort()
return bins
weights = np.array(data).flatten()
print(weights)
print(solveBinPacking(weights, [22.2, 27.6]))
presolving: (round 1, exhaustive) 0 del vars, 0 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 798 upgd conss, 0 impls, 798 clqs (0.0s) probing: 51/754 (6.8%) - 0 fixings, 0 aggregations, 0 implications, 0 bound changes (0.0s) probing aborted: 50/50 successive totally useless probings (0.0s) symmetry computation started: requiring (bin +, int -, cont +), (fixed: bin -, int +, cont -) (0.0s) symmetry computation finished: 23 generators found (max: 1500, log10 of symmetry group size: 12.5) (symcode time: 0.01) presolving (2 rounds: 2 fast, 2 medium, 2 exhaustive): 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients 0 implications, 798 cliques presolved problem has 754 variables (754 bin, 0 int, 0 impl, 0 cont) and 811 constraints 798 constraints of type <setppc> 13 constraints of type <linear> transformed objective value is always integral (scale: 1) Presolving Time: 0.03 time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl. p 0.0s| 1 | 0 | 0 | - | clique| 0 | 754 | 811 | 811 | 0 | 0 | 0 | 0 | 0.000000e+00 | 1.000000e+01 | Inf | unknown 0.1s| 1 | 0 | 1785 | - | 14M | 0 | 754 | 847 | 811 | 0 | 0 | 36 | 0 | 8.883600e+00 | 1.000000e+01 | 12.57%| unknown 0.2s| 1 | 0 | 1785 | - | 14M | 0 | 754 | 847 | 785 | 0 | 0 | 36 | 0 | 8.883600e+00 | 1.000000e+01 | 12.57%| unknown 0.2s| 1 | 0 | 1886 | - | 15M | 0 | 754 | 821 | 787 | 9 | 1 | 36 | 0 | 8.883600e+00 | 1.000000e+01 | 12.57%| unknown 0.3s| 1 | 0 | 1964 | - | 17M | 0 | 754 | 814 | 795 | 17 | 2 | 36 | 0 | 8.883600e+00 | 1.000000e+01 | 12.57%| unknown 0.4s| 1 | 0 | 2020 | - | 19M | 0 | 754 | 814 | 799 | 21 | 3 | 36 | 0 | 8.883600e+00 | 1.000000e+01 | 12.57%| unknown 0.5s| 1 | 0 | 2043 | - | 21M | 0 | 754 | 812 | 804 | 26 | 4 | 36 | 0 | 8.883600e+00 | 1.000000e+01 | 12.57%| unknown 0.7s| 1 | 0 | 2072 | - | 24M | 0 | 754 | 812 | 808 | 30 | 5 | 36 | 0 | 8.883600e+00 | 1.000000e+01 | 12.57%| unknown 0.9s| 1 | 0 | 2509 | - | 26M | 0 | 754 | 812 | 815 | 37 | 6 | 36 | 0 | 8.883600e+00 | 1.000000e+01 | 12.57%| unknown 0.9s| 1 | 0 | 2571 | - | 27M | 0 | 754 | 812 | 820 | 42 | 7 | 36 | 0 | 8.883600e+00 | 1.000000e+01 | 12.57%| unknown 1.1s| 1 | 0 | 2629 | - | 30M | 0 | 754 | 812 | 828 | 50 | 8 | 36 | 0 | 8.883600e+00 | 1.000000e+01 | 12.57%| unknown 1.2s| 1 | 0 | 2659 | - | 32M | 0 | 754 | 812 | 835 | 57 | 9 | 36 | 0 | 8.883600e+00 | 1.000000e+01 | 12.57%| unknown 1.3s| 1 | 0 | 2686 | - | 33M | 0 | 754 | 812 | 838 | 60 | 10 | 36 | 0 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 1.4s| 1 | 0 | 2743 | - | 33M | 0 | 754 | 812 | 843 | 65 | 11 | 36 | 0 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 1.4s| 1 | 0 | 2798 | - | 33M | 0 | 754 | 812 | 852 | 74 | 12 | 36 | 0 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl. 1.4s| 1 | 0 | 2850 | - | 34M | 0 | 754 | 812 | 860 | 82 | 13 | 36 | 0 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 1.5s| 1 | 0 | 2906 | - | 34M | 0 | 754 | 812 | 870 | 92 | 14 | 36 | 0 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 1.5s| 1 | 0 | 2933 | - | 34M | 0 | 754 | 812 | 878 | 100 | 15 | 36 | 0 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 1.6s| 1 | 0 | 2990 | - | 34M | 0 | 754 | 812 | 856 | 110 | 16 | 36 | 0 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 1.6s| 1 | 0 | 3043 | - | 34M | 0 | 754 | 813 | 866 | 120 | 17 | 37 | 0 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 1.6s| 1 | 0 | 3083 | - | 35M | 0 | 754 | 813 | 873 | 127 | 18 | 37 | 0 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 1.6s| 1 | 0 | 3112 | - | 35M | 0 | 754 | 813 | 877 | 131 | 19 | 37 | 0 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 1.6s| 1 | 0 | 3134 | - | 35M | 0 | 754 | 813 | 882 | 136 | 20 | 37 | 0 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 1.8s| 1 | 2 | 3963 | - | 35M | 0 | 754 | 791 | 882 | 136 | 20 | 40 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown (run 1, node 1) restarting after 58 global fixings of integer variables (restart) converted 97 cuts from the global cut pool into linear constraints presolving: (round 1, fast) 58 del vars, 13 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 80 chg coeffs, 0 upgd conss, 0 impls, 741 clqs (round 2, exhaustive) 58 del vars, 13 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 80 chg coeffs, 65 upgd conss, 0 impls, 741 clqs (round 3, fast) 58 del vars, 13 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 86 chg coeffs, 65 upgd conss, 0 impls, 741 clqs (round 4, exhaustive) 58 del vars, 16 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 113 chg coeffs, 65 upgd conss, 0 impls, 741 clqs presolving (5 rounds: 5 fast, 3 medium, 3 exhaustive): 58 deleted vars, 16 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 113 changed coefficients 0 implications, 741 cliques presolved problem has 696 variables (696 bin, 0 int, 0 impl, 0 cont) and 872 constraints 61 constraints of type <knapsack> 741 constraints of type <setppc> 44 constraints of type <linear> 26 constraints of type <logicor> transformed objective value is always integral (scale: 1) Presolving Time: 0.06 transformed 6/7 original solutions to the transformed problem space time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl. 1.9s| 1 | 0 | 4445 | - | 33M | 0 | 696 | 872 | 847 | 0 | 0 | 40 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 2.0s| 1 | 0 | 4472 | - | 33M | 0 | 696 | 872 | 855 | 8 | 1 | 40 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 2.0s| 1 | 0 | 4573 | - | 34M | 0 | 696 | 872 | 863 | 16 | 2 | 40 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 2.1s| 1 | 0 | 4657 | - | 34M | 0 | 696 | 872 | 870 | 23 | 3 | 40 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 2.2s| 1 | 0 | 4722 | - | 34M | 0 | 696 | 872 | 880 | 33 | 4 | 40 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 2.4s| 1 | 0 | 4799 | - | 35M | 0 | 696 | 872 | 890 | 43 | 5 | 40 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 2.5s| 1 | 0 | 4842 | - | 37M | 0 | 696 | 872 | 898 | 51 | 6 | 40 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 2.7s| 1 | 0 | 4891 | - | 37M | 0 | 696 | 872 | 906 | 59 | 7 | 40 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 2.9s| 1 | 0 | 4959 | - | 38M | 0 | 696 | 872 | 915 | 68 | 8 | 40 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 3.1s| 1 | 0 | 4984 | - | 39M | 0 | 696 | 872 | 922 | 75 | 9 | 40 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 3.3s| 1 | 0 | 5040 | - | 43M | 0 | 696 | 872 | 928 | 81 | 10 | 40 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 3.4s| 1 | 0 | 5118 | - | 43M | 0 | 696 | 873 | 939 | 92 | 11 | 41 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 3.4s| 1 | 0 | 5199 | - | 43M | 0 | 696 | 873 | 947 | 100 | 12 | 41 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 3.5s| 1 | 0 | 5240 | - | 43M | 0 | 696 | 873 | 956 | 109 | 13 | 41 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 3.5s| 1 | 0 | 5280 | - | 43M | 0 | 696 | 873 | 962 | 115 | 14 | 41 | 12 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl. 3.6s| 1 | 2 | 5781 | - | 43M | 0 | 696 | 876 | 962 | 115 | 14 | 44 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| unknown 5.1s| 100 | 91 | 16341 | 119.2 | 44M | 36 | 696 | 899 | 776 | 138 | 1 | 71 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 1.22% 5.8s| 200 | 191 | 20660 | 81.2 | 48M | 44 | 696 | 901 | 781 | 218 | 2 | 73 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 1.22% 6.4s| 300 | 291 | 23821 | 64.7 | 51M | 44 | 696 | 903 | 786 | 271 | 1 | 75 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 1.22% 7.2s| 400 | 391 | 27312 | 57.2 | 55M | 45 | 696 | 906 | 776 | 390 | 1 | 78 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 1.22% 7.7s| 500 | 491 | 29384 | 49.9 | 55M | 55 | 696 | 907 | 784 | 515 | 1 | 79 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 1.22% 8.1s| 600 | 589 | 31396 | 45.0 | 56M | 55 | 696 | 908 | 788 | 622 | 1 | 80 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 1.22% 8.5s| 700 | 687 | 32905 | 40.7 | 56M | 72 | 696 | 909 | 797 | 709 | 2 | 81 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 1.22% 8.9s| 800 | 739 | 33606 | 36.5 | 56M | 91 | 696 | 913 | 801 | 727 | 0 | 85 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 1.22% 9.1s| 900 | 771 | 34236 | 33.1 | 57M | 98 | 696 | 861 | 796 | 749 | 1 | 90 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 9.6s| 1000 | 828 | 34686 | 30.3 | 56M | 98 | 696 | 911 | 796 | 754 | 0 | 140 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 10.0s| 1100 | 860 | 35096 | 27.9 | 56M | 98 | 696 | 980 | 796 | 756 | 1 | 209 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 10.2s| 1200 | 887 | 35593 | 26.0 | 57M | 98 | 696 |1000 | 0 | 760 | 0 | 229 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 10.5s| 1300 | 933 | 36238 | 24.5 | 57M | 98 | 696 |1031 | 797 | 778 | 1 | 260 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 11.1s| 1400 | 1001 | 37036 | 23.3 | 57M | 98 | 696 |1097 | 797 | 806 | 1 | 326 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl. 11.4s| 1500 | 1057 | 37638 | 22.1 | 57M | 98 | 696 |1101 | 800 | 821 | 0 | 330 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 11.6s| 1600 | 1093 | 38161 | 21.1 | 57M | 98 | 696 |1104 | 799 | 823 | 0 | 333 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 11.8s| 1700 | 1109 | 38649 | 20.1 | 57M | 98 | 696 |1115 | 0 | 826 | 0 | 344 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 12.3s| 1800 | 1158 | 39293 | 19.4 | 57M | 98 | 696 |1134 | 799 | 840 | 1 | 363 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 12.6s| 1900 | 1202 | 39843 | 18.6 | 57M | 98 | 696 |1147 | 801 | 855 | 2 | 376 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 12.9s| 2000 | 1232 | 40375 | 18.0 | 57M | 98 | 696 |1158 | 796 | 858 | 1 | 387 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 13.3s| 2100 | 1252 | 40835 | 17.3 | 57M | 98 | 696 |1208 | 800 | 865 | 0 | 437 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 13.6s| 2200 | 1280 | 41372 | 16.8 | 57M | 98 | 696 |1227 | 800 | 869 | 0 | 456 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 13.9s| 2300 | 1298 | 41860 | 16.3 | 57M | 98 | 696 |1245 | 796 | 871 | 1 | 475 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 14.3s| 2400 | 1329 | 42310 | 15.8 | 57M | 98 | 696 |1288 | 0 | 882 | 0 | 518 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 14.7s| 2500 | 1357 | 42577 | 15.3 | 57M | 98 | 696 |1318 | 801 | 892 | 0 | 548 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 15.0s| 2600 | 1375 | 43073 | 14.9 | 57M | 98 | 696 |1358 | 798 | 897 | 1 | 589 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 15.3s| 2700 | 1387 | 43830 | 14.6 | 58M | 98 | 696 |1364 | 799 | 900 | 1 | 595 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 15.4s| 2800 | 1399 | 44344 | 14.3 | 58M | 99 | 696 |1380 | 797 | 904 | 1 | 611 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 15.6s| 2900 | 1403 | 44786 | 13.9 | 58M | 99 | 696 |1459 | 800 | 904 | 1 | 690 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl. 15.8s| 3000 | 1426 | 45314 | 13.6 | 58M | 99 | 696 |1463 | 801 | 911 | 0 | 694 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 16.0s| 3100 | 1460 | 46031 | 13.4 | 58M | 99 | 696 |1471 | 800 | 915 | 1 | 702 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 16.1s| 3200 | 1475 | 46509 | 13.2 | 58M | 102 | 696 |1553 | 800 | 918 | 1 | 784 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 16.3s| 3300 | 1500 | 47027 | 12.9 | 59M | 102 | 696 |1625 | 798 | 928 | 1 | 856 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 16.5s| 3400 | 1509 | 47486 | 12.7 | 59M | 102 | 696 |1660 | 800 | 934 | 1 | 891 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 16.7s| 3500 | 1513 | 47924 | 12.4 | 59M | 102 | 696 |1691 | 801 | 936 | 0 | 923 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 16.9s| 3600 | 1533 | 48534 | 12.3 | 59M | 102 | 696 |1711 | 800 | 944 | 1 | 943 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 17.1s| 3700 | 1556 | 49109 | 12.1 | 59M | 102 | 696 |1749 | 800 | 951 | 1 | 981 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 17.4s| 3800 | 1570 | 49616 | 11.9 | 59M | 102 | 696 |1798 | 0 | 957 | 0 |1030 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 17.6s| 3900 | 1585 | 50243 | 11.7 | 59M | 102 | 696 |1826 | 801 | 962 | 0 |1058 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 17.8s| 4000 | 1591 | 50734 | 11.6 | 59M | 102 | 696 |1859 | 800 | 969 | 1 |1091 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 18.1s| 4100 | 1608 | 51436 | 11.5 | 59M | 102 | 696 |1906 | 797 | 975 | 1 |1139 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 18.2s| 4200 | 1610 | 52020 | 11.3 | 59M | 102 | 696 |1919 | 799 | 981 | 1 |1152 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 18.4s| 4300 | 1644 | 52467 | 11.2 | 59M | 102 | 696 |1928 | 799 | 990 | 1 |1162 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 18.7s| 4400 | 1665 | 52952 | 11.0 | 59M | 102 | 696 |1958 | 799 |1000 | 1 |1194 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl. 19.1s| 4500 | 1689 | 53404 | 10.9 | 59M | 102 | 696 |1986 | 798 |1010 | 0 |1222 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 19.2s| 4600 | 1704 | 53890 | 10.8 | 59M | 102 | 696 |2009 | 783 |1011 | 1 |1247 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 19.6s| 4700 | 1804 | 55880 | 10.9 | 59M | 102 | 696 |2006 | 790 |1063 | 1 |1251 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 19.8s| 4800 | 1902 | 57452 | 11.0 | 59M | 102 | 696 |2017 | 787 |1093 | 1 |1265 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 20.1s| 4900 | 1996 | 58609 | 11.1 | 60M | 102 | 696 |2032 | 789 |1126 | 1 |1282 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 20.2s| 5000 | 2071 | 59468 | 11.0 | 60M | 102 | 696 |2055 | 790 |1147 | 0 |1306 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 20.4s| 5100 | 2108 | 60009 | 10.9 | 60M | 102 | 696 |2070 | 793 |1166 | 0 |1321 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 20.6s| 5200 | 2166 | 60842 | 10.9 | 60M | 102 | 696 |2084 | 786 |1186 | 1 |1339 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 20.8s| 5300 | 2240 | 61934 | 10.9 | 60M | 102 | 696 |2081 | 791 |1225 | 1 |1340 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 20.9s| 5400 | 2309 | 62399 | 10.7 | 60M | 102 | 696 |2162 | 792 |1226 | 1 |1422 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 21.1s| 5500 | 2360 | 62953 | 10.6 | 60M | 102 | 696 |2218 | 0 |1236 | 0 |1481 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 21.2s| 5600 | 2396 | 63346 | 10.5 | 60M | 102 | 696 |2283 | 793 |1241 | 1 |1546 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 21.4s| 5700 | 2457 | 64154 | 10.5 | 60M | 102 | 696 |2286 | 791 |1260 | 1 |1554 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 21.6s| 5800 | 2539 | 64861 | 10.4 | 60M | 102 | 696 |2312 | 792 |1273 | 0 |1580 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% 21.7s| 5900 | 2613 | 65589 | 10.4 | 60M | 102 | 696 |2306 | 792 |1288 | 0 |1580 | 13 | 9.000000e+00 | 1.000000e+01 | 11.11%| 51.22% time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl. r21.9s| 5979 | 0 | 66116 | 10.3 |randroun| 102 | 696 |2304 | 788 |1298 | 1 |1604 | 13 | 9.000000e+00 | 9.000000e+00 | 0.00%| 100.00% SCIP Status : problem is solved [optimal solution found] Solving Time (sec) : 21.90 Solving Nodes : 5979 (total of 5980 nodes in 2 runs) Primal Bound : +9.00000000000000e+00 (119 solutions) Dual Bound : +9.00000000000000e+00 Gap : 0.00 % [[], [8.62, 8.57, 8.31, 7.14, 6.03, 5.75, 5.31], [], [8.5, 8.47, 8.2, 8.12, 5.74, 5.64, 5.31], [], [], [8.63, 8.63, 8.49, 8.26, 8.12, 7.85], [8.77, 8.72, 8.53, 8.44, 8.27, 7.06], [8.7, 8.62, 8.6, 8.42, 8.33, 5.81], [8.74, 8.73, 8.61, 8.37, 8.31, 6.3], [8.41, 8.39, 8.38, 8.28, 8.27, 8.15], [8.77, 8.62, 8.53, 8.49, 7.13, 6.31], [8.78, 8.76, 8.57, 6.02, 5.78, 5.76, 5.76]]
import pandas as pd
def pd2org(df_to_table):
return tabulate(df_to_table, headers=df_to_table.columns, tablefmt='orgtbl')
df = pd.DataFrame(data, columns=['weight'])
pd2org(df.describe())
weight | |
---|---|
count | 57 |
mean | 7.79263 |
std | 1.15286 |
min | 5.31 |
25% | 7.13 |
50% | 8.37 |
75% | 8.6 |
max | 8.78 |
import numpy as np
weights = np.array(data).flatten()
print(weights)
[8.78 8.77 8.77 8.76 8.74 8.73 8.72 8.7 8.63 8.63 8.62 8.62 8.62 8.61 8.6 8.57 8.57 8.53 8.53 8.5 8.49 8.49 8.47 8.44 8.42 8.41 8.39 8.38 8.37 8.33 8.31 8.31 8.28 8.27 8.27 8.26 8.2 8.15 8.12 8.12 7.85 7.14 7.13 7.06 6.31 6.3 6.03 6.02 5.81 5.78 5.76 5.76 5.75 5.74 5.64 5.31 5.31]
import numpy as np
from scipy import optimize
sizes = weights
bounds = optimize.Bounds(0, 1) # 0 <= x_i <= 1
integrality = np.full_like(values, True) # x_i are integers
constraints = optimize.LinearConstraint(A=sizes, lb=0, ub=capacity)
import random
import numpy as np
import time
def FFD(s, bs):
"""heuristic - pack to containers
:return [[8], [8], [7, 2], [7, 2], [6, 3], ...]"""
bin_sizes=[]
r = random.randint(0,len(bs)-1)
remain = [bs[r]]
bin_sizes.append(bs[r])
sol = [[]]
for item in sorted(s, reverse=True):
for j,free in enumerate(remain):
if free >= item:
remain[j] -= item
sol[j].append(item)
break
else:
sol.append([item])
r = random.randint(0,len(bs)-1)
remain.append(bs[r]-item)
bin_sizes.append(bs[r])
return sol, bin_sizes
start_time = time.time()
# print(weight)
# weight = np.array(data).flatten()
weight = [8.78, 8.77, 8.77, 8.76, 8.74, 8.73, 8.72, 8.7, 8.63, 8.63, 8.62, 8.62, 8.62, 8.61, 8.6, 8.57, 8.57, 8.53, 8.53, 8.5, 8.49, 8.49, 8.47, 8.44, 8.42, 8.41, 8.39, 8.38, 8.37, 8.33, 8.31, 8.31, 8.28, 8.27, 8.27, 8.26, 8.2, 8.15, 8.12, 8.12, 7.85, 7.14, 7.13, 7.06, 6.31, 6.3, 6.03, 6.02, 5.81, 5.78, 5.76, 5.76, 5.75, 5.74, 5.64, 5.31, 5.31]
bins_s = [22.2, 27.6]
c = 12
# min_bins = len(weight)
# min_mass = max(bins_s)
mer = 99999999999999999
s,b = None, None
for _ in range(10000):
sol, bs = FFD(weight,bins_s)
# if len(sol) < min_bins or sum(bs) < min_mass:
if (len(sol) + sum(bs)) < mer:
s = sol
b = bs
# min_bins=len(sol)
mer = len(sol) + sum(bs)
import collections
print(s)
print(collections.Counter(b))
print("time seconds:", round(time.time() - start_time))
[[8.78, 8.77, 8.77], [8.76, 8.74, 8.73], [8.72, 8.7, 8.63], [8.63, 8.62, 8.62], [8.62, 8.61, 8.6], [8.57, 8.57, 8.53], [8.53, 8.5, 8.49], [8.49, 8.47, 8.44], [8.42, 8.41, 8.39], [8.38, 8.37, 5.31], [8.33, 8.31, 8.31], [8.28, 8.27, 8.27], [8.26, 8.2, 5.74], [8.15, 8.12, 5.81], [8.12, 7.85, 6.03], [7.14, 7.13, 7.06, 6.02], [6.31, 6.3, 5.78, 5.76], [5.76, 5.75, 5.64, 5.31]] Counter({27.6: 14, 22.2: 4}) time seconds: 1