5 - mult_selection: multiple selection model 6 - convex_comb_sos: model with SOS2 constraints 7 - convex_comb_dis: convex combination with binary variables (disaggregated model) 8 - convex_comb_dis_log: convex combination with a logarithmic number of binary variables 9 - convex_comb_agg: convex combination with binary variables (aggregated model) 10 - convex_comb_agg_log: convex combination with a logarithmic number of binary variables 12 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012 16 from pyscipopt
import Model, quicksum, multidict
18 def mult_selection(model,a,b):
19 """mult_selection -- add piecewise relation with multiple selection formulation 21 - model: a model where to include the piecewise linear relation 22 - a[k]: x-coordinate of the k-th point in the piecewise linear relation 23 - b[k]: y-coordinate of the k-th point in the piecewise linear relation 24 Returns the model with the piecewise linear relation on added variables X, Y, and z. 30 w[k] = model.addVar(lb=-model.infinity())
31 z[k] = model.addVar(vtype=
"B")
32 X = model.addVar(lb=a[0], ub=a[K], vtype=
"C")
33 Y = model.addVar(lb=-model.infinity())
36 model.addCons(w[k] >= a[k]*z[k])
37 model.addCons(w[k] <= a[k+1]*z[k])
39 model.addCons(quicksum(z[k]
for k
in range(K)) == 1)
40 model.addCons(X == quicksum(w[k]
for k
in range(K)))
42 c = [float(b[k+1]-b[k])/(a[k+1]-a[k])
for k
in range(K)]
43 d = [b[k]-c[k]*a[k]
for k
in range(K)]
44 model.addCons(Y == quicksum(d[k]*z[k] + c[k]*w[k]
for k
in range(K)))
49 def convex_comb_sos(model,a,b):
50 """convex_comb_sos -- add piecewise relation with gurobi's SOS constraints 52 - model: a model where to include the piecewise linear relation 53 - a[k]: x-coordinate of the k-th point in the piecewise linear relation 54 - b[k]: y-coordinate of the k-th point in the piecewise linear relation 55 Returns the model with the piecewise linear relation on added variables X, Y, and z. 60 z[k] = model.addVar(lb=0, ub=1, vtype=
"C")
61 X = model.addVar(lb=a[0], ub=a[K], vtype=
"C")
62 Y = model.addVar(lb=-model.infinity(), vtype=
"C")
64 model.addCons(X == quicksum(a[k]*z[k]
for k
in range(K+1)))
65 model.addCons(Y == quicksum(b[k]*z[k]
for k
in range(K+1)))
67 model.addCons(quicksum(z[k]
for k
in range(K+1)) == 1)
68 model.addConsSOS2([z[k]
for k
in range(K+1)])
73 def convex_comb_dis(model,a,b):
74 """convex_comb_dis -- add piecewise relation with convex combination formulation 76 - model: a model where to include the piecewise linear relation 77 - a[k]: x-coordinate of the k-th point in the piecewise linear relation 78 - b[k]: y-coordinate of the k-th point in the piecewise linear relation 79 Returns the model with the piecewise linear relation on added variables X, Y, and z. 84 wL[k] = model.addVar(lb=0, ub=1, vtype=
"C")
85 wR[k] = model.addVar(lb=0, ub=1, vtype=
"C")
86 z[k] = model.addVar(vtype=
"B")
87 X = model.addVar(lb=a[0], ub=a[K], vtype=
"C")
88 Y = model.addVar(lb=-model.infinity(), vtype=
"C")
90 model.addCons(X == quicksum(a[k]*wL[k] + a[k+1]*wR[k]
for k
in range(K)))
91 model.addCons(Y == quicksum(b[k]*wL[k] + b[k+1]*wR[k]
for k
in range(K)))
93 model.addCons(wL[k] + wR[k] == z[k])
95 model.addCons(quicksum(z[k]
for k
in range(K)) == 1)
101 """returns i^int(i/2)""" 105 def convex_comb_dis_log(model,a,b):
106 """convex_comb_dis_log -- add piecewise relation with a logarithmic number of binary variables 107 using the convex combination formulation. 109 - model: a model where to include the piecewise linear relation 110 - a[k]: x-coordinate of the k-th point in the piecewise linear relation 111 - b[k]: y-coordinate of the k-th point in the piecewise linear relation 112 Returns the model with the piecewise linear relation on added variables X, Y, and z. 115 G = int(math.ceil((math.log(K)/math.log(2))))
120 wL[k] = model.addVar(lb=0, ub=1, vtype=
"C")
121 wR[k] = model.addVar(lb=0, ub=1, vtype=
"C")
122 X = model.addVar(lb=a[0], ub=a[K], vtype=
"C")
123 Y = model.addVar(lb=-model.infinity(), vtype=
"C")
127 g[j] = model.addVar(vtype=
"B")
129 model.addCons(X == quicksum(a[k]*wL[k] + a[k+1]*wR[k]
for k
in range(K)))
130 model.addCons(Y == quicksum(b[k]*wL[k] + b[k+1]*wR[k]
for k
in range(K)))
131 model.addCons(quicksum(wL[k] + wR[k]
for k
in range(K)) == 1)
142 model.addCons(quicksum(wL[k] + wR[k]
for k
in ones) <= g[j])
143 model.addCons(quicksum(wL[k] + wR[k]
for k
in zeros) <= 1-g[j])
149 def convex_comb_agg(model,a,b):
150 """convex_comb_agg -- add piecewise relation convex combination formulation -- non-disaggregated. 152 - model: a model where to include the piecewise linear relation 153 - a[k]: x-coordinate of the k-th point in the piecewise linear relation 154 - b[k]: y-coordinate of the k-th point in the piecewise linear relation 155 Returns the model with the piecewise linear relation on added variables X, Y, and z. 160 w[k] = model.addVar(lb=0, ub=1, vtype=
"C")
162 z[k] = model.addVar(vtype=
"B")
163 X = model.addVar(lb=a[0], ub=a[K], vtype=
"C")
164 Y = model.addVar(lb=-model.infinity(), vtype=
"C")
166 model.addCons(X == quicksum(a[k]*w[k]
for k
in range(K+1)))
167 model.addCons(Y == quicksum(b[k]*w[k]
for k
in range(K+1)))
168 model.addCons(w[0] <= z[0])
169 model.addCons(w[K] <= z[K-1])
171 model.addCons(w[k] <= z[k-1]+z[k])
172 model.addCons(quicksum(w[k]
for k
in range(K+1)) == 1)
173 model.addCons(quicksum(z[k]
for k
in range(K)) == 1)
178 def convex_comb_agg_log(model,a,b):
179 """convex_comb_agg_log -- add piecewise relation with a logarithmic number of binary variables 180 using the convex combination formulation -- non-disaggregated. 182 - model: a model where to include the piecewise linear relation 183 - a[k]: x-coordinate of the k-th point in the piecewise linear relation 184 - b[k]: y-coordinate of the k-th point in the piecewise linear relation 185 Returns the model with the piecewise linear relation on added variables X, Y, and z. 188 G = int(math.ceil((math.log(K)/math.log(2))))
191 w[k] = model.addVar(lb=0, ub=1, vtype=
"C")
193 g[j] = model.addVar(vtype=
"B")
194 X = model.addVar(lb=a[0], ub=a[K], vtype=
"C")
195 Y = model.addVar(lb=-model.infinity(), vtype=
"C")
197 model.addCons(X == quicksum(a[k]*w[k]
for k
in range(K+1)))
198 model.addCons(Y == quicksum(b[k]*w[k]
for k
in range(K+1)))
199 model.addCons(quicksum(w[k]
for k
in range(K+1)) == 1)
205 for k
in range(1,K+1):
207 if (1 & gray(k)>>j) == 1
and (1 & gray(k-1)>>j) == 1:
209 if (1 & gray(k)>>j) == 0
and (1 & gray(k-1)>>j) == 0:
214 model.addCons(quicksum(w[k]
for k
in ones) <= g[j])
215 model.addCons(quicksum(w[k]
for k
in zeros) <= 1-g[j])
220 if __name__ ==
"__main__":
223 a = [ -10, 10, 15, 25, 30, 35, 40, 45, 50, 55, 60, 70]
224 b = [ -20,-20, 15, -21, 0, 50, 18, 0, 15, 24, 10, 15]
226 print(
"\n\n\npiecewise: multiple selection")
227 model = Model(
"multiple selection")
228 X,Y,z = mult_selection(model,a,b)
230 u = model.addVar(vtype=
"C", name=
"u") 232 A = model.addCons(3*X + 4*Y <= 250, "A")
233 B = model.addCons(7*X - 2*Y + 3*u == 170,
"B")
234 model.setObjective(2*X + 15*Y + 5*u,
"maximize")
236 print(
"X:",model.getVal(X))
237 print(
"Y:",model.getVal(Y))
238 print(
"u:",model.getVal(u))
240 print(
"\n\n\npiecewise: disaggregated convex combination")
241 model = Model(
"disaggregated convex combination")
242 X,Y,z = convex_comb_dis(model,a,b)
243 u = model.addVar(vtype=
"C", name=
"u") 245 A = model.addCons(3*X + 4*Y <= 250, "A")
246 B = model.addCons(7*X - 2*Y + 3*u == 170,
"B")
247 model.setObjective(2*X + 15*Y + 5*u,
"maximize")
249 print(
"X:",model.getVal(X))
250 print(
"Y:",model.getVal(Y))
251 print(
"u:",model.getVal(u))
253 print(
"\n\n\npiecewise: disaggregated convex combination, logarithmic number of variables")
254 model = Model(
"disaggregated convex combination (log)")
255 X,Y,z = convex_comb_dis(model,a,b)
256 u = model.addVar(vtype=
"C", name=
"u") 258 A = model.addCons(3*X + 4*Y <= 250, "A")
259 B = model.addCons(7*X - 2*Y + 3*u == 170,
"B")
260 model.setObjective(2*X + 15*Y + 5*u,
"maximize")
262 print(
"X:",model.getVal(X))
263 print(
"Y:",model.getVal(Y))
264 print(
"u:",model.getVal(u))
266 print(
"\n\n\npiecewise: SOS2 constraint")
267 model = Model(
"SOS2")
268 X,Y,w = convex_comb_sos(model,a,b)
269 u = model.addVar(vtype=
"C", name=
"u") 271 A = model.addCons(3*X + 4*Y <= 250, "A")
272 B = model.addCons(7*X - 2*Y + 3*u == 170,
"B")
273 model.setObjective(2*X + 15*Y + 5*u,
"maximize")
275 print(
"X:",model.getVal(X))
276 print(
"Y:",model.getVal(Y))
277 print(
"u:",model.getVal(u))
279 print(
"\n\n\npiecewise: aggregated convex combination")
280 model = Model(
"aggregated convex combination")
281 X,Y,z = convex_comb_agg(model,a,b)
282 u = model.addVar(vtype=
"C", name=
"u") 284 A = model.addCons(3*X + 4*Y <= 250, "A")
285 B = model.addCons(7*X - 2*Y + 3*u == 170,
"B")
286 model.setObjective(2*X + 15*Y + 5*u,
"maximize")
288 print(
"X:",model.getVal(X))
289 print(
"Y:",model.getVal(Y))
290 print(
"u:",model.getVal(u))
292 print(
"\n\n\npiecewise: aggregated convex combination, logarithmic number of variables")
293 model = Model(
"aggregated convex combination (log)")
294 X,Y,w = convex_comb_agg_log(model,a,b)
295 u = model.addVar(vtype=
"C", name=
"u") 297 A = model.addCons(3*X + 4*Y <= 250, "A")
298 B = model.addCons(7*X - 2*Y + 3*u == 170,
"B")
299 model.setObjective(2*X + 15*Y + 5*u,
"maximize")
301 print(
"X:",model.getVal(X))
302 print(
"Y:",model.getVal(Y))
303 print(
"u:",model.getVal(u))