Satisfying constraint sets through convex envelopes

Autor:	Eugene Santos, Keum Joo Kim, Eunice E. Santos
Rok vydání:	2006
Předmět:	Convex analysis Mathematical optimization Computer science Proper convex function Hybrid algorithm (constraint satisfaction) Interval (mathematics) Subderivative Constraint satisfaction Theoretical Computer Science Artificial Intelligence Constraint graph Computer Science::Logic in Computer Science Software Constraint satisfaction problem
Zdroj:	Journal of Experimental & Theoretical Artificial Intelligence. 18:413-432
ISSN:	1362-3079 0952-813X
DOI:	10.1080/09528130600926082
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::e96eb151d7432a8caec06312433b091f https://doi.org/10.1080/09528130600926082 Zobrazit plný text záznamu Plný text ve formátu PDF Plný text ve formátu HTML
Nepřihlášeným uživatelům se plný text nezobrazuje	K zobrazení výsledku je třeba se přihlásit.