How to improve the performance of my graph coloring model in MiniZinc?

user_13660965 0
Viewed 766

I have created a model for solving the graph coloring problem in MiniZinc:

include "globals.mzn";

int: n_nodes;               % Number of nodes
int: n_edges;               % Number of edges
int: domain_ub;             % Number of colors
array[int] of int: edges;   % All edges of graph as a 1D array
array[1..n_edges, 1..2] of int: edges2d = array2d(1..n_edges, 1..2, edges);

array[1..n_nodes] of var 1..domain_ub: colors;

constraint forall (i in 1..n_edges) (colors[edges2d[i,1]] != colors[edges2d[i,2]]);

solve :: int_search(colors, dom_w_deg, indomain_random)
    satisfy;

In order to tackle big problems (around 400-500 nodes), I start with an upper bound of the number of colors and solve successive satisfaction problems decrementing the number by one till it becomes unsatisfiable or times out. This method gives me decent results.

In order to improve my results, I added symmetry breaking constraints to the above model:

constraint colors[1] = 1;
constraint forall (i in 2..n_nodes) ( colors[i] in 1..max(colors[1..i-1])+1 );

This, however, brings down my results both speed-wise and quality-wise.

Why is my model performing badly after adding the additional constraints? How should I go about adding the symmetry breaking constraints?

minizinc constraint-programming optimization
2 Answers

For symmetry breaking for cases where the values are fully symmetric, I would recommend the seq_precede_chain constraint, which breaks that symmetry. As commented by @hakank, using indomain_random is probably not a good idea when used with symmetry breaking, indomain_min is a safer choice.

For graph coloring in general, it may help performance to run a clique-finding algorithm, and post all_different constraints over each cliques found. That would have to be done when generating a minizinc program for each instance. For comparison, see the Gecode graph coloring example which uses pre-computed cliques.

user_339650

I know this is an old question, but I was working on the same problem and I wanted to write what I found about this topic that maybe it will be useful to someone in the future.

To improve the model the solution is to use symmetry breaking constraint, as you did, but in Minizinc there is a global constraint called value_precede which can be used in this case.

% A new color J is only allowed to appear after colors 0..J-1 have been seen before (in any order)
constraint forall(j in 1..n-1)(value_precede(j, j+1, map));

Changing the search heuristics the result does not improve much, I have tried different configurations and the best results are obtained using dom_w_deg and indomain_min (compared to my data files).

Another way to improve the results is to accept any good enough solution that's less than the number of colours in the domain. But this model does not always lead to obtaining the optimal result.

include "globals.mzn";

int: n; % Number of nodes
int: e; % Number of edges
int: maxcolors = 17; % Domain of colors

array[1..e,1..2] of int: E; % 2d array, rows = edges, 2 cols = nodes per edge
array[0..n-1] of var 0..maxccolors: c;   % Color of node n

constraint forall(i in 1..e)(c[E[i,1]] != c[E[i,2]] ); % Two linked nodes have diff color
constraint c[0] == 0; % Break Symmetry, force fist color == 0

% Big symmetry breaker. A new color J is only allowed to appear after colors
% 0..J-1 have been seen before (in any order)
constraint forall(i in 0..n-2)( value_precede(i,i+1, c)  );

% Ideally solve would minimize(max(c)), but that's too slow, so we accept any good
% enough solution that's less equal our heuristic "maxcolors"
constraint max(c) <= maxcolors;
solve :: int_search(c, dom_w_deg, indomain_min, complete) satisfy;

output [ show(max(c)+1), "\n", show(c)]

A clear and complete explanation can be found here: https://maxpowerwastaken.gitlab.io/model-idiot/posts/graph_coloring_and_minizinc/

user_110853740
Related