optimization - 如何提高 MiniZinc 中图形着色模型的性能？

Question

我创建了一个模型来解决 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;

为了解决大问题(大约 400-500 个节点)，我从颜色数量的上限开始，并解决连续的满意度问题，将数量递减 1，直到它变得不可满足或超时。这种方法给了我不错的结果。

为了改进结果，我在上述模型中添加了对称破缺约束:

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

然而，这降低了我的速度和质量的结果。

为什么我的模型在添加额外约束后表现不佳？我应该如何添加对称破缺约束？

Answer 1

对于值完全对称的情况下的对称性破坏，我建议 seq_precede_chain约束，打破了这种对称性。正如 @hakank 所评论的，当与对称性破坏一起使用时，使用 indomain_random 可能不是一个好主意，indomain_min 是一个更安全的选择。

对于一般的图形着色，运行派别查找算法并对找到的每个派别施加 all_ different 约束可能有助于提高性能。在为每个实例生成 minizinc 程序时必须完成此操作。如需比较，请参阅Gecode graph coloring example which uses pre-computed cliques .