Column generation
technique is used in integer (pure or mixed) programming problem in which
enumeration of variables is very large. It can be viewed as matrix with small
number of rows with very large number of columns. Since, it is difficult to
enumerate the variables and incorporate in the problem column generation
technique is used which iteratively adds variables that seems feasible to
enter. It is similar to simplex method in which new variables are added into
the basis.
We look here column generation
problem on shortest path problem with time constraint. A set of nodes and arcs
are present with arc time and arc cost associated with each arc. The objective
is to reach from start node to end node while satisfying total path time within
threshold time value. The problem selected (Desaulniers, G., Desrosiers, J. and
Solomon, M.M., Column generation, Chapter 1,Springer, 2005, DOI: 10.1007/b135457)
is shown in below figure:
It is required to reach from node 1 to node 6 in shortest time while satisfying the total time constraint. The problem can be stated in MILP form as:
The problem involves in enumeration of paths such that objective is met. However, there are nine paths and it would become difficult for a problem involving thousands of nodes. In such cases, we would decompose the original problem into master problem and sub-problem. Start the master problem by randomly selecting a path and an artificial variable with very large coefficient. Upon solving the master problem without integer constraint and additional path variable. The sum of path variable would be one and time restriction constraints of original problem are used. The master problem which is so called as restricted master problem is formulated as:
The sub-problem is same as original problem except the objective is modified with reduced cost for the constrain (1.11) and (1.12) as:
Upon construction of the restricted master problem and sub-problem, iterate it till objective of sub-problem is greater than or equal to zero. Check for the solution to the problem and if it is not integer, than we would perform column generation at each node with branch and bound technique. Here, we would consider the first solution of column generation with iterations till the sub-problem objective becomes greater than or equal to zero. The data consists of four headers in .csv file with headers: fromnode, tonode, Cost, Time. Minimum path time threshold is 14.
from pulp import*
import pandas as pd
arcdf = pd.DataFrame.from_csv('.....SPTRESData.csv', index_col=['fromnode', 'tonode'])
class MasterProblem:
def __init__(self,maxresrtime,nodes,arcdf,arcs,arccost,arctime,initialpaths,problemname):
self.maxresrtime = maxresrtime
self.nodes = nodes
self.arcdf = arcdf
self.arcs = arcs
self.arccost = arccost
self.arctime = arctime
self.initialpaths = initialpaths
self.prob = LpProblem(problemname,LpMinimize)
self.obj = LpConstraintVar("obj")
self.prob.setObjective(self.obj)
self.PathVars = []
self.FirstConstr = LpConstraintVar("TimeResrConstr",LpConstraintLE,self.maxresrtime)
self.prob += self.FirstConstr
self.SecondConstr = LpConstraintVar("LambdaConstr",LpConstraintEQ,1.0)
self.prob += self.SecondConstr
artfvar = LpVariable("ArtVar",0,None,LpContinuous,
lpSum(self.obj * 1000 + self.FirstConstr + self.SecondConstr))
self.PathVars.append(artfvar)
pathtime = 0
pathcost = 0
for i,x in enumerate(self.initialpaths):
if x>0:
pathtime += (self.arctime[i])
pathcost += (self.arccost[i])
var = LpVariable("Path"+str(len(self.initialpaths)),0,None,LpContinuous,
lpSum(self.obj * pathcost + pathtime * self.FirstConstr + self.SecondConstr))
self.PathVars.append(var)
def solve(self):
self.prob.writeLP("MasterProb.lp")
self.prob.solve()
return [self.prob.constraints[i].pi for i in self.prob.constraints]
def addPath(self,path):
self.initialpaths.append(path)
pathtime = 0
pathcost = 0
for j,y in enumerate(path):
if y>0:
pathtime += (self.arctime[j])
pathcost += (self.arccost[j])
var = LpVariable("Path"+str(len(self.initialpaths)),0,None,LpContinuous,
lpSum(self.obj * pathcost + pathtime * self.FirstConstr + self.SecondConstr))
self.PathVars.append(var)
def startSubProblem(self,duals):
newSubProb = SubProblem(duals,self.nodes,self.arcdf,self.arcs,self.arccost,self.arctime)
path = newSubProb.returnPath()
return path
def setRelaxed(self,relaxed):
if relaxed==False:
for var in self.prob.variables():
var.cat = LpBinary
def getObjective(self):
return value(self.prob.objective)
def getUsedPaths(self):
usedPathList=[]
for i,x in enumerate(self.PathVars):
if value(x)>0:
usedPathList.append((value(x),self.initialpaths[i]))
return usedPathList
class SubProblem:
def __init__(self,duals,nodes,arcdf,arcs,arccost,arctime):
f = -duals[0]
s = -duals[1]
self.subprob = LpProblem("Sub Solver",LpMinimize)
self.varList = LpVariable.dicts("Arc_variable", ((i,j) for i,j in arcs),cat='Binary')
self.subprob += lpSum([self.varList[i,j] * arcdf.loc[(i,j),'cost'] for i,j in arcdf.index] +
[self.varList[i,j] * f * arcdf.loc[(i,j),'time'] for i,j in arcdf.index]) + s
self.subprob += lpSum([self.varList[i,j] for i,j in arcs if i == 1]) == 1
self.subprob += lpSum([self.varList[i,j] for i,j in arcs if j == 6]) == 1
for n in nodes:
if n != 1:
if n != 6:
self.subprob += (lpSum([self.varList[i,j] for i,j in arcs if i == n]) == lpSum([self.varList[i,j] for i,j in arcs if j == n]))
self.subprob.writeLP('subprob.lp')
self.subprob.solve()
def returnPath(self):
path=False
if value(self.subprob.objective) < 0:
path=[]
for v in self.subprob.variables():
path.append(v.varValue)
return path
nodes = [1,2,3,4,5,6]
arcs = [[1,2],[1,3],[2,4],[2,5],[3,2],[3,4],[3,5],[4,5],[4,6],[5,6]]
arccost = [1,10,1,2,1,5,12,10,1,2]
arctime = [10,3,1,3,2,7,3,1,7,2]
paths = [1,0,1,0,0,0,0,0,1,0]
print ("\n\nTrying to solve problem")
CGprob=MasterProblem(14,nodes,arcdf,arcs,arccost,arctime,paths,'Shortest Path Problem with time constraint')
relaxed=True
while relaxed==True: # once no more new columns can be generated set relaxed to False
duals=CGprob.solve()
newPath=CGprob.startSubProblem(duals)
print ('New path: %s' % newPath)
if newPath:
CGprob.addPath(newPath)
else:
CGprob.setRelaxed(False)
CGprob.solve()
relaxed=False
print ("\n\nSolution: %s Optimal path cost is" % CGprob.getObjective())
t=CGprob.getUsedPaths()
for i,x in enumerate(t):
print ("Path %s: selected %s times %s" % (i,x[0],x[1]))
No comments:
Post a Comment