Module scop2
[hide private]
[frames] | no frames]

Source Code for Module scop2

  1  # scop interface class 
  2  # file name scop2.py 
  3  # ver. 2 Copyright Log Opt Co., Ltd. 
  4  # by J. P. Pedroso and M. Kubo 
  5           
6 -class Model(object):
7 - def __init__(self):
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 = [] # set of constraints is maintained by a list 17 self.variables = [] # set of variables is maintained by a list 18 self.Params=Parameters() 19 self.varDict={} # dictionary that maps variable names to their domains
20
21 - def __str__(self):
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
35 - def update(self):
36 """ 37 Prepares a string representing the current model in the scop input format. 38 """ 39 f = "" 40 #variable declarations 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 #target value declaration 45 f += "target = %s \n" % str(self.target) 46 #constraint declarations 47 for con in self.constraints: 48 f += str(con) 49 return f
50
51 - def addVariable(self, name="", domain=[]):
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 # keep variable names using the dictionary varDict to check the validity of constraints 71 self.varDict[var.name]=var.domain 72 return var
73
74 - def addVariables(self, names=[], domain=[]):
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
102 - def addConstraint(self, con):
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 #check the feasibility of the constraint added in the class con 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 ## def addConstraints(self,*cons): 126 ## for c in cons: 127 ## self.addConstraint(c) 128
129 - def optimize(self):
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) #solver call 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) #get the result 158 if LOG: 159 print "scop output: \n"+f 160 print out, '\n' 161 162 #extract the solution and the violated constraints 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 #return dictionaries containing the solution and the violated constraints 188 return sol,violated
189
190 -class Variable():
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 """
196 - def __init__(self,name="",domain=[]):
197 self.name=str(name) 198 self.domain=list(domain)
199
200 - def __str__(self):
201 return "variable "+str(self.name)+":"+str(self.domain)
202
203 -class Constraint(object):
204 """ 205 Constraint base class. 206 """
207 - def setWeight(self,weight):
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
224 -class Linear(Constraint):
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
252 - def __str__(self):
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([]): #need a check whether coeffs is numeric ... 281 #arguments are nor list; add a term 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
297 - def setRhs(self,rhs=0):
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
311 - def setDirection(self,direction="<="):
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
329 - def feasible(self,allvars):
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
343 -class Quadratic(Constraint):
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
370 - def __str__(self):
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([]): #need a check whether coeffs is numeric ... 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
416 - def setRhs(self,rhs=0):
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
430 - def setDirection(self,direction="<="):
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
447 - def feasible(self,allvars):
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
466 -class Alldiff(Constraint):
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
492 - def __str__(self):
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
502 - def addVariable(self,var):
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
518 - def addVariables(self, varlist):
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
534 - def feasible(self,allvars):
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
545 -class Parameters():
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 """
553 - def __init__(self):
554 self.TimeLimit=600 555 self.OutputFlag=0 556 self.RandomSeed=1 557 self.Target =0
558