Solving connected row convex constraints by variable elimination

Yuanlin Zhang, Satyanarayana Marisetti

Research output: Contribution to journalArticle

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
JournalArtificial Intelligence
StatePublished - 2009


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

Cite this