Solving connected row convex constraints by variable elimination

Yuanlin Zhang, Satyanarayana Marisetti

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

We propose an algorithm for the class of connected row convex constraints. In this algorithm, we introduce a novel variable elimination method to solve the constraints. This method is simple and able to make use of the sparsity of the problem instances. One of its key operations is the composition of two constraints. We have identified several nice properties of connected row convex constraints. Those properties enable the development of a fast composition algorithm whose complexity is linear to the size of the variable domains. Compared with the existing work including randomized algorithms, the new algorithm has favorable worst case time and working space complexity. Experimental results also show a significant performance margin over the existing consistency based algorithms.

Original languageEnglish
Pages (from-to)1204-1219
Number of pages16
JournalArtificial Intelligence
Volume173
Issue number12-13
DOIs
StatePublished - Aug 1 2009

    Fingerprint

Keywords

  • Connected row convex constraints
  • Constraint composition
  • Constraint satisfaction problems
  • Path consistency
  • Variable elimination

Cite this