4 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012 7 from pyscipopt
import Model, quicksum, multidict
10 """gcp_fixed_k -- model for minimizing number of bad edges in coloring a graph 12 - V: set/list of nodes in the graph 13 - E: set/list of edges in the graph 14 - K: number of colors to be used 15 Returns a model, ready to be solved. 17 model = Model(
"gcp - fixed k")
22 x[i,k] = model.addVar(vtype=
"B", name=
"x(%s,%s)"%(i,k))
24 z[i,j] = model.addVar(vtype=
"B", name=
"z(%s,%s)"%(i,j))
27 model.addCons(quicksum(x[i,k]
for k
in range(K)) == 1,
"AssignColor(%s)" % i)
31 model.addCons(x[i,k] + x[j,k] <= 1 + z[i,j],
"BadEdge(%s,%s,%s)"%(i,j,k))
33 model.setObjective(quicksum(z[i,j]
for (i,j)
in E),
"minimize")
40 """solve_gcp -- solve the graph coloring problem with bisection and fixed-k model 42 - V: set/list of nodes in the graph 43 - E: set/list of edges in the graph 44 Returns tuple with number of colors used, and dictionary mapping colors to vertices 56 status = gcp.getStatus()
57 if status ==
"optimal":
61 if gcp.getVal(x[i,k]) > 0.5:
74 def make_data(n,prob):
75 """make_data: prepare data for a random graph 77 - n: number of vertices 78 - prob: probability of existence of an edge, for each pair of vertices 79 Returns a tuple with a list of vertices and a list edges. 82 E = [(i,j)
for i
in V
for j
in V
if i < j
and random.random() < prob]
86 if __name__ ==
"__main__":
88 V,E = make_data(75,.25)
90 K,color = solve_gcp(V,E)
91 print(
"minimum number of colors:",K)
92 print(
"solution:",color)