Weight-based heuristics for constraint satisfaction and combinatorial optimization problems

Marie-José Huguet (1) , Pierre Lopez (1) , Wafa Karoui (1)

1 LAAS-MOGISA

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.

Mots clés: Weight-based heuristics; tree search; constraint satisfaction; scheduling

Domaines: Intelligence artificielle [cs.AI]; Recherche opérationnelle [math.OC]

Marie-José Huguet, Pierre Lopez, Wafa Karoui. Weight-based heuristics for constraint satisfaction and combinatorial optimization problems. Journal of Mathematical Modelling and Algorithms, 2012, 11 (2), p.193-215. ⟨hal-00660715⟩