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:
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__":
91 print(
"minimum number of colors:",K)
92 print(
"solution:",color)