objective function for graph coloring with ORtools solver

1
votes

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
optimizationor-toolsconstraint-programminggraph-coloringobjective-function
len(set(solution)) is a constant, you could minimize the max value of solutions using addmaxequality, or model the problem using booleans – Stradivari
obj_var = model.NewIntVar(0, node_count, 'makespan') model.AddMaxEquality(obj_var,solution) model.Minimize(obj_var) – Asael Bar Ilan
something like this? because its still not working :/ thanks though – Asael Bar Ilan
what is solution? a dict? maybe you need solution.values()? – Stradivari
solution is a list of the colors each node will get, at the beginning its zeros array but solver is supposed to put a color for each node in every cell-its just an array for vaiables here. colors is reciving the answer from solver - i do get a list, but it isnt optimal. solution isn't accessible, only solver.Value(solution[i]) gives solution values...so i can reach solution.values – Asael Bar Ilan