""" gcp_fixed_k.py: solve the graph coloring problem with fixed-k model Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012 """ from gurobipy import * def gcp_fixed_k(V,E,K): """gcp_fixed_k -- model for minimizing number of bad edges in coloring a graph Parameters: - V: set/list of nodes in the graph - E: set/list of edges in the graph - K: number of colors to be used Returns a model, ready to be solved. """ model = Model("gcp - fixed k") x,z = {},{} for i in V: for k in range(K): x[i,k] = model.addVar(vtype="B", name="x(%s,%s)"%(i,k)) for (i,j) in E: z[i,j] = model.addVar(vtype="B", name="z(%s,%s)"%(i,j)) model.update() for i in V: model.addConstr(quicksum(x[i,k] for k in range(K)) == 1, "AssignColor(%s)" % i) for (i,j) in E: for k in range(K): model.addConstr(x[i,k] + x[j,k] <= 1 + z[i,j], "BadEdge(%s,%s,%s)"%(i,j,k)) model.setObjective(quicksum(z[i,j] for (i,j) in E), GRB.MINIMIZE) model.update() model.__data = x,z return model def solve_gcp(V,E): """solve_gcp -- solve the graph coloring problem with bisection and fixed-k model Parameters: - V: set/list of nodes in the graph - E: set/list of edges in the graph Returns tuple with number of colors used, and dictionary mapping colors to vertices """ LB = 0 UB = len(V) color = {} while UB-LB > 1: K = (UB+LB) / 2 gcp = gcp_fixed_k(V,E,K) # gcp.Params.OutputFlag = 0 # silent mode gcp.Params.Cutoff = .1 gcp.optimize() if gcp.status == GRB.Status.OPTIMAL: x,z = gcp.__data for i in V: for k in range(K): if x[i,k].X > 0.5: color[i] = k break # else: # raise "undefined color for", i UB = K else: LB = K return UB,color import random def make_data(n,prob): """make_data: prepare data for a random graph Parameters: - n: number of vertices - prob: probability of existence of an edge, for each pair of vertices Returns a tuple with a list of vertices and a list edges. """ V = range(1,n+1) E = [(i,j) for i in V for j in V if i < j and random.random() < prob] return V,E if __name__ == "__main__": random.seed(1) V,E = make_data(75,.25) K,color = solve_gcp(V,E) print "minimum number of colors:",K print "solution:",color