Directional interchangeability for enhancing CSP solving

Naanaa, W.
(2007) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 4th International Conference, CPAIOR 2007 — Location: Brussels, Belgium (23.May.2007)

Files

No attached file found for this publication.

Details

Authors
  • Naanaa, W.
    Author
Abstract
This paper introduces directional interchangeability, a weak form of neighborhood interchangeability [Freuder, EC, 1991]. The basic idea is that although two values of a variable may not be neighborhood interchangeable if we consider the whole neighborhood of the variable, they could be neighborhood interchangeable if we restrict the neighborhood to a subset of neighboring variables induced by a variable ordering. In spite of the fact that the proposed concept cannot be used to remove redundant values while preserving problem satisfiability, it provides a mean to partition value domains into subsets of directionally interchangeable values that can be attempted simultaneously by a tree search. Several experiments carried out on various binary CSPs, clearly indicate that variations of the Forward-Checking algorithm and the Maintaining Arc-Consistency algorithm that exploit directional interchangeability often outperform the original algorithms.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Naanaa, W. (2007). Directional interchangeability for enhancing CSP solving. In Van Hentenryck, P.; Wolsey, L.; (ed.), Integration of AI and OR Techniques in Constraint Programming forCombinatorial Optimization Problems. Proceedings 4th InternationalConference, CPAIOR 2007 (p. p. 200-213). Springer-verlag. https://hdl.handle.net/2078.5/229762