Could DOcplex.CP recognize that it solves the graph coloring minimization problem?

Question

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.)

Answer 1

The automatic search of CP Optimizer does not try to recognize a graph colouring problem. As you notice, fixing the colour of one variable to get rid of some symmetries in the model may help. Extending this idea and fixing the colours of one clique may further help. Such dominance rules are not automatically inferred in CP Optimizer but are let to the user to add them to the model.

For giving hints to the solver besides model changes, one can define "search phases" for ordering variables and values (in the Python API, look for the search_phase() function).

Alternatively, the search can be entirely defined by the user through the concept of "goals" (only with the C++ API).

Another remark is that the solver has different parameters that have default values and that a user can change. The default values are expected to work correctly for very different kinds of problems, but when targeting a given family of problems, specific parameters can be much better.

A related feature is the possibility to inject a starting solution (possibly partial). The solver tries to improve it (see set_starting_point() in Python).

Answer 2

within 4s with your data set CPLEX both MIP and Constraint Programming prove optimality

In OPL

int n1=164;
    int n2=2;
    range r1=1..n1;
    range r2=1..n2;

    int values[i in r1][j in r2]=0;

    execute
    {

    // Read in file the 2D array values with seperator sep and ranges range1 and range2
    function read2D(file,range1,range2,values,sep)
    {
    for(var i in r1)
    {
       line=file.readline();
       var ar=line.split(sep);
       var k=0;
       for(var j in r2)
       {
          values[i][j]=ar[k];
          k++;   
       }
    }

    }
    }




    execute
    {
    var f= new IloOplInputFile("input");
    read2D(f,r1,r2,values," ");
    f.close();

    writeln("values = ",values);
    }


    int mini=min(i in r1,j in r2) values[i,j]; 
int maxi=max(i in r1,j in r2) values[i,j];   

//using CP; // Whether to use CPOptimizer or CPLEX is we comment using CP;

execute
{
if (thisOplModel.modelDefinition.isUsingCP()) 
{
 cp.param.timelimit=4;
 cp.param.AllDiffInferenceLevel=6;
 }
else 
{
  cplex.tilim=4;
} 
}  



range nodes=mini..maxi;

dvar int color[nodes] in nodes;

minimize 1+max(n in nodes) color[n];

subject to
{
// break sym
color[mini]==mini;
 forall(i in r1) color[values[i][1]]!=color[values[i][2]];
 }

gives a solution both with using CP; and without

The setting

cp.param.AllDiffInferenceLevel=6; 

helps