Weight‐based Heuristics for Constraint Satisfaction and Combinatorial Optimization Problems

In this paper, we propose mechanisms to improve instantiation heuristics by incorporating weighted factors on variables. The proposed weight‐based heuristics are evaluated on several tree search methods such as chronological backtracking and discrepancy‐based search for both constraint satisfaction and optimization problems. Experiments are carried out on random constraint satisfaction problems, car sequencing problems, and jobshop scheduling with time‐lags, considering various parameter settings and variants of the methods.The results show that weighting mechanisms reduce the tree size and then speed up the solving time, especially for the discrepancy‐based search method.