4 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012 7 from pyscipopt
import Model, quicksum, multidict
10 """gcp -- model for minimizing the number of colors in a graph 12 - V: set/list of nodes in the graph 13 - E: set/list of edges in the graph 14 - K: upper bound on the number of colors 15 Returns a model, ready to be solved. 20 y[k] = model.addVar(vtype=
"B", name=
"y(%s)"%k)
22 x[i,k] = model.addVar(vtype=
"B", name=
"x(%s,%s)"%(i,k))
25 model.addCons(quicksum(x[i,k]
for k
in range(K)) == 1,
"AssignColor(%s)"%i)
29 model.addCons(x[i,k] + x[j,k] <= y[k],
"NotSameColor(%s,%s,%s)"%(i,j,k))
31 model.setObjective(quicksum(y[k]
for k
in range(K)),
"minimize")
38 """gcp_low -- model for minimizing the number of colors in a graph 39 (use colors with low indices) 41 - V: set/list of nodes in the graph 42 - E: set/list of edges in the graph 43 - K: upper bound to the number of colors 44 Returns a model, ready to be solved. 46 model = Model(
"gcp - low colors")
49 y[k] = model.addVar(vtype=
"B", name=
"y(%s)"%k)
51 x[i,k] = model.addVar(vtype=
"B", name=
"x(%s,%s)"%(i,k))
55 model.addCons(quicksum(x[i,k]
for k
in range(K)) == 1,
"AssignColor(%s)" % i)
59 model.addCons(x[i,k] + x[j,k] <= y[k],
"NotSameColor(%s,%s,%s)"%(i,j,k))
62 model.addCons(y[k] >= y[k+1],
"LowColor(%s)"%k)
64 model.setObjective(quicksum(y[k]
for k
in range(K)),
"minimize")
71 """gcp_sos -- model for minimizing the number of colors in a graph 72 (use sos type 1 constraints) 74 - V: set/list of nodes in the graph 75 - E: set/list of edges in the graph 76 - K: upper bound to the number of colors 77 Returns a model, ready to be solved. 79 model = Model(
"gcp - sos constraints")
83 y[k] = model.addVar(vtype=
"B", name=
"y(%s)"%k)
85 x[i,k] = model.addVar(vtype=
"B", name=
"x(%s,%s)"%(i,k))
88 model.addCons(quicksum(x[i,k]
for k
in range(K)) == 1,
"AssignColor(%s)" % i)
89 model.addConsSOS1([x[i,k]
for k
in range(K)])
93 model.addCons(x[i,k] + x[j,k] <= y[k],
"NotSameColor(%s,%s,%s)"%(i,j,k))
96 model.addCons(y[k] >= y[k+1],
"LowColor(%s)"%k)
98 model.setObjective(quicksum(y[k]
for k
in range(K)),
"minimize")
105 def make_data(n,prob):
106 """make_data: prepare data for a random graph 108 - n: number of vertices 109 - prob: probability of existence of an edge, for each pair of vertices 110 Returns a tuple with a list of vertices and a list edges. 113 E = [(i,j)
for i
in V
for j
in V
if i < j
and random.random() < prob]
117 if __name__ ==
"__main__":
119 V,E = make_data(20,.5)
121 print(
"n,K=",len(V),K)
123 model = gcp_low(V,E,K)
125 print(
"Optimal value:", model.getObjVal())
131 if model.getVal(x[i,k]) > 0.5:
133 print(
"colors:",color)
136 models = [gcp,gcp_low,gcp_sos]
139 print(
"#size\t%s\t%s\t%s" % tuple(m.__name__
for m
in models))
140 for size
in range(250):
146 if not (name,size-1,prob)
in cpu
or cpu[name,size-1,prob] < 100:
147 cpu[name,size,prob] = 0.
151 V,E = make_data(size,prob)
155 assert model.getObjVal() >= 0
and model.getObjVal() <= K
157 cpu[name,size,prob] += tend - tinit
158 cpu[name,size,prob] /= N
160 cpu[name,size,prob] =
"-" 161 print(cpu[name,size,prob],
"\t",)