""" bpp.py: use gurobi for solving the bin packing problem. The instance of the bin packing problem is represented by the two lists of n items of sizes and quantity s=(s_i). The bin size is B. We use Martello and Toth (1990) formulation, and suggest extensions with tie-breaking and SOS constraints. Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012 """ from gurobipy import * def FFD(s,B): """First Fit Decreasing heuristics for the Bin Packing Problem. Parameters: - s: list with item widths - B: bin capacity Returns a list of lists with bin compositions. """ remain = [B] # keep list of empty space per bin sol = [[]] # a list ot items (i.e., sizes) on each used bin 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: #does not fit in any bin sol.append([item]) remain.append(B-item) return sol def bpp(s,B): """bpp: Martello and Toth's model to solve the bin packing problem. Parameters: - s: list with item widths - B: bin capacity Returns a model, ready to be solved. """ n = len(s) U = len(FFD(s,B)) # upper bound of the number of bins model = Model("bpp") # setParam("MIPFocus",1) x,y = {},{} 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) model.update() # assignment constraints for i in range(n): model.addConstr(quicksum(x[i,j] for j in range(U)) == 1, "Assign(%s)"%i) # bin capacity constraints for j in range(U): model.addConstr(quicksum(s[i]*x[i,j] for i in range(n)) <= B*y[j], "Capac(%s)"%j) # tighten assignment constraints for j in range(U): for i in range(n): model.addConstr(x[i,j] <= y[j], "Strong(%s,%s)"%(i,j)) ## # tie breaking constraints ## for j in range(U-1): ## model.addConstr(y[j] >= y[j+1),"TieBrk(%s)"%j) ## ## # SOS constraints ## for i in range(n): ## model.addSOS(1,[x[i,j] for j in range(U)]) model.setObjective(quicksum(y[j] for j in range(U)), GRB.MINIMIZE) model.update() model.__data = x,y return model def solveBinPacking(s,B): """solveBinPacking: use an IP model to solve the in Packing Problem. Parameters: - s: list with item widths - B: bin capacity Returns a solution: list of lists, each of which with the items in a roll. """ n = len(s) U = len(FFD(s,B)) # upper bound of the number of bins model = bpp(s,B) x,y = model.__data model.optimize() bins = [[] for i in range(U)] for (i,j) in x: if x[i,j].X > .5: bins[j].append(s[i]) for i in range(bins.count([])): bins.remove([]) for b in bins: b.sort() bins.sort() return bins import random def DiscreteUniform(n=10,LB=1,UB=99,B=100): """DiscreteUniform: create random, uniform instance for the bin packing problem.""" B = 100 s = [0]*n for i in range(n): s[i] = random.randint(LB,UB) return s,B if __name__ == "__main__": random.seed(256) s,B = DiscreteUniform() print "items:",s print "bin size:",B ffd = FFD(s,B) print "\n\n\nSolution of FFD:" print ffd print len(ffd),"bins" print "\n\n\nBin packing problem:" bins = solveBinPacking(s,B) print len(bins),"bins:" print bins