Solving functional constraints by variable substitution

Yuanlin Zhang, Roland H.C. Yap

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

Functional constraints and bi-functional constraints are an important constraint class in Constraint Programming (CP) systems, in particular for Constraint Logic Programming (CLP) systems. CP systems with finite domain constraints usually employ Constraint Satisfaction Problem(s)-based solvers which use local consistency, for example, arc consistency. We introduce a new approach which is based instead on variable substitution. We obtain efficient algorithms for reducing systems involving functional and bi-functional constraints together with other nonfunctional constraints. It also solves globally any CSP where there exists a variable such that any other variable is reachable from it through a sequence of functional constraints. Our experiments on random problems show that variable elimination can significantly improve the efficiency of solving problems with functional constraints.

Original languageEnglish
Pages (from-to)297-322
Number of pages26
JournalTheory and Practice of Logic Programming
Volume11
Issue number2-3
DOIs
StatePublished - Mar 2011

Keywords

  • Arc consistency
  • Constraint logic programming
  • Constraint satisfaction problem
  • Functional constraints
  • Variable substitution

Fingerprint Dive into the research topics of 'Solving functional constraints by variable substitution'. Together they form a unique fingerprint.

  • Cite this