并行传播是并行约束程序领域中的一个研究方向,其研究内容是如何并行执行在约束上的过滤算法.根据维持表约束网络广义弧相容(generalized arc consistency,简称GAC)的串行传播模式,提出了维持表约束网络临时广义弧相容(temporary generalized arc consistency,简称TGAC)的并行传播模式,该模式基于多核CPU,由并行传播算法和并行过滤算法两部分组成;之后,给出了并行传播模式的可靠性证明,而且通过对并行传播模式的最坏时间复杂度分析,可以认为并行传播模式在平均过滤时间较长的实例上要快于串行传播模式;最终的实验结果也验证了上述结论,并行传播模式在多数实例集上取得了从1.4~3.4不等的加速比.
Parallel propagation is a research direction in the field of parallel constraint programming, and its research content is how to implement filtering algorithms on constraints in parallel. According to the serial propagation mode which enforces generalized arc consistency (GAC) on table constraint network, this study proposes a parallel propagation mode to enforce temporary generalized arc consistency (TGAC) on table constraint network. This mode is based on multi-core CPU and consists of parallel propagation algorithm and parallel filtering algorithm. After that, the reliability of the parallel propagation mode is proved, and through the analysis of the worst case time complexity of the parallel propagation mode, it is also demonstrated that the parallel propagation mode is faster than the serial propagation mode in instances of which the average filtering time is longer. Finally, the experimental results also confirm the above conclusion, and the parallel propagation mode achieves a speed-up ratio ranging from 1.4 to 3.4 on most series.
约束程序(constraint programming, 简称CP)是一种求解组合优化问题的有效方法, 在人工智能、运筹学、图论等诸多领域都有广泛的应用.并行计算是在不改变预期结果的情况下, 同时对问题的多个部分进行处理的能力.随着计算机并行处理能力的发展, 约束程序与并行计算的结合研究已成为被关注的领域, 即并行约束程序.
针对并行约束程序的研究大致可分为以下几类: 并行传播、搜索空间分割、组合算法和问题分解等[
由于缺少相应的表约束并行过滤算法, Rolf等人提出的传播模型不能直接应用在对表约束的并行传播上.根据我们掌握的资料, 目前还没有针对表约束并行传播的研究成果被公布.表约束是约束程序中最常用的约束类型之一, 也被称为外延约束, 每个约束在包含的变量集上显式地列举出所有支持或禁止的取值组合.表约束理论上可以编码任何类型的约束, 在许多应用程序领域中, 当对组合问题进行建模时, 常常需要使用它们.
维持表约束网络广义弧相容(generalized arc consistency, 简称GAC)的串行传播模式由串行传播算法和串行过滤算法两部分组成, 串行传播算法串行执行维持表约束GAC的串行过滤算法.过去的十多年中, 维持表约束GAC的串行过滤算法研究已经公布了大量的成果, 其中具有代表性的系列成果是基于简单表缩减的串行过滤算法(若无特殊说明, 后文的过滤算法均指基于简单表缩减的过滤算法).比如: STR(simple tabular reduction)[
根据维持表约束网络GAC的串行传播模式, 我们提出了维持表约束网络临时广义弧相容(temporary generalized arc consistency, 简称TGAC)的并行传播模式.该模式基于多核CPU, 由并行传播算法和并行过滤算法两部分组成, 并行传播算法利用线程池并行执行维持表约束TGAC的并行过滤算法.之后, 我们给出了并行传播模式的可靠性证明, 即并行传播模式也维持表约束网络GAC.接下来, 我们分析了并行传播模式的最坏时间复杂度, 并将其与串行传播模式的最坏时间复杂度进行对比; 经过分析对比, 我们认为, 并行传播模式在平均过滤时间较长的实例上要快于串行传播模式.最终的实验结果也验证了上述结论, 而且并行传播模式在多数实例集上取得了从1.4~3.4不等的加速比.
本文第1节介绍相关的背景知识.第2节回顾维持表约束网络GAC的串行传播模式.第3节给出维持表约束网络TGAC的并行传播模式.第4节展示实验结果.第5节做出工作总结和未来展望.
一个约束网络
例1:变量
● 取值(
● 约束
● 约束网络
为了降低并行传播过程中不同线程同时访问同一变量论域的频率, Rolf等人[
接下来, 我们给出临时广义弧相容的定义和性质.
● 取值(
● 约束
● 约束网络
证明: 因为取值(
证明: 因为约束
证明: 因为约束网络
线程池是一种多线程处理形式, 管理一组线程, 以便并行处理大量任务.在需要多次使用线程的并行程序中, 单独创建与销毁线程会增加运行开销, 从而影响程序的整体性能.而线程池通过限制线程的数量和重用线程, 能够避免创建与销毁线程的代价, 还可以提高程序的稳定性.
本文使用的是工作窃取线程池, 其中每个线程都有一个独立的任务队列, 主线程将任务分配到各个线程的任务队列中.工作窃取是指如果某个线程完成了其队列中的所有任务, 而其他线程的队列中还有未处理任务, 那么空闲线程可以窃取其他线程的未处理任务, 从而改善了并行程序的负载均衡.
位向量是由若干个位(bit)组成的向量, 具有存储空间占用少和处理速度快的特点.在构建一个CP求解器时, 位向量是变量论域的重要表示方式之一[
为了便于说明位向量的数据结构及其操作, 我们用
本文共涉及以下6种有关位向量的基本操作.
(1) 位赋值操作: 将位向量的某个位赋值为0b或1b, 如
(2) 位判等操作: 判断位向量的某个位是否为0b或1b, 如
(3) 位向量赋值操作: 对位向量的整体进行赋值, 如
(4) 位向量判等操作: 判断位向量的整体取值, 如
(5) 位向量按位或操作: 将两个位向量的对应位进行或运算, 如
(6) 位向量按位与操作: 将两个位向量的对应位进行与运算, 如
例2:位向量
位向量及其操作
Bit vectors and their operations
在本文的相关算法中, 我们用位向量
维持表约束网络GAC的串行传播模式由串行传播算法和串行过滤算法两部分组成, 本节将依次介绍这两部分算法, 并分析串行传播模式的相关性质.
求解CSP实例的常用方法是回溯搜索, 回溯搜索是一种完整方法, 它通过系统地探索实例的搜索空间, 可找到全部的解或者证明无解存在.MAC(maintaining arc consistency)算法[
常用的串行传播算法之一是面向变量的串行传播算法[
1
2
3
4
5
6 pick and delete
7
8
9
10
11
12
13
14
15
1
2
3
在算法1中,
算法1的传入参数
如前文所述, 维持表约束GAC的串行过滤算法研究已经公布了大量成果, 它们的设计实现虽然有所不同, 但主要由更新表(算法4)和过滤论域(算法5)两部分组成.我们总结了它们的共同之处, 具体见算法3~算法5.
1
2
1
2
3
4
5
1
2
3
4
5
6
7
8
9
10
11
算法3中, 串行过滤算法首先更新表, 即移除无效的元组(算法4第4行); 进而过滤论域, 即删除在该约束上不存在支持的值(算法5第5行); 最后返回由被删值的变量所组成的集合.如果有一个变量
因为不同的串行过滤算法有不同的最坏时间复杂度, 所以它们的最坏时间复杂度被统一设为
证明: 串行传播算法中, 初始化变量集合
在本节中, 我们提出了维持表约束网络TGAC的并行传播模式, 它同样由并行传播算法和并行过滤算法两部分组成.之后, 我们分析了并行传播模式的相关性质.
在并行传播模式中, 我们引入了一些新的数据结构.
● 约束位标识
● 位订阅
通过
例3:约束网络
位订阅及其提交操作
Bit subscriptions and their submission operations
如前文所述, 串行传播算法根据变量传播集合顺次执行对相关约束的过滤任务(算法1第7行、第8行), 我们将这一操作并行化, 提出了并行传播算法.并行传播算法使用约束位标识
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
算法6的传入参数
我们对维持表约束GAC的串行过滤算法进行扩展, 得到了维持表约束TGAC的并行过滤算法(算法7), 如PSTR2, PSTR3, PSTRbit和PCT, 并进行了一般化总结, 它们同样主要由更新表(算法8)和过滤论域(算法9)两部分组成.
1
2
3
4
5
6
1
2
3
4
5
1
2
3
4
5
6
7
8
9
10
11
与算法3不同的是, 算法7首先判断不相容标识
多个线程在并行执行对不同表约束的并行过滤算法时, 可能会同时过滤同一个变量
例4:表约束
并行过滤算法执行实例
Parallel filtering algorithm execution instance
首先, 我们给出并行传播模式的可靠性证明.
证明: 一方面, 如果取值(
另一方面, 如果取值(
综上所述, 维持表约束网络TGAC的并行传播模式也维持表约束网络GAC.证毕.
接下来, 我们对并行传播模式的最坏时间复杂度进行分析.通过对比串行过滤算法, 因为并行过滤算法中所增加的操作语句均有着
证明: 并行传播算法中初始化约束位标识
当并行度
p依次被置为2, 4和6.MAC算法采用
不同实例集的平均实验结果(CT和PCT)
Average results to solve instances from different series (CT and PCT)
Series | # | Serial (CT) | Parallel (PCT) | ||||||||||
Time | Filt | Avg. | Time | Filt | Speed | Time | Filt | Speed | Time | Filt | Speed | ||
rand-3-20-fcd | 50 | 14.06 | 121.86 | 1.15 | 10.39 | 171.78 | 1.35 | |
176.26 | 1.46 | 12.03 | 176.77 | 1.17 |
rand-3-20 | 50 | 29.58 | 244.96 | 1.21 | 21.50 | 344.79 | 1.38 | |
353.97 | 1.52 | 24.09 | 355.33 | 1.23 |
rand-5-12 | 50 | 0.85 | 2.41 | 3.52 | 0.43 | 3.33 | 1.98 | 0.27 | 3.38 | 3.15 | |
3.41 | 3.40 |
rand-8-20 | 20 | 4.67 | 30.34 | 1.54 | |
42.37 | 1.14 | 4.50 | 43.38 | 1.04 | 6.03 | 43.04 | 0.77 |
rand-10-60 | 32 | 9.10 | 4.89 | 18.60 | 5.40 | 7.10 | 1.69 | |
7.59 | 2.46 | 3.84 | 8.03 | 2.37 |
half | 19 | 95.64 | 605.16 | 1.58 | 65.93 | 833.86 | 1.45 | |
845.03 | 1.74 | 67.60 | 849.79 | 1.41 |
MDD0.7 | 8 | 31.22 | 139.41 | 2.24 | 20.27 | 194.18 | 1.54 | |
197.26 | 2.01 | 17.75 | 198.91 | 1.76 |
MDD0.9 | 9 | 1.47 | 7.91 | 1.86 | 1.01 | 11.08 | 1.46 | |
11.26 | 1.84 | 0.94 | 11.34 | 1.56 |
bddSmall | 35 | 2.66 | 10.29 | 2.58 | 1.55 | 15.20 | 1.72 | 0.95 | 15.26 | 2.80 | |
15.31 | 2.96 |
uk | 42 | 10.35 | 8.56 | 12.09 | 5.53 | 11.35 | 1.87 | |
11.56 | 2.58 | 4.07 | 11.77 | 2.54 |
ogd | 43 | 5.80 | 2.25 | 25.83 | 3.28 | 3.07 | 1.77 | 2.18 | 3.13 | 2.66 | |
3.20 | 2.67 |
lex | 62 | 1.56 | 4.03 | 3.87 | 1.03 | 5.63 | 1.51 | |
5.81 | 1.54 | 1.32 | 5.96 | 1.18 |
words | 65 | 4.44 | 10.36 | 4.29 | 2.93 | 14.48 | 1.52 | |
14.91 | 1.54 | 3.56 | 15.38 | 1.25 |
tsp-20 | 15 | 2.49 | 35.92 | 0.69 | 2.17 | 46.19 | 1.15 | |
46.53 | 1.20 | 2.63 | 46.45 | 0.95 |
tsp-25 | 15 | 44.08 | 649.17 | 0.68 | 37.34 | 819.74 | 1.18 | |
824.59 | 1.31 | 41.29 | 823.70 | 1.07 |
jnhSat | 16 | 0.53 | 8.70 | 0.61 | 0.35 | 10.92 | 1.51 | |
10.88 | 1.89 | 0.31 | 10.92 | 1.71 |
jnhUnsat | 34 | 0.21 | 3.39 | 0.62 | 0.14 | 4.27 | 1.50 | |
4.24 | 1.91 | 0.12 | 4.26 | 1.75 |
modR | 25 | |
75.80 | 0.85 | 8.18 | 102.57 | 0.79 | 12.14 | 104.88 | 0.53 | 15.95 | 104.03 | 0.41 |
aim-50 | 24 | |
0.73 | 0.41 | 0.08 | 0.95 | 0.38 | 0.14 | 0.95 | 0.21 | 0.17 | 0.94 | 0.18 |
aim-100 | 16 | |
4.44 | 0.34 | 0.34 | 5.83 | 0.44 | 0.61 | 5.81 | 0.25 | 0.83 | 5.81 | 0.18 |
aim-200 | 8 | |
355.72 | 0.44 | 16.22 | 465.04 | 0.96 | 19.58 | 465.14 | 0.79 | 27.32 | 465.69 | 0.57 |
dubois | 3 | |
591.96 | 0.38 | 112.77 | 1 007.99 | 0.20 | 275.14 | 1 008.04 | 0.08 | 310.58 | 1 010.59 | 0.07 |
不同实例集的平均实验结果(STRbit和PSTRbit)
Average results to solve instances from different series (STRbit and PSTRbit)
Series | # | Serial (STRbit) | Parallel (PSTRbit) | ||||||||||
Time | Filt | Avg. | Time | Filt | Speed | Time | Filt | Speed | Time | Filt | Speed | ||
rand-3-20-fcd | 50 | 17.57 | 121.86 | 1.44 | 13.79 | 171.90 | 1.27 | |
176.44 | 1.51 | 14.23 | 177.60 | 1.23 |
rand-3-20 | 50 | 36.96 | 244.96 | 1.51 | 26.90 | 345.07 | 1.37 | |
354.55 | 1.63 | 27.70 | 356.85 | 1.33 |
rand-5-12 | 50 | 1.98 | 2.41 | 8.21 | 1.18 | 3.33 | 1.68 | 0.86 | 3.38 | 2.30 | |
3.41 | 2.47 |
rand-8-20 | 20 | 19.30 | 30.34 | 6.36 | 15.08 | 42.67 | 1.28 | |
44.31 | 1.50 | 14.62 | 44.85 | 1.32 |
rand-10-60 | 32 | 58.77 | 4.89 | 120.14 | 32.31 | 7.24 | 1.82 | 28.89 | 8.01 | 2.03 | |
8.65 | 2.07 |
half | 19 | 240.38 | 605.16 | 3.97 | 181.89 | 836.02 | 1.32 | |
852.54 | 1.95 | 133.33 | 864.64 | 1.80 |
MDD0.7 | 8 | 94.14 | 139.41 | 6.75 | 57.99 | 194.72 | 1.62 | 39.71 | 199.09 | 2.37 | |
202.30 | 2.43 |
MDD0.9 | 9 | 8.14 | 7.91 | 10.29 | 4.79 | 11.11 | 1.70 | 3.05 | 11.35 | 2.67 | |
11.53 | 2.98 |
bddSmall | 35 | 8.69 | 10.29 | 8.44 | 6.15 | 15.21 | 1.41 | 4.18 | 15.28 | 2.08 | |
15.34 | 2.27 |
uk | 42 | 15.21 | 8.56 | 17.77 | 10.09 | 11.34 | 1.51 | 7.24 | 11.59 | 2.10 | |
11.85 | 2.12 |
ogd | 43 | 6.79 | 2.24 | 30.25 | 4.80 | 3.08 | 1.41 | 3.54 | 3.17 | 1.92 | |
3.27 | 2.11 |
lex | 62 | 1.69 | 4.03 | 4.20 | 1.35 | 5.62 | 1.25 | |
5.76 | 1.40 | 1.49 | 5.92 | 1.13 |
words | 65 | 5.06 | 10.36 | 4.88 | 3.85 | 14.44 | 1.31 | |
14.80 | 1.53 | 4.16 | 15.30 | 1.22 |
tsp-20 | 15 | 3.26 | 35.92 | 0.91 | 2.74 | 46.24 | 1.19 | |
46.58 | 1.29 | 3.21 | 46.57 | 1.02 |
tsp-25 | 15 | 52.22 | 649.16 | 0.80 | 47.99 | 820.89 | 1.09 | |
825.40 | 1.29 | 47.91 | 824.96 | 1.09 |
jnhSat | 16 | 0.50 | 8.69 | 0.58 | 0.42 | 10.92 | 1.19 | |
10.88 | 1.61 | 0.36 | 10.91 | 1.39 |
jnhUnsat | 34 | 0.23 | 3.38 | 0.68 | 0.21 | 4.28 | 1.10 | |
4.26 | 1.53 | |
4.27 | 1.53 |
modR | 25 | |
75.80 | 1.06 | 9.81 | 101.58 | 0.82 | 13.56 | 104.95 | 0.59 | 17.48 | 104.58 | 0.46 |
aim-50 | 24 | |
0.73 | 0.27 | 0.08 | 0.95 | 0.25 | 0.14 | 0.95 | 0.14 | 0.18 | 0.95 | 0.11 |
aim-100 | 16 | |
4.44 | 0.34 | 0.39 | 5.83 | 0.38 | 0.69 | 5.81 | 0.22 | 0.92 | 5.82 | 0.16 |
aim-200 | 8 | |
355.71 | 0.35 | 18.66 | 465.44 | 0.67 | 20.77 | 465.68 | 0.61 | 28.77 | 465.94 | 0.44 |
dubois | 3 | |
591.96 | 0.34 | 138.03 | 1 008.12 | 0.15 | 286.92 | 1 008.00 | 0.07 | 330.55 | 1 008.59 | 0.06 |
首先, 我们比较一下串行传播模式和并行传播模式的实验结果.在17组实例集上, 并行传播模式要快于串行传播模式, 而且在多数实例集上取得了从1.4~3.4不等的加速比; 在另外5组实例集上, 并行传播模式的表现不如串行传播模式.从各实例集在串行传播模式下的平均过滤时间avg可以看出: 取得较好加速比的实例集, 其avg普遍较大, 如rand-10-60, ogd, uk和MDD0.9等; 并行传播效果不好的实例集, 其avg普遍较小, 如aim-50, aim-100和dubois等.这与第3.3节性质6的分析相一致.因此, 我们提出的并行传播模式适用于平均过滤时间avg较大的实例.
并行传播模式在多数实例集上取得了较好的加速比, 但是没有实现线性加速(加速比与并行度相等), 原因主要有两点.
● 在求解实例的过程中, 并行过滤算法被调用的平均次数filt多于串行过滤算法被调用的平均次数filt.
虽然并行传播模式有多个线程并行执行过滤算法, 但其工作总量并不与串行传播模式的工作总量相等, 而是随着线程的增多而增加.这是因为在并行传播模式下, 线程之间不能相互通信.对表约束
例5:现有两个表约束
串行传播模式与并行传播模式的对比实例
An example of serial propagation mode versus parallel propagation mode
● 并行传播进程中线程利用率并不总是100%.
线程利用率是活跃线程数与并行度的比率, 活跃线程是指正在运行任务的线程.我们在求解一个实例的并行传播(并行度
并行传播进程中的活跃线程数
Number of active threads in a parallel propagation process
最后, 我们对比一下并行传播模式在不同并行度
在本文中, 首先, 我们提出了维持表约束网络TGAC的并行传播模式, 该模式基于多核CPU, 由并行传播算法和并行过滤算法两部分组成, 并行传播算法利用线程池并行执行维持表约束TGAC的并行过滤算法; 之后, 我们给出了并行传播模式的可靠性证明, 即并行传播模式也维持表约束网络GAC; 另外, 通过对并行传播模式的最坏时间复杂度分析, 我们认为并行传播模式在平均过滤时间较长的实例上要快于串行传播模式, 最终的实验结果也验证了这一结论.
基于本文的思路, 我们认为未来的研究可从以下3个方面继续开展.
1) 我们在实验分析中给出了两点关于并行传播模式没有实现线性加速的原因, 因此未来的研究可尝试通过减少并行传播模式的工作总量或提高线程利用率, 来进一步提升并行传播的效率;
2) 维持表约束GAC的串行过滤算法研究除了基于简单表缩减, 还有很多基于其他设计思想的成果, 比如泛型过滤算法系列(GAC2001[
3) 在相容性理论方面, 删值能力强于GAC的相容性被称为高阶相容性, 如最大限制成对相容性(max restricted pairwise consistency, 简称maxRPWC)和成对相容性(pairwise consistency, 简称PWC).维持表约束网络高阶相容性的串行传播模式设计受到了很多研究工作的关注[
Hamadi Y, Sais L. Parallel Constraint Programming. Handbook of Parallel Constraint Reasoning, Chapter 9. Springer-Verlag, 2018. 337-379.
Kasif S. On the parallel complexity of discrete relaxation in constraint satisfaction networks. Artificial Intelligence, 1990, 45(3): 275-286.
Rolf CC, Kuchcinski K. Parallel consistency in constraint programming. In: Proc. of the 2009 Int'l Conf. on Parallel and Distributed Processing Techniques and Applications (PDPTA 2009). 2009. 638-644.
Li Z, Li ZS, Li Y. A constraint network model and parallel arc consistency algorithms based on GPU. Ji Suan Ji Yan Jiu Yu Fa Zhan/Journal of Computer Research and Development, 2017, 54(3): 514-528(in Chinese with English abstract).
李哲, 李占山, 李颖. 基于GPU的约束网络模型和并行弧相容算法. 计算机研究与发展, 2017, 54(3): 514-528.
Ullmann JR. Partition search for non-binary constraint satisfaction. Information Sciences, 2007, 177(18): 3639-3678.
Lecoutre C. STR2: Optimized simple tabular reduction for table constraints. Constraints, 2011, 16(4): 341-371.
Lecoutre C, Likitvivatanavong C, Yap RHC. STR3: A path-optimal filtering algorithm for table constraints. Artificial Intelligence, 2015, 220: 1-27.
Wang R, Xia W, Yap RHC,
Demeulenaere J, Hartert R, Lecoutre C,
Li HB, Liang YC, Li ZS. Simple tabular reduction for generalized arc consistency on negative table constraints. Ruan Jian Xue Bao/Journal of Software, 2016, 27(11): 2701-2711(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4874.htm[doi:10.13328/j.cnki.jos.004874]
李宏博, 梁艳春, 李占山. 负表约束的简单表缩减广泛弧相容算法. 软件学报, 2016, 27(11): 2701-2711. http://www.jos.org.cn/1000-9825/4874.htm[doi:10.13328/j.cnki.jos.004874]
Yang MQ, Li ZS, Li Z. Optimizing MDDc and STR3 for solving constraint satisfaction problem. Ruan Jian Xue Bao/Journal of Software, 2017, 28(12): 3156-3166(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5242.htm[doi:10.13328/j.cnki.jos.005242]
杨明奇, 李占山, 李哲. 优化求解约束满足问题的MDDc和STR3算法. 软件学报, 2017, 28(12): 3156-3166. http://www.jos.org.cn/1000-9825/5242.htm[doi:10.13328/j.cnki.jos.005242]
Yang MQ, Li ZS, Zhang JC. Time-stamp based simple tabular reduction algorithm. Ruan Jian Xue Bao/Journal of Software, 2019, 30(11): 3355-3363(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5559.htm[doi:10.13328/j.cnki.jos.005559]
杨明奇, 李占山, 张家晨. 一种基于时间戳的简单表缩减弧相容算法. 软件学报, 2019, 30(11): 3355-3363. http://www.jos.org.cn/1000-9825/5559.htm[doi:10.13328/j.cnki.jos.005559]
Schulte C, Carlsson M. Finite Domain Constraint Programming Systems. Handbook of Constraint Programming, Chapter 14. Elsevier, 2006. 493-524.
Sabin D, Freuder EC. Contradicting conventional wisdom in constraint satisfaction. In: Proc. of the Int'l Workshop on Principles and Practice of Constraint Programming. Berlin, Heidelberg: Springer-Verlag, 1994. 10-20.
Mcgregor JJ. Relational consistency algorithms and their application in finding subgraph and graph isomorphisms. Information Sciences, 1979, 19(3): 229-250.
Li Z, Yang M, Li Z. A new variable-oriented propagation scheme for constraint satisfaction problem. In: Proc. of the Int'l Conf. on Knowledge Science, Engineering and Management. Cham: Springer-Verlag, 2018. 59-68.
Lecoutre C. Generic GAC Algorithms. Constraint Networks: Techniques and Algorithms, Chapter 4. John Wiley & Sons, 2010. 185-237.
Bessière C, Régin JC, Yap RHC,
Lecoutre C, Hemery F. A study of residual supports in arc consistency. In: Proc. of the Int'l Joint Conf. on Artificial Intelligence, Vol. 7. AAAI, 2007. 125-130.
Perez G, Régin JC. Improving GAC-4 for table and MDD constraints. In: Proc. of the Int'l Conf. on Principles and Practice of Constraint Programming. Cham: Springer-Verlag, 2014. 606-621.
Cheng KCK, Yap RHC. An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints. Constraints, 2010, 15(2): 265-304.
Paparrizou A, Stergiou K. An efficient higher-order consistency algorithm for table constraints. In: Proc. of the 26th AAAI Conf. on Artificial Intelligence. 2012.
Lecoutre C, Paparrizou A, Stergiou K. Extending STR to a higher-order consistency. In: Proc. of the 27th AAAI Conf. on Artificial Intelligence. 2013.
Schneider A, Choueiry BY. PW-CT: Extending compact-table to enforce pairwise consistency on table constraints. In: Proc. of the Int'l Conf. on Principles and Practice of Constraint Programming. Cham: Springer-Verlag, 2018. 345-361.