1

我有一个变量数组和它们之间的线性约束列表。对于每个变量，我都有一个集合，其中包含一个有效值的起始列表。使用 Minizinc，我怎样才能将这些起始值集减少到仅能满足约束的那些？

一个简单的例子来展示我想要实现的目标：

array[1..2] of var int: xy;
array[1..2] of set of int: xyvalid = [ {1, 5, 7}, 0..9 ];

constraint forall(i in 1..2)( xy[i] in xyvalid[i] );
constraint xy[1] + xy[2] = 7;

当我用一个solve satisfy项目运行它并打印所有解决方案时xy，我得到（删除了水平线）：

[1, 6]
[5, 2]
[4, 3]
[3, 4]

我想要的是以某种方式获得一个 var set 数组，调用它xypossible，在这种情况下等于[ {1, 3, 4, 5}, {2, 3, 4, 6} ]。我想我可以定义一组约束，以某种方式检查，对于 中的每个可能值xypossible[1]，有一个值xypossible[2]产生一个有效的解决方案，反之亦然，然后求解以最大化 中所有集合的总基数xypossible，但是当我的真实数据可能是几百个变量的规模时，有几十个线性约束，这对于代码来说很难看，而且运行起来很糟糕。

如果没有一种很好的方法可以将其作为模型，那么有没有一种方法可以捕获信息作为求解器识别有效值作为其自身工作的一部分的结果？

4

1 回答 1

1

我假设您的意思是结果应该是 [{1,5,7},{0,2,6}] 因为 xy[1] 的唯一可能值是在“xyvalid”中说明的 {1,5,7}大批; 0、2 和 6 是唯一在与 1,5 和 7 相加时产生 7 的值。否则，我一定错过了什么……

这是一个可能以您想要的方式工作的模型。尽管它需要一个最大化的目标才能挑选出最佳解决方案。

% the domains of the two variables
array[1..2] of set of int: xyvalid = [ {1, 5, 7}, 0..9 ];

% the result sets 
array[1..2] of var set of 0..9: z;

% ensure that the largest solution is picked 
solve maximize card(z[1]) + card(z[2]);

constraint
   % get the domains of each variable set 
   forall(i in 1..2)( z[i] subset xyvalid[i] ) /\
   % ensure that for all valid values in z[1] are in z[2] given
   % that j + k = 7 
   forall(j in z[1]) (
       exists(k in z[2]) (j + k = 7)
   ) 
   /\
   % and ensure that all valid values in z[2] are in z[1]
   forall(k in z[2]) (
        exists(j in z[1]) (j + k = 7)
   )
   ;

那么结果就是

  z = array1d(1..2 ,[{1,5,7}, {0,2,6}]);

如果没有最大化目标，将有 8 个解决方案：

  z = array1d(1..2 ,[{1,5,7}, {0,2,6}]);
  ----------
  z = array1d(1..2 ,[{1,7}, {0,6}]);
  ----------
  z = array1d(1..2 ,[{5,7}, {0,2}]);
  ----------
  z = array1d(1..2 ,[7..7, 0..0]);
  ----------
  z = array1d(1..2 ,[{1,5}, {2,6}]);
  ----------
  z = array1d(1..2 ,[1..1, 6..6]);
  ----------
  z = array1d(1..2 ,[5..5, 2..2]);
  ----------
  z = array1d(1..2 ,[{}, {}]);
  ----------
  ==========

（其中一些可能已被一些额外的限制删除）

我个人的方法可能是使用您的变体并通过一些外部程序收集可能的值。

注意：在某些 CP 系统中，可以在标记之前打印决策变量的域（即尝试找到正确的有效值）。但是 MiniZinc 没有这个功能。我想念那个。

注意 2：我测试了 dom() 函数，它给出了决策变量的域，但我无法让它工作。

于 2017-02-01T22:09:45.297 回答