PySCIPOpt  5.1.1
Python Interface for the SCIP Optimization Suite
lotsizing_lazy.py
Go to the documentation of this file.
1 
3 """
4 Approaches:
5  - sils: solve the problem using the standard formulation
6  - sils_cut: solve the problem using cutting planes
7 
8 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
9 """
10 from pyscipopt import Model, Conshdlr, quicksum, multidict, SCIP_RESULT, SCIP_PRESOLTIMING, SCIP_PROPTIMING
11 
12 
13 class Conshdlr_sils(Conshdlr):
14 
15  def addcut(self, checkonly, sol):
16  D, Ts = self.data
17  y, x, I = self.model.data
18  cutsadded = False
19 
20  for ell in Ts:
21  lhs = 0
22  S, L = [], []
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:
27  S.append(t)
28  lhs += D[t, ell] * yt
29  else:
30  L.append(t)
31  lhs += xt
32  if lhs < D[1, ell]:
33  if checkonly:
34  return True
35  else:
36  # add cutting plane constraint
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)
40  cutsadded = True
41  return cutsadded
42 
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}
46  else:
47  return {"result": SCIP_RESULT.FEASIBLE}
48 
49  def consenfolp(self, constraints, nusefulconss, solinfeasible):
50  if self.addcut(checkonly=False):
51  return {"result": SCIP_RESULT.CONSADDED}
52  else:
53  return {"result": SCIP_RESULT.FEASIBLE}
54 
55  def conslock(self, constraint, locktype, nlockspos, nlocksneg):
56  pass
57 
58 
59 def sils(T, f, c, d, h):
60  """sils -- LP lotsizing for the single item lot sizing problem
61  Parameters:
62  - T: number of periods
63  - P: set of products
64  - f[t]: set-up costs (on period t)
65  - c[t]: variable costs
66  - d[t]: demand values
67  - h[t]: holding costs
68  Returns a model, ready to be solved.
69  """
70  model = Model("single item lotsizing")
71  Ts = range(1, T + 1)
72  M = sum(d[t] for t in Ts)
73  y, x, I = {}, {}, {}
74  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)
78  I[0] = 0
79 
80  for t in Ts:
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)
83 
84  model.setObjective( \
85  quicksum(f[t] * y[t] + c[t] * x[t] + h[t] * I[t] for t in Ts), \
86  "minimize")
87 
88  model.data = y, x, I
89  return model
90 
91 
92 def sils_cut(T, f, c, d, h, conshdlr):
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
96  Parameters:
97  - T: number of periods
98  - P: set of products
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.
104  """
105  Ts = range(1, T + 1)
106 
107  model = sils(T, f, c, d, h)
108  y, x, I = model.data
109 
110  # relax integer variables
111  for t in Ts:
112  model.chgVarType(y[t], "C")
113  model.addVar(vtype="B", name="fake") # for making the problem MIP
114 
115  # compute D[i,j] = sum_{t=i}^j d[t]
116  D = {}
117  for t in Ts:
118  s = 0
119  for j in range(t, T + 1):
120  s += d[j]
121  D[t, j] = s
122 
123  # include the lot sizing constraint handler
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
129 
130  model.data = y, x, I
131  return model
132 
133 
135  """mk_example: book example for the single item lot sizing"""
136  T = 5
137  _, f, c, d, h = multidict({
138  1: [3, 1, 5, 1],
139  2: [3, 1, 7, 1],
140  3: [3, 3, 3, 1],
141  4: [3, 3, 6, 1],
142  5: [3, 3, 4, 1],
143  })
144 
145  return T, f, c, d, h
146 
147 
148 if __name__ == "__main__":
149  T, f, c, d, h = mk_example()
150 
151  model = sils(T, f, c, d, h)
152  y, x, I = model.data
153  model.optimize()
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])))
159 
160  conshdlr = Conshdlr_sils()
161  model = sils_cut(T, f, c, d, h, conshdlr)
162  model.setBoolParam("misc/allowstrongdualreds", 0)
163  model.optimize()
164  y, x, I = model.data
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])))
pyscipopt.expr.quicksum
def quicksum(termlist)
Definition: expr.pxi:357
lotsizing_lazy.sils
def sils(T, f, c, d, h)
Definition: lotsizing_lazy.py:59
pyscipopt.conshdlr.conslock
def conslock(self, constraint, locktype, nlockspos, nlocksneg)
Definition: conshdlr.pxi:90
pyscipopt.conshdlr.conscheck
def conscheck(self, constraints, solution, checkintegrality, checklprows, printreason, completely)
Definition: conshdlr.pxi:71
pyscipopt.conshdlr.consenfolp
def consenfolp(self, constraints, nusefulconss, solinfeasible)
Definition: conshdlr.pxi:56
lotsizing_lazy.mk_example
def mk_example()
Definition: lotsizing_lazy.py:134
pyscipopt.Multidict.multidict
def multidict(D)
Definition: Multidict.py:3
lotsizing_lazy.sils_cut
def sils_cut(T, f, c, d, h, conshdlr)
Definition: lotsizing_lazy.py:92