1
2
3
4
5
8 """
9 SCOP model class.
10 - Attbibutes:
11 - constraints: Set of constraint objects in the model.
12 - variables: Set of variable objects in the model.
13 - Params: Object including all the parameters of the model.
14 - varDict: Dictionary that maps variable names to their domains.
15 """
16 self.constraints = []
17 self.variables = []
18 self.Params=Parameters()
19 self.varDict={}
20
22 """
23 Returns the information of the problem.
24 Constraints are expanded and are shown in a readable format
25 """
26 ret="number of variables = "+str(len(self.variables))+" \n"
27 ret+="number of constraints= "+str(len(self.constraints))+"\n"
28 for v in self.variables:
29 ret+=str(v)+"\n"
30
31 for c in self.constraints:
32 ret+=str(c)
33 return ret
34
36 """
37 Prepares a string representing the current model in the scop input format.
38 """
39 f = ""
40
41 for var in self.variables:
42 domainList = ",".join([str(i) for i in var.domain])
43 f += "variable %s in { %s } \n" % (var.name, domainList)
44
45 f += "target = %s \n" % str(self.target)
46
47 for con in self.constraints:
48 f += str(con)
49 return f
50
52 """
53 Adds a variable to the model.
54 - Arguments:
55 - name: Name for new variable. A string object.
56 - domain: Domain (list of values) of new variable. Each value must be a string or numeric object.
57
58 - Return value: New variable object.
59
60 - Example usage:
61
62 >>> x = model.addVarriable("var")
63
64 >>> x = model.addVariable(name="var",domain=[1,2,3])
65
66 >>> x = model.addVariable("var",["A","B","C"])
67 """
68 var =Variable(name,domain)
69 self.variables.append(var)
70
71 self.varDict[var.name]=var.domain
72 return var
73
75 """
76 Adds variables and their (identical) domain.
77
78 - Arguments:
79 - names: list of new variables. A list of string objects.
80 - domain: Domain (list of values) of new variables. Each value must be a string or numeric object.
81
82 - Return value: List of new variable objects.
83
84 - Example usage:
85
86 >>> varlist=["var1","var2","var3"]
87
88 >>> x = model.addVariables(varlist)
89
90 >>> x = model.addVariables(names=varlist,domain=[1,2,3]
91
92 >>> x = model.addVariables(varlist,["A","B","C"]
93 """
94 if type(names)!=type([]):
95 print "The first argument (names) must be a list."
96 raise NameError
97 varlist=[]
98 for var in names:
99 varlist.append(self.addVariable(var,domain))
100 return varlist
101
103 """
104 Adds a constraint to the model.
105
106 - Argument:
107 - con: A constraint object (Linear, Quadratic or AllDiff).
108
109 - Example usage:
110
111 >>> model.addConstraint(L)
112 """
113 if not isinstance(con,Constraint):
114 print "error: %r should be a subclass of Constraint" % con
115 raise NameError
116
117
118 try:
119 if con.feasible(self.varDict):
120 self.constraints.append(con)
121 except NameError:
122 print "Execute update before adding constraints"
123 raise NameError
124
125
126
127
128
130 """
131 Optimizes the model using scop.exe in the same directory.
132
133 - Example usage:
134
135 >>> model.optimize()
136 """
137 time=self.Params.TimeLimit
138 seed=self.Params.RandomSeed
139 LOG=self.Params.OutputFlag
140 self.target=self.Params.Target
141
142 f = self.update()
143 if LOG:
144 print "scop input: \n"+f + "\n"
145 print "solving using parameters: \n "
146 print " TimeLimit =%s second"%time
147 print " RandomSeed= %s"%seed
148 print " OutputFlag= %s"%LOG +"\n"
149 import subprocess
150 cmd = SCOP + " -time "+str(time)+" -seed "+str(seed)
151 try:
152 pipe = subprocess.Popen(cmd.split(), stdout=subprocess.PIPE, stdin=subprocess.PIPE)
153 except OSError:
154 print "error: could not execute command '%s'" % cmd
155 print "please check that the solver is in the path"
156 exit(0)
157 out, err = pipe.communicate(f)
158 if LOG:
159 print "scop output: \n"+f
160 print out, '\n'
161
162
163 s0 = "[best solution]"
164 s1 = "penalty"
165 s2 = "[Violated constraints]"
166 i0 = out.find(s0) + len(s0)
167 i1 = out.find(s1, i0)
168 i2 = out.find(s2, i1) + len(s2)
169
170 data = out[i0:i1].strip()
171 sol = {}
172
173 if data != "":
174 for s in data.split("\n"):
175 name, value = s.split(":")
176 if type(value)==type(1):
177 sol[name]=int(value)
178 else:
179 sol[name] = value
180 data = out[i2:].strip()
181 violated = {}
182 if data != "":
183 for s in data.split("\n"):
184 name, value = s.split(":")
185 violated[name] = value if value != int(value) else int(value)
186
187
188 return sol,violated
189
191 """
192 SCOP variable class. Variables are associated with a particular model.
193
194 You can create a variable object by adding a variable to a model (using Model.addVariable or Model.addVariables) instead of by using a Variable constructor.
195 """
197 self.name=str(name)
198 self.domain=list(domain)
199
201 return "variable "+str(self.name)+":"+str(self.domain)
202
204 """
205 Constraint base class.
206 """
208 """
209 Sets weight of constraint.
210
211 - Argument:
212 - weight: Weight of the constraint representing importance of constraint.. Positive integer or string "inf."
213
214 - Example usage:
215
216 >>> L.setWeight("inf")
217
218 """
219 self.weight = str(weight)
220
221
222
223
225 - def __init__(self,name,weight=1,rhs=0,direction="<="):
226 """
227 Linear constraint constructor.
228
229 - Arguments:
230 - name: Name of linear constraint.
231 - weight (optional): Positive integer representing importance of constraint.
232 - rhs: Right-hand-side constant of linear constraint.
233 - direction: Rirection (or sense) of linear constraint; "<=" (default) or ">=" or "=."
234
235 - Attributes:
236 - name: Name of linear constraint.
237 - weight (optional): Positive integer representing importance of constraint.
238 - rhs: Right-hand-side constant of linear constraint.
239 - direction: Direction (or sense) of linear constraint; "<=" (default) or ">=" or "=".
240 - terms: List of terms in left-hand-side of constraint. Each term is a tuple of coeffcient,variable and its value.
241 """
242 if name==None or name=="":
243 print "error: please specify the name when creating a constraint"
244 raise NameError
245
246 self.name = name
247 self.weight = str(weight)
248 self.rhs = rhs
249 self.direction = direction
250 self.terms = []
251
253 """
254 Returns the information of the linear constraint.
255 The constraint is expanded and is shown in a readable format.
256 """
257 f = self.name+": weight= "+self.weight+" type=linear "
258 for (coeff,var,value) in self.terms:
259 f += str(coeff)+"("+var.name +","+ str(value)+") "
260 f += self.direction+str(self.rhs) +"\n"
261 return f
262
263 - def addTerms(self,coeffs=[],vars=[],values=[]):
264 """
265 Adds new terms into left-hand-side of linear constraint.
266
267 - Arguments:
268 - coeffs: Coefficients for new terms; either a list of coefficients or a single coefficient. The three arguments must have the same size.
269 - vars: Variables for new terms; either a list of variables or a single variable. The three arguments must have the same size.
270 - values: Values for new terms; either a list of values or a single value. The three arguments must have the same size.
271
272 - Example usage:
273
274 >>> L.addTerms(1.0, y, "A")
275
276 >>> L.addTerms([2, 3, 1], [y, y, z], ["C", "D", "C"])
277
278 which adds the left-hand-side 2 X[y,"C"]+3 X[y,"D"]+1 X[z,"C"].
279 """
280 if type(coeffs) !=type([]):
281
282 if type(coeffs)==type(1):
283 self.terms.append( (coeffs,vars,values))
284 elif type(coeffs)!=type([]) or type(vars)!=type([]) or type(values)!=type([]):
285 print "coeffs, vars, values must be lists"
286 raise TypeError
287 elif len(coeffs)!=len(vars) or len(coeffs)!=len(values):
288 print "length of coeffs, vars, values must be identical"
289 raise TypeError
290 elif len(coeffs) !=len(vars) or len(coeffs) !=len(values):
291 print "error: length of coeffs, vars, and values must be identical"
292 raise TypeError
293 else:
294 for i in range(len(coeffs)):
295 self.terms.append( (coeffs[i],vars[i],values[i]))
296
298 """
299 Sets the right-hand-side of linear constraint.
300
301 - Argument:
302 - rhs: Right-hand-side of linear constraint.
303
304 - Example usage:
305
306 >>> L.setRhs(10)
307
308 """
309 self.rhs = rhs
310
312 """
313 Sets the direction (or sense) of linear constraint.
314
315 - Argument:
316 - direction: direction (or sense) of linear constraint; "<=" (default) or ">=" or "=."
317
318 - Example usage:
319
320 >>> L.setDirection("=")
321
322 """
323 if direction in ["<=",">=","="]:
324 self.direction = direction
325 else:
326 print "direction setting error; direction should be one of '<=', '>=', or '='"
327 raise NameError
328
330 """
331 Return True if the constraint is defined correctly.
332 """
333 for (coeff,var,value) in self.terms:
334 if var.name not in allvars:
335 print "no variable in the problem instance named %r" % var.name
336 raise NameError
337 if value not in allvars[var.name]:
338 print "no value %r for the variable named %r" % (value, var.name)
339 raise NameError
340 return True
341
342
344 - def __init__(self,name=None,weight=1,rhs=0,direction="<="):
345 """
346 Quadratic constraint constructor.
347
348 - Arguments:
349 - name: Name of quadratic constraint.
350 - weight (optional): Positive integer representing importance of constraint.
351 - rhs: Right-hand-side constant of linear constraint.
352 - direction: Direction (or sense) of linear constraint; "<=" (default) or ">=" or "=".
353
354 - Attributes:
355 - name: Name of quadratic constraint.
356 - weight (optional): Positive integer representing importance of constraint.
357 - rhs: Right-hand-side constant of linear constraint.
358 - direction: Direction (or sense) of linear constraint; "<=" (default) or ">=" or "=".
359 - terms: List of terms in left-hand-side of constraint. Each term is a tuple of coeffcient, variable1, value1, variable2 and value2.
360 """
361 if name==None or name=="":
362 print "error: please specify the name when creating a constraint"
363 raise NameError
364 self.name = name
365 self.weight = str(weight)
366 self.rhs = rhs
367 self.direction = direction
368 self.terms = []
369
371 """
372 Returns the information of the quadratic constraint.
373
374 The constraint is expanded and is shown in a readable format
375 """
376 f = self.name+": weight= "+self.weight+" type=quadratic "
377 for (coeff,var1,value1,var2,value2) in self.terms:
378 f += str(coeff)+"("+var1.name +","+ str(value1)+") ("+var2.name +","+ str(value2)+") "
379 f += self.direction+str(self.rhs) +"\n"
380 return f
381
382 - def addTerms(self,coeffs=[],vars=[],values=[],vars2=[],values2=[]):
383 """
384 Adds new terms into left-hand-side of quadratic constraint.
385
386 - Arguments:
387 - coeffs: Coefficients for new terms; either a list of coefficients or a single coefficient. The five arguments must have the same size.
388 - vars: Variables for new terms; either a list of variables or a single variable. The five arguments must have the same size.
389 - values: Values for new terms; either a list of values or a single value. The five arguments must have the same size.
390 - vars2: Variables for new terms; either a list of variables or a single variable. The five arguments must have the same size.
391 - values2: Values for new terms; either a list of values or a single value. The five arguments must have the same size.
392
393 - Example usage:
394
395 >>> Q.addTerms(1.0, y, "A", z, "B")
396
397 >>> Q.addTerms([2, 3, 1], [y, y, z], ["C", "D", "C"], \
398 [x, x, y], ["A", "B", "C"])
399
400 which adds the left-hand-side 2 X[y,"C"] X[x,"A"]+3 X[y,"D"] X[x,"B"]+1 X[z,"C"] X[y,"C"].
401 """
402 if type(coeffs) !=type([]):
403 self.terms.append( (coeffs,vars,values,vars2,values2))
404 elif type(coeffs)!=type([]) or type(vars)!=type([]) or type(values)!=type([]) \
405 or type(vars2)!=type([]) or type(values2)!=type([]):
406 print "coeffs, vars, values must be lists"
407 raise TypeError
408 elif len(coeffs)!=len(vars) or len(coeffs)!=len(values) or len(values)!=len(vars) \
409 or len(coeffs)!=len(vars2) or len(coeffs)!=len(values2):
410 print "length of coeffs, vars, values must be identical"
411 raise TypeError
412 else:
413 for i in range(len(coeffs)):
414 self.terms.append( (coeffs[i],vars[i],values[i],vars2[i],values2[i]))
415
417 """
418 Sets the right-hand-side of quadratic constraint.
419
420 - Argument:
421 - rhs: Right-hand-side of quadratic constraint.
422
423 - Example usage:
424
425 >>> Q.setRhs(10)
426
427 """
428 self.rhs = rhs
429
431 """
432 Sets the direction (or sense) of quadratic constraint.
433
434 - Argument:
435 - direction: direction (or sense) of quadratic constraint; "<=" (default) or ">=" or "=."
436
437 - Example usage:
438
439 >>> Q.setDirection("=")
440
441 """
442 if direction in ["<=", ">=", "="]:
443 self.direction = direction
444 else:
445 print "direction setting error"
446
448 """
449 Returns True if the constraint is defined correctly.
450 """
451 for (coeff,var1,value1,var2,value2) in self.terms:
452 if var1.name not in allvars:
453 print "no variable in the problem instance named %r" % var1.name
454 raise NameError
455 if var2.name not in allvars:
456 print "no variable in the problem instance named %r" % var2.name
457 raise NameError
458 if value1 not in allvars[var1.name]:
459 print "no value %r for the variable named %r" % (value1, var1.name)
460 raise NameError
461 if value2 not in allvars[var2.name]:
462 print "no value %r for the variable named %r" % (value2, var2.name)
463 raise NameError
464 return True
465
467 - def __init__(self,name=None,varlist=None,weight=1):
468 """
469 Alldiff type constraint constructor.
470
471 - Arguments:
472 - name: Name of all-different type constraint.
473 - varlist (optional): List of variables that must have differennt value indices.
474 - weight (optional): Positive integer representing importance of constraint.
475
476 - Attributes:
477 - name: Name of all-different type constraint.
478 - varlist (optional): List of variables that must have differennt value indices.
479 - weight (optional): Positive integer representing importance of constraint.
480 """
481 if name==None or name=="":
482 print "error: please specify the name when creating a constraint"
483 raise NameError
484 self.name = name
485 self.weight = str(weight)
486
487 if varlist==None:
488 self.variables = set([])
489 else:
490 self.variables = set(varlist)
491
493 """
494 Return the information of the alldiff constraint.
495 """
496 f = self.name+": weight= "+self.weight+" type=alldiff "
497 for var in self.variables:
498 f += var.name+" "
499 f += "; \n"
500 return f
501
503 """
504 Adds new variable into all-different type constraint.
505
506 - Arguments:
507 - var : Variable object added to all-different type constraint.
508
509 - Example usage:
510
511 >>> AD.addVaeiable( x )
512 """
513 if var in self.variables:
514 print "duplicate variable name error when adding variable %r" % var
515 return False
516 self.variables.add(var)
517
519 """
520 Adds variables into all-different type constraint.
521
522 - Arguments:
523 - varlist: List or tuple of variable objects added to all-different type constraint.
524
525 - Example usage:
526
527 >>> AD.addVariables( x, y, z )
528
529 >>> AD.addVariables( [x1,x2,x2] )
530 """
531 for var in varlist:
532 self.addvar(var)
533
535 """
536 Returns True if the constraint is defined correctly.
537 """
538 for var in self.variables:
539 if var.name not in allvars:
540 print "no variable in the problem instance named %r" % var.name
541 raise NameError
542 return True
543
544
546 """
547 SCOP parameter class to control the operation of SCOP.
548 @param TimeLimit: Limits the total time expended (in seconds). Positive integer. Default=600.
549 @param OutputFlag: Controls the output log. Boolean. Default=False (0).
550 @param RandomSeed: Sets the random seed number. Integer. Default=1.
551 @param Target: Sets the target penalty value; optimization will terminate if the solver determines that the optimum penalty value for the model is worse than the specified "Target." Non-negative integer. Default=0.
552 """
554 self.TimeLimit=600
555 self.OutputFlag=0
556 self.RandomSeed=1
557 self.Target =0
558