1
问题

solve minimize即使有多个最佳解决方案，我也只能得到一个解决方案。我在求解器配置中启用了多个解决方案的打印输出。其他最优解solve satisfy与非最优解一起找到。

可能的原因

可能是基数函数card()在两个集合的大小相等的情况下按枚举值排序吗？换句话说，那card(A, B) > card(B, C)？如果是这样，我是否必须切换顶点的表示？

该程序

我正在创建一个 MiniZinc 程序来查找给定图形的最小顶点覆盖。此示例中的图表是这样的：

示例图

最小顶点覆盖解决方案是： [{A, B, C, E}, {A, B, E, F}, {A, C, D, E}, {B, C, D, E}, {B, C, D, F}, {B, D, E, F}]. 我的代码只输出{A, B, C, E}.

数据文件：

VERTEX = {A, B, C, D, E, F};
       
edges = [|1, 0, 1, 0, 0, 0, 0, 0, 0
         |1, 1, 0, 1, 1, 0, 0, 0, 0
         |0, 1, 0, 0, 0, 1, 1, 0, 0
         |0, 0, 1, 1, 0, 0, 0, 1, 0
         |0, 0, 0, 0, 1, 1, 0, 1, 1
         |0, 0, 0, 0, 0, 0, 1, 0, 1|];

求解程序：

% Vertices in graph
enum VERTEX;

% Edges between vertices
array[VERTEX, int] of int: edges;

int: num_edges = (length(edges) div card(VERTEX));

% Set of vertices to find
var set of VERTEX: span;

% Number of vertices connected to edge resulting from span
array[1..num_edges] of var 0..num_edges: conn;

% All edges must be connected with at least one vertex from span
constraint forall(i in 1..num_edges)
           (conn[i] >= 1);

% The number of connections to each edge is the number of vertices 
% in span with a connection to that edge
constraint forall(i in 1..num_edges)
           (conn[i] = sum([edges[vert,i]| vert in span]));
           
% Minimize the number of vertices in span
solve minimize card(span);
4

2 回答 2

4

solve minimize仅显示一种最佳解决方案（在某些情况下，还可能显示中间值）。

如果您想要所有最佳解决方案，则必须使用solve satisfy 并添加具有最佳值的约束：

constraint card(span) = 4;

然后模型输出所有 6 个最优解：

card(cpan): 4
span: {A, B, C, E}
conn: [2, 2, 1, 1, 2, 2, 1, 1, 1]
----------
card(cpan): 4
span: {B, C, D, F}
conn: [1, 2, 1, 2, 1, 1, 2, 1, 1]
----------
card(cpan): 4
span: {A, C, D, E}
conn: [1, 1, 2, 1, 1, 2, 1, 2, 1]
----------
card(cpan): 4
span: {B, C, D, E}
conn: [1, 2, 1, 2, 2, 2, 1, 2, 1]
----------
card(cpan): 4
span: {A, B, E, F}
conn: [2, 1, 1, 1, 2, 1, 1, 1, 2]
----------
card(cpan): 4
span: {B, D, E, F}
conn: [1, 1, 1, 2, 2, 1, 1, 2, 2]
----------
==========

注意：我添加了output显示所有值的部分：

output [
   "card(cpan): \(card(span))\n",
   "span: \(span)\n",
   "conn: \(conn)"
];
于 2019-05-12T17:11:45.557 回答
2

另一种解决方案是使用OptiMathSAT (v. 1.6.3)。

在优化模式下询问所有解决方案时，求解器返回具有相同最优值的所有解决方案（关于输出变量） 。

例子：

~$ mzn2fzn test.mzn test.dzn                                        # your instance
~$ optimathsat -input=fzn -opt.fzn.all_solutions=True < test.fzn 
% allsat model
span = {2, 4, 5, 6};
conn = array1d(1..9, [1, 1, 1, 2, 2, 1, 1, 2, 2]);
----------
% allsat model
span = {1, 3, 4, 5};
conn = array1d(1..9, [1, 1, 2, 1, 1, 2, 1, 2, 1]);
----------
% allsat model
span = {1, 2, 3, 5};
conn = array1d(1..9, [2, 2, 1, 1, 2, 2, 1, 1, 1]);
----------
% allsat model
span = {1, 2, 5, 6};
conn = array1d(1..9, [2, 1, 1, 1, 2, 1, 1, 1, 2]);
----------
% allsat model
span = {2, 3, 4, 5};
conn = array1d(1..9, [1, 2, 1, 2, 2, 2, 1, 2, 1]);
----------
% allsat model
span = {2, 3, 4, 6};
conn = array1d(1..9, [1, 2, 1, 2, 1, 1, 2, 1, 1]);
----------
=========

主要优势。接受的答案中提出的方法是 OptiMathSAT 是增量的，这意味着该工具无需重新启动即可搜索其他解决方案，因此它可以重新使用先前生成的任何有用信息来加速搜索（例如理论引理）。[警告：这可能与小实例无关；此外，根据输入问题，其他 MiniZinc 求解器可能仍然更快]

注意：请注意OptiMathSAT不会打印每个的标签VERTEX，因为mzn2fzn编译器在编译文件时会删除这些标签。但是，数字和标签之间的映射应该是显而易见的。

披露：我是这个工具的开发者之一。

于 2019-05-13T10:15:40.520 回答