4 Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
7 from pyscipopt
import Model, quicksum
11 """gcp_fixed_k -- model for minimizing number of bad edges in coloring a graph
13 - V: set/list of nodes in the graph
14 - E: set/list of edges in the graph
15 - K: number of colors to be used
16 Returns a model, ready to be solved.
18 model = Model(
"gcp - fixed k")
23 x[i, k] = model.addVar(vtype=
"B", name=
"x(%s,%s)" % (i, k))
25 z[i, j] = model.addVar(vtype=
"B", name=
"z(%s,%s)" % (i, j))
28 model.addCons(
quicksum(x[i, k]
for k
in range(K)) == 1,
"AssignColor(%s)" % i)
32 model.addCons(x[i, k] + x[j, k] <= 1 + z[i, j],
"BadEdge(%s,%s,%s)" % (i, j, k))
34 model.setObjective(
quicksum(z[i, j]
for (i, j)
in E),
"minimize")
41 """solve_gcp -- solve the graph coloring problem with bisection and fixed-k model
43 - V: set/list of nodes in the graph
44 - E: set/list of edges in the graph
45 Returns tuple with number of colors used, and dictionary mapping colors to vertices
51 K = int((UB + LB) / 2)
57 status = gcp.getStatus()
58 if status ==
"optimal":
62 if gcp.getVal(x[i, k]) > 0.5:
78 """make_data: prepare data for a random graph
80 - n: number of vertices
81 - prob: probability of existence of an edge, for each pair of vertices
82 Returns a tuple with a list of vertices and a list edges.
85 E = [(i, j)
for i
in V
for j
in V
if i < j
and random.random() < prob]
89 if __name__ ==
"__main__":
94 print(
"minimum number of colors:", K)
95 print(
"solution:", color)