一种高效的FDE并行传播算法

Efficient Parallel Propagation Algorithm for FDE

约束规划(constraint programming, CP)是表示和求解组合问题的经典范式之一.扩展约束(extensional constraint)或称表约束(table constraint)是约束规划中最为常见的约束类型.绝大多数约束规划问题都可以用表约束表达.在问题求解时,相容性算法用于缩减搜索空间.目前,最为高效的表约束相容性算法是简单表约缩减(simple table reduction, STR)算法簇,如Compact-Table (CT)和STRbit算法.它们在搜索过程中维持广义弧相容(generalized arc consistency, GAC).此外,完全成对相容性(full pairwise consistency, fPWC)是一种比GAC剪枝能力更强的相容性.最为高效的维持fPWC算法是PW-CT算法.多年来,人们提出了多种表约束相容性算法来提高剪枝能力和执行效率.因子分解编码(factor-decomposition encoding, FDE)通过对平凡问题重新编码.它一定程度地扩大了问题模型,使在新的问题上维持相对较弱的GAC等价于在原问题上维持fPWC.目前, FDE的合适STR算法是STRFDE和STR2,而不是CT.这是由于CT算法可能产生内存溢出问题.在维持相容性算法的过程中,需要将迭代地调用各个约束执行其相容性算法过滤搜索空间,这个过程称为约束传播.动态提交方案是一个并行约束传播框架,可以并行地调度约束执行传播算法.它在大规模问题中,改进效果尤为明显.改进STRFDE和动态提交传播算法.针对FDE提出了PSTRFDE算法. PSTRFDE可以嵌入到动态提交方案中,进一步提高了约束规划问题的求解效率.大量的实验表明, PSTRFDE与CT和STRbit相比,可以减少内存占用;与STRFDE和STR2相比,可以提高算法的效率.所作工作充分说明了PSTRFDE是FDE上最为高效的过滤算法.

Constraint programming(CP)is one of the classical paradigms for representing and solving combinatorial problems.Extensional constraints,also called table constraints,are the most common type of constraints in CP,and most CP problems can be expressed by table constraints.In the problem-solving process,consistency algorithms are used to reduce the search space,and the simple table reduction(STR)algorithms are the most efficient consistency algorithms with table constraints,including Compact-Table(CT)and STRbit algorithms,both of which maintain the generalized arc consistency(GAC)during the search.In addition,the full pairwise consistency(fPWC)is stronger than GAC in the pruning capability,and the most efficient fPWC maintenance algorithm is the PW-CT algorithm.Over the years,many consistency algorithms with table constraints are proposed to improve the pruning capability and efficiency.Factordecomposition encoding(FDE)recodes trivial problems,which enlarges the scale of the problem model to some extent,and as a result,maintaining a relatively weak GAC on a new model is equivalent to maintaining a strong fPWC on the original model.Currently,the appropriate STR algorithms for FDE are STRFDE and STR2 rather than CT as the CT algorithm may produce memory overflow.In the process of maintaining the consistency algorithm,it is necessary to call each constraint iteratively to perform its consistency algorithm to filter the search space.This process is called constraint propagation.The dynamic submission scheme is a parallel constraint propagation scheme,which can schedule constraint execution propagation algorithms in parallel,and it is particularly effective in large-scale problems.Therefore,this study proposes PSTRFDE for FDE by improving STRFDE and dynamic submission propagation algorithms.PSTRFDE can be embedded into the dynamic submission scheme to further improve the efficiency of constraint problem solving.Extensive experiments indicate that PSTRFDE can reduce the used memory compared with CT and STRbit,and compared with the results of STRFDE and STR2,the efficiency of PSTRFDE can be further improved.The research demonstrates that PSTRFDE is the most efficient filtering algorithm for FDE at present.