一种高效的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等价于在原问题...

Efficient Parallel Propagation Algorithm for 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. Factor-decomposition 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.