Satisfying constraint sets through convex envelopes

Eugene Santos, Eunice E. Santos, Keumjoo Kim

Research output: Contribution to journalArticlepeer-review


In this article, we present a general representation for constraint satisfaction problems with disjunctive relations called cluster constraint systems (CCS). For this representation, we develop a novel and simple approach for solving CCSs using convex envelopes. These envelopes can be used to decompose the feasible space of the CCS through convex approximations. We explore interval reasoning as a case study of CCS. Our experimental results demonstrate that such CCS can be effectively and efficiently solved through convex enveloping with very modest branching requirements in comparison to other generic as well as specialized algorithms for interval reasoning. In fact, convex enveloping solves significantly more cases and more efficiently than other methods used in our test bed.

Original languageEnglish (US)
Pages (from-to)413-432
Number of pages20
JournalJournal of Experimental and Theoretical Artificial Intelligence
Issue number3
StatePublished - Sep 1 2006
Externally publishedYes


  • Algorithms
  • Constraint satisfaction
  • Convex envelopes
  • Interval reasoning

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Satisfying constraint sets through convex envelopes'. Together they form a unique fingerprint.

Cite this