4 The instance of the bin packing problem is represented by the two
5 lists of n items of sizes and quantity s=(s_i).
8 We use Martello and Toth (1990) formulation, and suggest
9 extensions with tie-breaking and SOS constraints.
11 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
14 from pyscipopt
import Model, quicksum
17 """First Fit Decreasing heuristics for the Bin Packing Problem.
19 - s: list with item widths
21 Returns a list of lists with bin compositions.
25 for item
in sorted(s,reverse=
True):
26 for (j,free)
in enumerate(remain):
38 """bpp: Martello and Toth's model to solve the bin packing problem.
40 - s: list with item widths
42 Returns a model, ready to be solved.
51 x[i,j] = model.addVar(vtype=
"B", name=
"x(%s,%s)"%(i,j))
53 y[j] = model.addVar(vtype=
"B", name=
"y(%s)"%j)
57 model.addCons(
quicksum(x[i,j]
for j
in range(U)) == 1,
"Assign(%s)"%i)
61 model.addCons(
quicksum(s[i]*x[i,j]
for i
in range(n)) <= B*y[j],
"Capac(%s)"%j)
66 model.addCons(x[i,j] <= y[j],
"Strong(%s,%s)"%(i,j))
70 model.addCons(y[j] >= y[j+1],
"TieBrk(%s)"%j)
74 model.addConsSOS1([x[i,j]
for j
in range(U)])
76 model.setObjective(
quicksum(y[j]
for j
in range(U)),
"minimize")
83 """solveBinPacking: use an IP model to solve the in Packing Problem.
86 - s: list with item widths
89 Returns a solution: list of lists, each of which with the items in a roll.
98 bins = [[]
for i
in range(U)]
100 if model.getVal(x[i,j]) > .5:
102 for i
in range(bins.count([])):
112 """DiscreteUniform: create random, uniform instance for the bin packing problem."""
116 s[i] = random.randint(LB,UB)
120 if __name__ ==
"__main__":
124 print(
"bin size:", B)
127 print(
"\n\n\n FFD heuristic:")
130 print(len(ffd),
"bins")
132 print(
"\n\n\n IP formulation:")
136 print(len(bins),
"bins")