Abstract:

Variable ordering heuristic is a key technique of constraint programming to solve constraint satisfaction problem, which has an important influence on solving efficiency. In order to further improve the efficiency and ability of CRBS to solve the problem, a correlation heuristic based on ParetoHeu and the instantiation failure statistics, PICRBS, is proposed. PICRBS adopts ParetoHeu, the Pareto optimal heuristic combination method, combines CRBS with the classic general heuristic dom/wdeg, and uses the weight statistics method based on the number of instantiation failures to select the variables most likely to cause search backtracking for the solution of the problem. Experimental results show that the proposed method is more efficient than CRBS and popular variable ordering heuristic in solving multiple problems.

Key words: constraint programming, variable ordering heuristics, Pareto optimality, correlation heuristics, constraint satisfaction problem

摘要：

变量排序启发式是约束规划求解约束满足问题中的一项关键技术，对求解效率有着重要影响。为进一步提高基于关联的变量排序启发式方法CRBS对问题求解的效率和能力，提出了一种基于ParetoHeu和实例化失败统计的关联启发式PICRBS。PICRBS采用源于帕累托最优的启发式组合方式ParetoHeu，将CRBS与经典的通用启发式dom/wdeg进行结合，同时加入基于实例化失败次数的权值统计方法，为问题求解选择最有可能导致搜索发生回溯的变量。实验结果显示，针对多个问题实例，该方法在问题求解效率上高于CRBS和主流变量排序启发式。

关键词: 约束规划, 变量排序启发式, 帕累托最优, 关联启发式, 约束满足问题