Column generation with pulp-or (Python)

CG.py

import random  ## to generate the items
from pulp import * ## import pulp-or functions


	
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
		
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)])<=maxValue 

        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
	
		
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


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


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

Excellent implementation ! Bart6114

Thanks for the code. In solve function, the duals are all None for me, although the model is solved and the status is optimal. Do you have any ideas why this happens?

Such helpful code but I am very new to pulp/column generation and wondering how i can specify my required (numeric) demand/lengths/raw material length.

Old guy trying to learn new tricks here (GaTech'75). Downloaded code but am having some issues. 1) Does it run correctly straight out of the box in PY2? I converted to PY3 but may have missed a thing or two. Fixed the PY2 vs PY3 print issues. Eliminated the ---> tabs (could have just been how the file was created. I'm in Jupyter NB) 3) It "runs" now in the NB, but has run for 7 hours or so with zero output. My computer is a bit old (Intel 8700/10 yrs ish w/64GB). Does it run that long? I know it could. Combinatorials have that issue. That's why we look at CG. 3) None value was not handled well in PY3. My conversion attempt may have been too simple.

Thoughts appreciated. My next attempt will be a venv with PY2 and Pulp. Might do it, but will still go back and fix PY3. Thanks for reading.

My eyesight isn't what it used to be, but did I miss a "Reply" button. If I could, I would comment to a user or two. Thanks.