5 - sils: solve the problem using the standard formulation
6 - sils_cut: solve the problem using cutting planes
8 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
10 from pyscipopt
import Model, Conshdlr, quicksum, multidict, SCIP_RESULT, SCIP_PRESOLTIMING, SCIP_PROPTIMING
12 class Conshdlr_sils(Conshdlr):
14 def addcut(self, checkonly, sol):
16 y,x,I = self.model.data
22 for t
in range(1,ell+1):
23 yt = self.model.getSolVal(sol, y[t])
24 xt = self.model.getSolVal(sol, x[t])
36 self.model.addCons(
quicksum([x[t]
for t
in L]) + \
37 quicksum(D[t, ell] * y[t]
for t
in S)
38 >= D[1, ell], removable =
True)
42 def conscheck(self, constraints, solution, checkintegrality, checklprows, printreason, completely):
43 if not self.addcut(checkonly =
True, sol = solution):
44 return {
"result": SCIP_RESULT.INFEASIBLE}
46 return {
"result": SCIP_RESULT.FEASIBLE}
48 def consenfolp(self, constraints, nusefulconss, solinfeasible):
49 if self.addcut(checkonly =
False):
50 return {
"result": SCIP_RESULT.CONSADDED}
52 return {
"result": SCIP_RESULT.FEASIBLE}
54 def conslock(self, constraint, locktype, nlockspos, nlocksneg):
58 """sils -- LP lotsizing for the single item lot sizing problem
60 - T: number of periods
62 - f[t]: set-up costs (on period t)
63 - c[t]: variable costs
66 Returns a model, ready to be solved.
68 model = Model(
"single item lotsizing")
70 M = sum(d[t]
for t
in Ts)
73 y[t] = model.addVar(vtype=
"I", ub=1, name=
"y(%s)"%t)
74 x[t] = model.addVar(vtype=
"C", ub=M, name=
"x(%s)"%t)
75 I[t] = model.addVar(vtype=
"C", name=
"I(%s)"%t)
79 model.addCons(x[t] <= M*y[t],
"ConstrUB(%s)"%t)
80 model.addCons(I[t-1] + x[t] == I[t] + d[t],
"FlowCons(%s)"%t)
83 quicksum(f[t]*y[t] + c[t]*x[t] + h[t]*I[t]
for t
in Ts),\
90 """solve_sils -- solve the lot sizing problem with cutting planes
91 - start with a relaxed model
92 - used lazy constraints to elimitate fractional setup variables with cutting planes
94 - T: number of periods
96 - f[t]: set-up costs (on period t)
97 - c[t]: variable costs
100 Returns the final model solved, with all necessary cuts added.
104 model =
sils(T,f,c,d,h)
109 model.chgVarType(y[t],
"C")
110 model.addVar(vtype=
"B", name=
"fake")
116 for j
in range(t,T+1):
121 model.includeConshdlr(conshdlr,
"SILS",
"Constraint handler for single item lot sizing",
122 sepapriority = 0, enfopriority = -1, chckpriority = -1, sepafreq = -1, propfreq = -1,
123 eagerfreq = -1, maxprerounds = 0, delaysepa =
False, delayprop =
False, needscons =
False,
124 presoltiming = SCIP_PRESOLTIMING.FAST, proptiming = SCIP_PROPTIMING.BEFORELP)
131 """mk_example: book example for the single item lot sizing"""
143 if __name__ ==
"__main__":
149 print(
"\nOptimal value [standard]:",model.getObjVal())
150 print(
"%8s%8s%8s%8s%8s%8s%12s%12s" % (
"t",
"fix",
"var",
"h",
"dem",
"y",
"x",
"I"))
151 for t
in range(1,T+1):
152 print(
"%8d%8d%8d%8d%8d%8.1f%12.1f%12.1f" % (t,f[t],c[t],h[t],d[t],model.getVal(y[t]),model.getVal(x[t]),model.getVal(I[t])))
154 conshdlr = Conshdlr_sils()
155 model =
sils_cut(T,f,c,d,h, conshdlr)
156 model.setBoolParam(
"misc/allowstrongdualreds", 0)
159 print(
"\nOptimal value [cutting planes]:",model.getObjVal())
160 print(
"%8s%8s%8s%8s%8s%8s%12s%12s" % (
"t",
"fix",
"var",
"h",
"dem",
"y",
"x",
"I"))
161 for t
in range(1,T+1):
162 print(
"%8d%8d%8d%8d%8d%8.1f%12.1f%12.1f" % (t,f[t],c[t],h[t],d[t],model.getVal(y[t]),model.getVal(x[t]),model.getVal(I[t])))