MiniZinc地理编码未将所有解决方案打印到启用了“所有”解决方案的CSP
Issue
使用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}]。My code仅输出 {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);回答 2
Stack Overflow用户
发布于 2019-05-13 01:11:46
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)"
];Stack Overflow用户
发布于 2019-05-13 18:15:41
另一种解决方案是使用。
在优化模式下请求all solutions时，求解器将返回具有相同最佳值的所有解(相对于输出变量)。
示例：
~$ 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]);
----------
=========wrt的主要优势。在被接受的答案中提出的方法是OptiMathSAT是incremental，这意味着该工具无需重启即可搜索其他解决方案，因此它可以重用之前生成的任何有用信息来加速搜索(例如理论引理)。注意:这可能与小实例无关；此外，根据输入问题，其他MiniZinc求解器可能会更快
注意：请注意，OptiMathSAT不会打印每个VERTEX的标签，因为mzn2fzn编译器在编译文件时会删除这些标签。但是，数字和标签之间的映射应该是明显的。
披露：我是这个工具的开发人员之一。
https://stackoverflow.com/questions/56100045
复制相似问题