示例通道约束ECLiPSe

Question

有人可以提供一个简单的渠道约束示例吗？

通道约束用于组合约束问题的视点.约束编程手册很好地解释了它是如何工作的以及为什么它有用:

搜索变量可以是其中一个视点的变量,比如X1(这将在下面进一步讨论).随着搜索的进行,传播约束C1从X1中的变量的域中移除值.然后,信道约束可以允许从X2中的变量的域中移除值.使用第二模型C2的约束来传播这些值删除可以从这些变量中移除更多值,并且这些移除可以通过信道约束再次转换回第一视点.最终结果可能是在视点V1内移除的值多于仅由约束C1移除的值,导致搜索减少.

我不明白这是如何实现的.究竟是什么限制,它们在真正的问题中看起来如何？一个简单的例子非常有用.

Answer 1

当在模型中以多种方式表示问题的方面时，将使用通道约束。这样，即使它们本身没有对问题的一个方面建模，也必须使它们同步这些多个表示。

通常，在对具有约束的问题进行建模时，您有几种选择变量的方法。例如，在计划问题中，您可以选择

• 每个作业的整数变量（指示执行该作业的机器）
• 每台机器的整数变量（指示其执行的作业）
• 布尔矩阵（指示哪个作业在哪个计算机上运行）
• 或更奇特的东西

在足够简单的问题中，您选择最易于制定问题约束条件的表示形式。但是，在现实生活中，存在许多不同约束的问题，通常不可能找到这样一个单一的最佳表示形式：某些约束最好用一种类型的变量来表示，而其他约束用另一种类型的变量来最好地表示。

在这种情况下，您可以使用多组变量，并在最方便的变量集上制定每个问题约束。当然，您最终将面临多个独立的子问题，而单独解决这些问题将无法为您解决整个问题。但是，通过添加通道约束，可以同步变量集，并因此重新连接子问题。结果就是整个问题的有效模型。

正如手册中的引用所暗示的那样，这样的表述足以仅对一个变量集（“视点”）执行搜索，因为其他变量的值由通道约束隐含。

在两个表示之间进行引导的一些常见示例是：

整数变量和布尔的阵列：考虑一个整数变量T指示该时隙1..N当一个事件发生时，和布尔值的阵列Bs[N]，使得Bs[T] = 1当且仅当一个事件发生在时隙T。在ECLiPSe中：

    T #:: 1..N,
    dim(Bs, [N]), Bs #:: 0..1,

然后可以在两个表示之间建立通道

    ( for(I,1,N), param(T,Bs) do Bs[I] #= (T#=I) )

它将在T和之间双向传播信息Bs。实现此通道的另一种方法是专用的bool_channeling / 3约束。

开始/结束整数变量和布尔数组（时间表）：我们有整数变量，S,E指示活动的开始和结束时间。在另一侧上的布尔值的阵列Bs[N]，使得Bs[T] = 1当且仅当在活动时间发生T。在ECLiPSe中：

    [S,E] #:: 1..N,
    dim(Bs, [N]), Bs #:: 0..1,

可以通过以下途径实现

    ( for(I,1,N), param(S,E,Bs) do Bs[I] #= (S#=<I and I#=<E) ).

对偶表示Job / Machine整数变量：在这里，Js[J] = M表示作业J是在机器上执行的M，而对偶Ms[M] = J表示则表示机器M在作业上执行J

    dim(Js, [NJobs]), Js #:: 0..NMach,
    dim(Ms, [NMach]), Ms #:: 1..NJobs,

并通过

    ( multifor([J,M],1,[NJobs,NMach]), param(Js,Ms) do
        (Js[J] #= M) #= (Ms[M] #= J)
    ).

设置变量和布尔数组：如果您使用求解器（例如 Boolean可以直接处理set变量 library（ic_sets）），则可以将它们反映到一个布尔数组中，以指示集合中元素的成员身份。为此，该库提供了专用的约束Membership_booleans / 2。

Answer 2

如二进制约束满足问题的双重观点启发式算法（PA Geelen）中所述：

两种不同模型的通道约束允许表达两组变量之间的关系，每种变量之一。

这意味着可以将其中一个视点中的分配转换为另一个视点中的分配，反之亦然，并且，当搜索启动时，也可以从一个模型中排除一个模型中的排除值。

让我举一个我在编写数独求解器时实现的示例。

经典观点

在这里，我们以与人类相同的方式解释问题：使用1到9之间的整数以及所有行，列和块必须包含每个整数恰好一次的定义。

我们可以使用类似以下的内容在ECLiPSe中轻松声明：

% Domain
dim(Sudoku,[N,N]),
Sudoku[1..N,1..N] :: 1..N

% For X = rows, cols, blocks
alldifferent(X)

这就足以解决数独难题。

二进制布尔观点

但是，可以选择用其二进制布尔数组表示整数（在@jschimpf 的答案中显示）。如果不清楚这是做什么的，请考虑下面的小示例（这是内置功能！）：

?­ ic_global:bool_channeling(Digit, [0,0,0,1,0], 1).
    Digit = 4
    Yes (0.00s cpu)
?­ ic_global:bool_channeling(Digit, [A,B,C,D], 1), C = 1.
    Digit = 3
    A = 0
    B = 0
    C = 1
    D = 0
    Yes (0.00s cpu)

如果使用此模型表示Sudoku，则每个数字都将替换为其二进制布尔数组，并且可以编写相应的约束。对于这个答案而言，这是微不足道的，我将不包括约束的所有代码，但是单个和约束仍然足以解决其二进制布尔表示形式中的Sudoku难题。

引导

现在，将这两种观点与相应的受约束模型一起使用，就有机会在它们之间进行引导，并查看是否进行了任何改进。

由于两个模型仍然只是NxN板，因此在表示尺寸上不存在差异，并且通道变得非常容易。

让我首先给您最后一个示例，说明在两个模型中填充有整数1..9的块的样子：

% Classic viewpoint
1 2 3
4 5 6
7 8 9

% Binary Boolean Viewpoint
[](1,0,0,0,0,0,0,0,0)  [](0,1,0,0,0,0,0,0,0)  [](0,0,1,0,0,0,0,0,0) 
[](0,0,0,1,0,0,0,0,0)  [](0,0,0,0,1,0,0,0,0)  [](0,0,0,0,0,1,0,0,0) 
[](0,0,0,0,0,0,1,0,0)  [](0,0,0,0,0,0,0,1,0)  [](0,0,0,0,0,0,0,0,1)

现在，我们清楚地看到了模型之间的链接，只需编写代码以传递我们的决策变量。使用Sudoku和BinBools作为我们的开发板，代码将类似于：

( multifor([Row,Col],1,N), param(Sudoku,BinBools,N) 
do
  Value is Sudoku[Row,Col], 
  ValueBools is BinBools[Row,Col,1..N], 
  ic_global:bool_channeling(Value,ValueBools,1) 
).

至此，我们有了一个渠道模型，在搜索过程中，如果其中一个模型中的值被修剪，则其影响也会在另一个模型中发生。这样当然可以导致进一步的整体约束传播。

推理

为了解释二元布尔模型对Sudoku难题的有用性，我们必须首先区分alldifferent/1ECLiPSe 提供的一些实现：

在实践中，这意味着什么：

?­ [A, B, C] :: [0..1], ic:alldifferent([A, B, C]). 
  A = A{[0, 1]} 
  B = B{[0, 1]} 
  C = C{[0, 1]} 
  There are 3 delayed goals. 
  Yes (0.00s cpu) 

?­ [A, B, C] :: [0..1], ic_global:alldifferent([A, B, C]). 
  No (0.00s cpu)

由于尚未使用前向检查（ic库）进行任何分配，因此尚未检测到查询的无效性，而“边界一致”版本会立即注意到这一点。在通过高度约束的模型进行搜索和回溯时，此行为可能导致约束传播方面的显着差异。

在这两个库的顶部，是ic_global_gac库，该库用于维护全局弧约束（也称为超弧约束或域一致性）的全局约束。这个alldifferent / 1约束比一致的边界约束提供了更多的修剪机会，但是保留完整的域一致性具有代价，并且在高度约束的模型中使用此库通常会导致运行性能下降。

因此，我发现数独谜题尝试使用alldifferent的边界一致（ic_global）实现以最大程度地提高性能，然后尝试通过引入二进制布尔模型来实现域一致性，这很有趣。

实验结果

下面是为“platinumblonde”独难题回溯结果（引用为是最硬的，最混乱Sudoku难题在解决混沌在独，M. ErcseyRavasz和Z. Toroczkai）分别使用前向检查，界定一致性，一致性域，独立的二进制布尔模型，最后是通道模型：

      (ic)   (ic_global)  (ic_global_gac)  (bin_bools)  (channelled)
BT    6 582      43             29             143           30

如我们所见，我们的通道模型（使用边界一致性（ic_global））比域一致性实现还需要一个回溯，但是它的性能肯定比独立的边界一致性版本更好。

现在我们来看一下运行时间（结果是在多次执行中计算平均值的结果，这是避免极端情况的结果），排除了前向检查实现，因为事实证明，对于解决Sudoku难题不再感兴趣：

          (ic_global)  (ic_global_gac)  (bin_bools)  (channelled)
Time(ms)     180ms          510ms           100ms        220ms

查看这些结果，我认为我们可以成功完成实验（这些结果已被20多个Sudoku拼图实例所证实）：

将二进制布尔值视点引导到边界一致的独立实现中产生的约束传播行为比域一致的独立实现中产生的约束传播行为稍微强一些，但是运行时间从长到明显更快。

编辑：尝试澄清

想象一些域变量，它代表Sudoku板上的一个单元，其剩余域为4..9。使用边界一致性，可以保证对于值4和9都可以找到满足所有约束并因此提供一致性的其他域值。但是，没有明确保证域中其他值的一致性（这就是“域一致性”）。

使用二进制布尔模型，我们定义以下两个总和约束：

• 每个二进制布尔数组的总和始终等于1
• 每个行/列/块中每个数组的第N个元素的总和始终等于1

额外的约束强度由第二个约束强制执行，第二个约束除了约束行，列和块外，还隐含地说：“每个单元只能包含每个数字一次”。仅使用边界一致的alldifferent / 1约束时，不会主动表达此行为！

结论

显然，通道化对于改进独立约束模型非常有用，但是，如果新模型的约束强度比当前模型的约束强度弱，则显然不会进行任何改进。还要注意，拥有更多约束模型并不一定意味着整体上会有更好的性能！实际上，添加更多的约束将减少解决问题所需的回溯量，但是如果必须进行更多的约束检查，这也可能会增加程序的运行时间。