Value ordering for quantified CSPs

Authors: David Stynes Kenneth N Brown

Publish Date: 2008/07/23

Volume: 14, Issue: 1, Pages: 16-37

PDF Link

Abstract

We investigate the use of value ordering in backtracking search for Quantified Constraint Satisfaction problems QCSPs We consider two approaches for ordering heuristics The first approach is solutionfocused and is inspired by adversarial search on existential variables we prefer values that maximise the chances of leading to a solution while on universal variables we prefer values that minimise those chances The second approach is verificationfocused where we prefer values that are easier to verify whether or not they lead to a solution In particular we give instantiations of this approach using QCSPSolve’s purevalue rule Gent et al QCSPsolve A solver for quantified constraint satisfaction problems In Proceedings of IJCAI pp 138–143 2005 We show that on dense 3block problems using QCSPSolve the solutionfocused adversarial heuristics are up to 50 faster than lexicographic ordering while on sparse loose interleaved problems the verificationfocused purevalue heuristics are up to 50 faster Both types are up to 50 faster on dense interleaved problems with one purevalue heuristic approaching an order of magnitude improvement

Keywords: