如何在 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约束可能会有所帮助。在为每个实例生成迷你锌程序时，必须这样做。有关比较，请参阅使用预先计算的集团的 Gecode 图形着色示例。

Answer 2

我知道这是一个老问题，但我正在研究同样的问题，我想写下我对这个主题的发现，也许它对将来的某人有用。

为了改进模型，解决方案是像您一样使用对称破坏约束，但在 Minizinc 中有一个称为value_precede的全局约束，可用于这种情况。

% 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));

更改搜索启发式结果并没有太大改善，我尝试了不同的配置，并且使用dom_w_deg和indomain_min(与我的数据文件相比(获得最佳结果。

改善结果的另一种方法是接受任何小于域中颜色数量的足够好的解决方案。 但是这种模型并不总是导致获得最佳结果。

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

可以在此处找到清晰完整的解释： https://maxpowerwastaken.gitlab.io/model-idiot/posts/graph_coloring_and_minizinc/