Conflict History Based Branching Heuristic for CSP Solving

Djamal Habet (1) , Cyril Terrioux (1)

1 COALA - COntraintes, ALgorithmes et Applications

An important feature in designing algorithms to solve Constraint Satisfaction Problems (CSP) is the definition of a branching heuristic to explore efficiently the search space and exploit the problem structure. We propose Conflict-History Search (CHS), a new dynamic and adaptive branching heuristic for CSP solving. It is based on the search history by considering the temporality of search failures. To achieve that, we use the exponential recency weighted average to estimate the evolution of the hardness of constraints throughout the search. The experimental evaluation on XCSP3 instances shows that integrating CHS to solvers based on MAC obtains competitive results and can improve those obtained through other heuristics of the state of the art.

Mots clés: CSP; Search History; Conflict Based Branching Heuristic; Exponential Recency Weighted Average

Domaines: Intelligence artificielle [cs.AI]

Djamal Habet, Cyril Terrioux. Conflict History Based Branching Heuristic for CSP Solving. Proceedings of the 8th International Workshop on Combinations of Intelligent Methods and Applications (CIMA), Nov 2018, Volos, Greece. ⟨hal-02090610⟩