Computer Engineering and Applications ›› 2020, Vol. 56 ›› Issue (5): 57-64.DOI: 10.3778/j.issn.1002-8331.1902-0195

Previous Articles     Next Articles

Correlation Heuristics Based on ParetoHeu and Instantiation Failure Statistics

XIAO Chenglong, NIE Ziyang, WANG Shanshan   

  1. College of Software, Liaoning Technical University, Huludao, Liaoning 125105, China
  • Online:2020-03-01 Published:2020-03-06



  1. 辽宁工程技术大学 软件学院,辽宁 葫芦岛 125105


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



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