Minimizing production waste can result in significant cost savings. However, calculating just the right production configuration can be a tedious task.
Let’s take the example of a firm which delivers sheet metal. The sheets it delivers are all of the same width but can differ in length. The raw material used by the company are metal sheets of 3 meters wide by 20 meters long. Clients can order any length metal sheets (as long as it doesn’t exceed 20 meters).
Let’s say there is demand for the following lengths of sheet metal (all are 3 meters wide). The number of demands are denoted in the next line. E.g. for 40 items of length 6 have to be produced, 5 items of length 9 have to be produced and so on.
How should we cut the raw material metal sheets, which are 20 meters long, so that we satisfy demand but minimize waste? Column generation is a very effective method to solve this problem (often referred to as the cutting-stock problem).
The column generation method consists of a master linear program and a slave integer program.
The master sets up the problem with initial feasible (but probably not optimal) cutting patterns. The example that follows is build using pulp-or, an LP-modeler for Python.
First let’s generate the above items and item demands;
random.seed(2012) nrItems=12 lengthSheets=20 itemLengths=[] itemDemands=[] while len(itemLengths)!=nrItems: length=random.randint(5, lengthSheets-2) demand=random.randint(5, 100) if length not in itemLengths: itemLengths.append(length) itemDemands.append(demand) print "Item lengts : %s" % itemLengths print "Item demands : %s\n\n" % itemDemands
Then we have to generate a set of feasible starting cut patterns. In this example I generate very simple patterns, however, much better starting patterns can be found, which would result in much faster solve times in large problems. The naive starting patterns are generated as follows.
patterns=[] print "Generating start patterns:" ## generate simple start patterns for x in range(nrItems): temp=[0.0 for y in range(x)] temp.append(1.0) temp+=[0.0 for y in range(nrItems-x-1)] patterns.append(temp) print temp
This code generates the following patterns:
Next we have to set up a master model and a slave model. The master model will solve the problem using the generated start patterns. Following that, we will use the resulting dual prices to set up the slave model. The results of the slave model will then be used to add a new pattern to the master problem.
Let’s take a look at the master model;
class MasterProblem:
def __init__(self, maxValue, itemLengths, itemDemands, initialPatterns, problemname):
self.maxValue=maxValue
self.itemLengths=itemLengths
self.itemDemands=itemDemands
self.initialPatterns=initialPatterns
self.prob = LpProblem(problemname,LpMinimize) # set up the problem
self.obj = LpConstraintVar("obj") # generate a constraint variable that will be used as the objective
self.prob.setObjective(self.obj)
self.PatternVars=[]
self.constraintList=[] # list to save constraint variables in
for i,x in enumerate(itemDemands): # create variables & set the constraints, in other words: set the minimum amount of items to be produced
var=LpConstraintVar("C"+str(i),LpConstraintGE,x) # create constraintvar and set to >= demand for item
self.constraintList.append(var)
self.prob+=var
for i,x in enumerate(self.initialPatterns): #save initial patterns and set column constraints
temp=[]
for j,y in enumerate(x):
if y>0:
temp.append(j)
var=LpVariable("Pat"+str(i) , 0, None, LpContinuous, lpSum(self.obj+[self.constraintList[v] for v in temp])) # create decision variable: will determine how often pattern x should be produced
self.PatternVars.append(var)
def solve(self):
self.prob.writeLP('prob.lp')
self.prob.solve() # start solve
return [self.prob.constraints[i].pi for i in self.prob.constraints]
def addPattern(self,pattern): # add new pattern to existing model
self.initialPatterns.append(pattern)
temp=[]
for j,y in enumerate(pattern):
if y>0:
temp.append(j)
var=LpVariable("Pat"+str(len(self.initialPatterns)) , 0, None, LpContinuous, lpSum(self.obj+[pattern[v]*self.constraintList[v] for v in temp]))
self.PatternVars.append(var)
def startSlave(self,duals): # create/run new slave and return new pattern (if available)
newSlaveProb=SlaveProblem(duals,self.itemLengths,self.maxValue)
pattern=newSlaveProb.returnPattern()
return pattern
def setRelaxed(self,relaxed): # if no new patterns are available, solve model as IP problem
if relaxed==False:
for var in self.prob.variables():
var.cat = LpInteger
def getObjective(self):
return value(self.prob.objective)
def getUsedPatterns(self):
usedPatternList=[]
for i,x in enumerate(self.PatternVars):
if value(x)>0:
usedPatternList.append((value(x),self.initialPatterns[i]))
return usedPatternList
The slave model will then use the dual prices to generate a new column. This process will go on until the value of the solved slave model is –1, in other words, no better column can be generated (-1.0001 is used to account for rounding errors). The slave model is set up as follows;
class SlaveProblem:
def __init__(self,duals, itemLengths,maxValue):
self.slaveprob=LpProblem("Slave solver",LpMinimize)
self.varList=[LpVariable('S'+str(i),0,None,LpInteger) for i,x in enumerate(duals)]
self.slaveprob+=-lpSum([duals[i]*x for i,x in enumerate(self.varList)]) #use duals to set objective coefficients
self.slaveprob+=lpSum([itemLengths[i]*x for i,x in enumerate(self.varList)])
self.slaveprob.writeLP('slaveprob.lp')
self.slaveprob.solve()
self.slaveprob.roundSolution() #to avoid rounding problems
def returnPattern(self):
pattern=False
if value(self.slaveprob.objective) < -1.00001:
pattern=[]
for v in self.varList:
pattern.append(value(v))
return pattern
Then let’s set up the problem;
print "\n\nTrying to solve problem" CGprob=MasterProblem(lengthSheets,itemLengths,itemDemands,patterns,'1D cutting stock') relaxed=True while relaxed==True: # once no more new columns can be generated set relaxed to False duals=CGprob.solve() newPattern=CGprob.startSlave(duals) print 'New pattern: %s' % newPattern if newPattern: CGprob.addPattern(newPattern) else: CGprob.setRelaxed(False) CGprob.solve() relaxed=False print "\n\nSolution: %s sheets required" % CGprob.getObjective() t=CGprob.getUsedPatterns() for i,x in enumerate(t): print "Pattern %s: selected %s times %s" % (i,x[0],x[1])
And finally, the optimal cutting patterns will be outputted to the screen.
The complete .py file can be found here (dependency: pulp-or).