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
13 class Conshdlr_sils(Conshdlr):
15 def addcut(self, checkonly, sol):
17 y, x, I = self.model.data
23 for t
in range(1, ell + 1):
24 yt = self.model.getSolVal(sol, y[t])
25 xt = self.model.getSolVal(sol, x[t])
26 if D[t, ell] * yt < xt:
37 self.model.addCons(
quicksum([x[t]
for t
in L]) + \
38 quicksum(D[t, ell] * y[t]
for t
in S)
39 >= D[1, ell], removable=
True)
43 def conscheck(self, constraints, solution, checkintegrality, checklprows, printreason, completely):
44 if not self.addcut(checkonly=
True, sol=solution):
45 return {
"result": SCIP_RESULT.INFEASIBLE}
47 return {
"result": SCIP_RESULT.FEASIBLE}
49 def consenfolp(self, constraints, nusefulconss, solinfeasible):
50 if self.addcut(checkonly=
False):
51 return {
"result": SCIP_RESULT.CONSADDED}
53 return {
"result": SCIP_RESULT.FEASIBLE}
55 def conslock(self, constraint, locktype, nlockspos, nlocksneg):
60 """sils -- LP lotsizing for the single item lot sizing problem
62 - T: number of periods
64 - f[t]: set-up costs (on period t)
65 - c[t]: variable costs
68 Returns a model, ready to be solved.
70 model = Model(
"single item lotsizing")
72 M = sum(d[t]
for t
in Ts)
75 y[t] = model.addVar(vtype=
"I", ub=1, name=
"y(%s)" % t)
76 x[t] = model.addVar(vtype=
"C", ub=M, name=
"x(%s)" % t)
77 I[t] = model.addVar(vtype=
"C", name=
"I(%s)" % t)
81 model.addCons(x[t] <= M * y[t],
"ConstrUB(%s)" % t)
82 model.addCons(I[t - 1] + x[t] == I[t] + d[t],
"FlowCons(%s)" % t)
85 quicksum(f[t] * y[t] + c[t] * x[t] + h[t] * I[t]
for t
in Ts), \
93 """solve_sils -- solve the lot sizing problem with cutting planes
94 - start with a relaxed model
95 - used lazy constraints to elimitate fractional setup variables with cutting planes
97 - T: number of periods
99 - f[t]: set-up costs (on period t)
100 - c[t]: variable costs
101 - d[t]: demand values
102 - h[t]: holding costs
103 Returns the final model solved, with all necessary cuts added.
107 model =
sils(T, f, c, d, h)
112 model.chgVarType(y[t],
"C")
113 model.addVar(vtype=
"B", name=
"fake")
119 for j
in range(t, T + 1):
124 model.includeConshdlr(conshdlr,
"SILS",
"Constraint handler for single item lot sizing",
125 sepapriority=0, enfopriority=-1, chckpriority=-1, sepafreq=-1, propfreq=-1,
126 eagerfreq=-1, maxprerounds=0, delaysepa=
False, delayprop=
False, needscons=
False,
127 presoltiming=SCIP_PRESOLTIMING.FAST, proptiming=SCIP_PROPTIMING.BEFORELP)
128 conshdlr.data = D, Ts
135 """mk_example: book example for the single item lot sizing"""
148 if __name__ ==
"__main__":
154 print(
"\nOptimal value [standard]:", model.getObjVal())
155 print(
"%8s%8s%8s%8s%8s%8s%12s%12s" % (
"t",
"fix",
"var",
"h",
"dem",
"y",
"x",
"I"))
156 for t
in range(1, T + 1):
157 print(
"%8d%8d%8d%8d%8d%8.1f%12.1f%12.1f" % (
158 t, f[t], c[t], h[t], d[t], model.getVal(y[t]), model.getVal(x[t]), model.getVal(I[t])))
160 conshdlr = Conshdlr_sils()
161 model =
sils_cut(T, f, c, d, h, conshdlr)
162 model.setBoolParam(
"misc/allowstrongdualreds", 0)
165 print(
"\nOptimal value [cutting planes]:", model.getObjVal())
166 print(
"%8s%8s%8s%8s%8s%8s%12s%12s" % (
"t",
"fix",
"var",
"h",
"dem",
"y",
"x",
"I"))
167 for t
in range(1, T + 1):
168 print(
"%8d%8d%8d%8d%8d%8.1f%12.1f%12.1f" % (
169 t, f[t], c[t], h[t], d[t], model.getVal(y[t]), model.getVal(x[t]), model.getVal(I[t])))