I created a graph coloring DOcplex.CP model inspired by this example. However, I do not know the number of colors in advance. The goal is to minimize the number of colors (i.e., get as close as possible to the graph chromatic number):
import docplex import itertools graph_edges = [(0, 1), (0, 2), (1, 3), (2, 4)] num_nodes = max(itertools.chain.from_iterable(graph_edges)) + 1 mdl = docplex.cp.model.CpoModel() color_vars = mdl.integer_var_list(num_nodes, min=0) for n1, n2 in graph_edges: mdl.add(color_vars[n1] != color_vars[n2]) mdl.minimize(mdl.max(color_vars)) msol = mdl.solve(TimeLimit=120.0) colors = [msol[color_var] for color_var in color_vars] print(str(colors))
I noticed that for rather small graphs (~20 nodes, ~200 edges) my own very simple graph coloring constraint programming algorithm works way faster than this model and proves optimality more often.
I tried to fix one variable in this model (in order to break the symmetry), and that improved the model performance. I have a couple of other similar basic techniques in mind that I could apply to the model. (I mean, such techniques do not depend on a specific solver.)
But is that possible to somehow tune the DOcplex.CP solver itself or provide it some meta-information about the problem? i.e., help the solver to recognize the problem? (The way the CPLEX network optimizer recognizes the problems with network structure.)