MiniZinc 找到 int 的集合

Question

我在 minizinc 中有一个脚本试图找到 int 集，但找不到。问题陈述给出了一组 2 class 个特征，需要找到最小支持集，其长度应小于某个 k，并且对于某些集合数组，它应至少包含一个索引值从他们。因此，假设解决方案是 {3,4,7} 和集合数组（我们称之为 - atmostone）atmostone = [{1,2,3}, {4,5,6}, {7,8 ,9}] 所以解决方案的交集和 atmostone 数组中的每个集合的长度必须恰好为一。

这些是我实现的约束，但错误是模型不一致。

include "globals.mzn";
include "alldifferent.mzn";

int: t; %number of attributes
int: k; %maximum size of support set
int: n; %number of positive instances
int: m; %number of negative instances
int: c; %number of atMostOne Constraints
array [1..n, 1..t] of 0..1: omegap;
array [1..m, 1..t] of 0..1: omegan;
array [int] of set of int: atMostOne;

set of int: K = 1..k;
set of int: T = 1..t;    
var set of T: solution;


function array[int] of var opt int : set2array(var set of int: a) = 
  [i | i in a];

% constraint alldifferent(solution);
constraint length(set2array(solution)) <= k;
constraint forall(i in 1..length(atMostOne))(length(set2array(solution intersect atMostOne[i])) <= 1);
constraint forall(i in 1..n, j in 1..m)(not(omegap[i, fix(solution)] == omegan[j, fix(solution)]));

solve satisfy;

这是错误：

Compiling support_send.mzn

  WARNING: model inconsistency detected
Running support_send.mzn
=====UNSATISFIABLE=====
% Top level failure!
Finished in 88msec

更新：

数据：

t=8; %number of attributes
k=3; %maximum size of support set
n=5; %number of positive instances
m=3; %number of negative instances
c=4; %number of atMostOne Constraints
omegap=[| 0,0,1,0,1,0,0,0 |
1,0,1,1,0,0,0,1|
0,1,0,1,0,0,1,1|
0,1,1,0,1,1,0,1|
0,0,1,0,1,1,1,1
|];
omegan=[| 1,1,0,0,1,0,1,1|
0,1,0,0,1,1,0,0|
1,0,0,1,1,0,0,1
|];

atMostOne =
[{1,2,3},
{4,5,6},
{3,5},
{7,8}];

如有任何帮助，我们将不胜感激。

谢谢。

Answer 1

您模型中的问题源于您设置的变量 solutions。

第一个问题是由set2array函数引起的。您可能认为这个 return 是一个数组，其中的整数位于您的数组中；然而，事实并非如此。相反，它 return 是一个 可选整数 的数组。这意味着您的集合中所有可能的值都存储在数组中，但其中一些可能只是标记为 absent。在这种情况下，它几乎与拥有一个布尔变量数组相同，只是说一个值是否位于集合中。

请注意，约束条件 length(set2array(solution)) <= k 无法满足。因为 solution 比 k 有更多的可能性，所以数组的长度总是更大。您可能想要强制执行的约束是 card(solution) <= k。函数card(X) return 基数/集合的大小。在第二个约束中可以找到同样的问题。

您的最终约束有一个不同的问题：它包含表达式 fix(solution)。在您的模型的上下文中，您不能编写此代码，因为它不会在编译时修复。该表达式的计算结果也为 set of int。虽然您可以使用集合来访问数组、数组切片，但目前不允许使用变量集。我建议尝试为这个约束找到一个不同的公式。（因为我不知道它应该做什么，恐怕我不能提出任何建议）

最后一点，注释掉的约束 alldifferent(solution) 是不必要的。因为 solution 是一个集合，它保证只包含一次值。

MiniZinc 找到 int 的集合

MiniZinc find the set of int

optimization

constraint-programming

minizinc