Solving connected row convex constraints by variable elimination

Yuanlin Zhang, Satyanarayana Marisetti

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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
Issue number12-13
StatePublished - Aug 2009


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


Dive into the research topics of 'Solving connected row convex constraints by variable elimination'. Together they form a unique fingerprint.

Cite this