1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
"""
Columnwise Column Generation Functions
Authors: Antony Phillips, Dr Stuart Mitchell 2008
"""
# Import PuLP modeler functions
from pulp import *
class Pattern:
"""
Information on a specific pattern in the SpongeRoll Problem
"""
cost = 1
trimValue = 0.04
totalRollLength = 20
lenOpts = ["5", "7", "9"]
numPatterns = 0
def __init__(self, name, lengths = None):
self.name = name
self.lengthsdict = dict(zip(self.lenOpts,lengths))
Pattern.numPatterns += 1
def __str__(self):
return self.name
def trim(self):
return Pattern.totalRollLength - sum([int(i)*int(self.lengthsdict[i]) for i in self.lengthsdict])
def createMaster():
rollData = {#Length Demand SalePrice
"5": [150, 0.25],
"7": [200, 0.33],
"9": [300, 0.40]}
(rollDemand,surplusPrice) = splitDict(rollData)
# The variable 'prob' is created
prob = LpProblem("MasterSpongeRollProblem",LpMinimize)
# The variable 'obj' is created and set as the LP's objective function
obj = LpConstraintVar("Obj")
prob.setObjective(obj)
# The constraints are initialised and added to prob
constraints = {}
for l in Pattern.lenOpts:
constraints[l]= LpConstraintVar("Min" + str(l), LpConstraintGE, rollDemand[l])
prob += constraints[l]
# The surplus variables are created
surplusVars = []
for i in Pattern.lenOpts:
surplusVars += [LpVariable("Surplus "+ i,0,None,LpContinuous, -surplusPrice[i] * obj - constraints[i])]
return prob,obj,constraints
def addPatterns(obj,constraints,newPatterns):
# A list called Patterns is created to contain all the Pattern class
# objects created in this function call
Patterns = []
for i in newPatterns:
# The new patterns are checked to see that their length does not exceed
# the total roll length
lsum = 0
for j,k in zip(i,Pattern.lenOpts):
lsum += j * int(k)
if lsum > Pattern.totalRollLength:
raise "Length Options too large for Roll"
# The number of rolls of each length in each new pattern is printed
print "P"+str(Pattern.numPatterns),"=",i
# The patterns are instantiated as Pattern objects
Patterns += [Pattern("P" + str(Pattern.numPatterns),i)]
# The pattern variables are created
pattVars = []
for i in Patterns:
pattVars += [LpVariable("Pattern "+i.name,0,None,LpContinuous, (i.cost - Pattern.trimValue*i.trim()) * obj\
+ lpSum([constraints[l]*i.lengthsdict[l] for l in Pattern.lenOpts]))]
def masterSolve(prob,relax = True):
# Unrelaxes the Integer Constraint
if not relax:
for v in prob.variables():
v.cat = LpInteger
# The problem is solved and rounded
prob.solve(PULP_CBC_CMD())
prob.roundSolution()
if relax:
# A dictionary of dual variable values is returned
duals = {}
for i,name in zip(Pattern.lenOpts,["Min5","Min7","Min9"]):
duals[i] = prob.constraints[name].pi
return duals
else:
# A dictionary of variable values and the objective value are returned
varsdict = {}
for v in prob.variables():
varsdict[v.name] = v.varValue
return value(prob.objective), varsdict
def subSolve(duals):
# The variable 'prob' is created
prob = LpProblem("SubProb",LpMinimize)
# The problem variables are created
vars = LpVariable.dicts("Roll Length", Pattern.lenOpts, 0, None, LpInteger)
trim = LpVariable("Trim", 0 ,None,LpInteger)
# The objective function is entered: the reduced cost of a new pattern
prob += (Pattern.cost - Pattern.trimValue*trim) - lpSum([vars[i]*duals[i] for i in Pattern.lenOpts]), "Objective"
# The conservation of length constraint is entered
prob += lpSum([vars[i]*int(i) for i in Pattern.lenOpts]) + trim == Pattern.totalRollLength, "lengthEquate"
# The problem is solved
prob.solve()
# The variable values are rounded
prob.roundSolution()
newPatterns = []
# Check if there are more patterns which would reduce the master LP objective function further
if value(prob.objective) < -10**-5:
varsdict = {}
for v in prob.variables():
varsdict[v.name] = v.varValue
# Adds the new pattern to the newPatterns list
newPatterns += [[int(varsdict["Roll_Length_5"]),int(varsdict["Roll_Length_7"]),int(varsdict["Roll_Length_9"])]]
return newPatterns
|
