i wrote a cp function to solve graph coloring with ORtools
(minimizing color usage, when the colors of every two vertices on an edge needs to be different) i get weird result,which isnt optimal, and im not sure why- i think my objective function is wrong, or my constraint formulation,any help? thanks
def cp_with_ortools(node_count, edge_count, edges, M, solution, max_degree):
global colors
from ortools.sat.python import cp_model
solution = [0] * (node_count)# list of colors to nodes initialized with 0
# Creates the model.
model = cp_model.CpModel()
# Creates the variables.
for i in range(node_count):
solution[i] = model.NewIntVar(0, int(node_count), '')
#shouldnt be max_degree? isnt working..
# Adds constraint
for edge in edges:
model.Add(solution[edge[0]] != solution[edge[1]])
# Create the objective function
obj_var = model.NewIntVar(0, node_count, 'makespan')
model.AddMaxEquality(obj_var,solution)
model.Minimize(obj_var)
#model.Minimize(len(set(solution)))
#model.Minimize(sum(solution)))
# Creates a solver and solves the model.
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
colors = [solver.Value(solution[i]) for i in range(node_count)]
return colors