SCOPExample

1 2 from scop2 import * 3

4 -def assign1():

5 """ 6 assign1.py: 7 Using SCOP for solving an assignment problem 8 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2011 9 10 Example 1 (Assignment Problem): 11 Three jobs (0,1,2) must be assigned to three workers (A,B,C) 12 so that each job is assigned to exactly one worker. 13 The cost matrix is represented by the list of lists 14 Cost=[[15, 20, 30], 15 [7, 15, 12], 16 [25,10,13]], 17 where rows of the matrix are workers, and columns are jobs. 18 Find the minimum cost assignment of workers to jobs. 19 """ 20 21 m=Model() 22 workers=["A","B","C"] 23 Cost=[[15, 20, 30],[7, 15, 12],[25,10,13]] 24 25 varlist=m.addVariables(workers,range(3)) 26 27 #con1=Alldiff("AD",varlist,weight="inf") 28 con1=Alldiff("AD",varlist) 29 con1.setWeight("inf") 30 con2=Linear("L",weight=1,rhs=0,direction="<=") 31 for i in range(len(workers)): 32 for j in range(3): 33 con2.addTerms(Cost[i][j],varlist[i],j) 34 m.addConstraint(con1) 35 m.addConstraint(con2) 36 m.Params.TimeLimit=1 37 sol,violated=m.optimize() 38 39 print m 40 41 print "solution" 42 for x in sol: 43 print x,sol[x] 44 print "violated constraint(s)" 45 for v in violated: 46 print v,violated[v]

47 48 ##number of variables = 3 49 ##number of constraints= 2 50 ##variable A:[0, 1, 2] 51 ##variable B:[0, 1, 2] 52 ##variable C:[0, 1, 2] 53 ##AD: weight= inf type=alldiff A B C ; 54 ##L: weight= 1 type=linear 15(A,0) 20(A,1) 30(A,2) 7(B,0) 15(B,1) 12(B,2) 25(C,0) 10(C,1) 13(C,2) <=0 55 ## 56 ##solution 57 ##A 0 58 59 ##C 1 60 ##B 2 61 62 ##violated constraint(s) 63 ##L 37 64

65 -def assign2():

66 """ 67 assign2.py: 68 Using SCOP for solving an assignment problem under linear constraints. 69 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2011 70 71 Example 2 (Generalized Assignment Problem): 72 Three jobs (0,1,2) must be assigned to five workers (A,B,C,D,E). 73 The numbers of workers that must be assigned to jobs 0,1 and 2 are 1,1 and 2, respectively. 74 The cost matrix is represented by the list of lists 75 Cost=[[15, 20, 30], 76 [7, 15, 12], 77 [25,10,13], 78 [15,18,3], 79 [5,12,17]] 80 where rows are workers, and columns are jobs. 81 Find the minimum cost assignment of workers to jobs. 82 83 """ 84 85 m=Model() 86 workers=["A","B","C","D","E"] 87 Cost=[[15, 20, 30],[7, 15, 12],[25,10,13],[15,18,3],[5,12,17]] 88 LB=[1,2,2] 89 varlist=m.addVariables(workers,range(3)) 90 LBC={} #dictionary for keeping lower bound constraints 91 for j in range(len(LB)): 92 LBC[j]=Linear("LB%s"%j,"inf",LB[j],">=") 93 coeffs=[1 for i in range(5)] 94 values=[j for i in range(5)] 95 LBC[j].addTerms(coeffs,varlist,values) 96 m.addConstraint(LBC[j]) 97 con1=Linear("L") 98 for i in range(len(workers)): 99 for j in range(3): 100 con1.addTerms(Cost[i][j],varlist[i],j) 101 m.addConstraint(con1) 102 m.Params.TimeLimit=1 103 sol,violated=m.optimize() 104 print m 105 print "solution" 106 for x in sol: 107 print x,sol[x] 108 print "violated constraint(s)" 109 for v in violated: print v,violated[v]

110 111 112 ##number of variables = 5 113 ##number of constraints= 4 114 ##variable A:[0, 1, 2] 115 ##variable B:[0, 1, 2] 116 ##variable C:[0, 1, 2] 117 ##variable D:[0, 1, 2] 118 ##variable E:[0, 1, 2] 119 ##LB_constraint0: weight= inf type=linear 1(A,0) 1(B,0) 1(C,0) 1(D,0) 1(E,0) >=1 120 ##LB_constraint1: weight= inf type=linear 1(A,1) 1(B,1) 1(C,1) 1(D,1) 1(E,1) >=2 121 ##LB_constraint2: weight= inf type=linear 1(A,2) 1(B,2) 1(C,2) 1(D,2) 1(E,2) >=2 122 ##linear_constraint: weight= 1 type=linear 15(A,0) 20(A,1) 30(A,2) 7(B,0) 15(B,1) 12(B,2) 25(C,0) 10(C,1) 13(C,2) 15(D,0) 18(D,1) 3(D,2) 5(E,0) 12(E,1) 17(E,2) <=0 123 ## 124 ##solution 125 ##A 1 126 127 ##C 1 128 129 ##B 2 130 131 ##E 0 132 ##D 2 133 134 ##violated constraint(s) 135 ##linear_constraint 50 136

137 -def assign3():

138 """ 139 assign3.py: 140 Using SCOP for solving an assignment problem under a quadratic constraint. 141 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2011 142 143 Example 3 (Variation of Generalized Assignment Problem): 144 Three jobs (0,1,2) must be assigned to five workers (A,B,C,D,E). 145 The numbers of workers that must be assigned to jobs 0,1 and 2 are 1,1 and 2, respectively. 146 The cost matrix is represented by the list of lists 147 Cost=[[15, 20, 30], 148 [7, 15, 12], 149 [25,10,13], 150 [15,18,3], 151 [5,12,17]] 152 where rows are workers, and columns are jobs. 153 We add an additional condition: worker A cannot do the job with worker C. 154 Find the minimum cost assignment of workers to jobs. 155 156 """ 157 158 m=Model() 159 160 workers=["A","B","C","D","E"] 161 Cost=[[15, 20, 30],[7, 15, 12],[25,10,13],[15,18,3],[5,12,17]] 162 LB=[1,2,2] 163 164 varlist=m.addVariables(workers,range(3)) 165 166 LBC={} #dictionary for keeping lower bound constraints 167 for j in range(len(LB)): 168 LBC[j]=Linear("LB%s"%j,"inf",LB[j],">=") 169 for i in range(len(workers)): 170 LBC[j].addTerms(1,varlist[i],j) 171 m.addConstraint(LBC[j]) 172 173 con1=Linear("L") 174 for i in range(len(workers)): 175 for j in range(3): 176 con1.addTerms(Cost[i][j],varlist[i],j) 177 m.addConstraint(con1) 178 179 #Method 1: by calling addTerms just once 180 ## coeffs=[1,1,1] 181 ## var1=[varlist[0],varlist[0],varlist[0]] 182 ## var2=[varlist[2],varlist[2],varlist[2]] 183 ## vallist=[0,1,2] 184 ## vallist2=[0,1,2] 185 ## con2=Quadratic("quadratic_constraint",100) 186 ## con2.addTerms(coeffs,var1,vallist,var2,vallist2) 187 188 #Method 2: using addTerms to add terms one by one (recommendation) 189 con2=Quadratic("Q",100) 190 for j in range(3): 191 con2.addTerms(1,varlist[0],j,varlist[2],j) 192 m.addConstraint(con2) 193 194 m.Params.TimeLimit=1 195 sol,violated=m.optimize() 196 197 print m 198 199 print "solution" 200 for x in sol: 201 print x,sol[x] 202 print "violated constraint(s)" 203 for v in violated: 204 print v,violated[v]

205 206 ##number of variables = 5 207 ##number of constraints= 5 208 ##variable A:[0, 1, 2] 209 ##variable B:[0, 1, 2] 210 ##variable C:[0, 1, 2] 211 ##variable D:[0, 1, 2] 212 ##variable E:[0, 1, 2] 213 ##LB_constraint0: weight= inf type=linear 1(A,0) 1(B,0) 1(C,0) 1(D,0) 1(E,0) >=1 214 ##LB_constraint1: weight= inf type=linear 1(A,1) 1(B,1) 1(C,1) 1(D,1) 1(E,1) >=2 215 ##LB_constraint2: weight= inf type=linear 1(A,2) 1(B,2) 1(C,2) 1(D,2) 1(E,2) >=2 216 ##linear_constraint: weight= 1 type=linear 15(A,0) 20(A,1) 30(A,2) 7(B,0) 15(B,1) 12(B,2) 25(C,0) 10(C,1) 13(C,2) 15(D,0) 18(D,1) 3(D,2) 5(E,0) 12(E,1) 17(E,2) <=0 217 ##quadratic_constraint: weight= 100 type=quadratic 1(A,0) (C,0) 1(A,1) (C,1) 1(A,2) (C,2) <=0 218 ## 219 ##solution 220 ##A 0 221 222 ##C 1 223 224 ##B 2 225 226 ##E 1 227 ##D 2 228 229 ##violated constraint(s) 230 ##linear_constraint 52 231

Source Code for Module SCOPExample