Using indexed finite set variables for set bounds propagation

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Constraint Programming (CP) has been successfully applied to numerous combinatorial problems such as scheduling, graph coloring, circuit analysis, or DNA sequencing. Following the success of CP over traditional domains, set variables were also introduced to more declaratively solve a number of different problems. Using a bounds representation for a finite set variable allows one to compactly represent the solution set of a set constraint problem. Many consistency mechanisms for maintaining bounds consistency have been proposed and in this paper we propose to use delta domain variable information to speed up constraint propagation. Additionally, we propose the use of indexed set domain variable representations as a better means of improving the use, intuitiveness and efficiency of delta domain variables for propagation tasks.

Original languageEnglish
Title of host publicationAdvances in Artificial Intelligence - IBERAMIA 2008 - 11th Ibero-American Conference on AI, Proceedings
EditorsH. Geffner, R. Prada, I. Machado Alexandre, N. David
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages73-82
Number of pages10
ISBN (Electronic)978-3-540-88309-8
ISBN (Print)978-3-540-88308-1
DOIs
Publication statusPublished - 1 Dec 2008
Event11th Ibero-American Conference on Artificial Intelligence, IBERAMIA 2008 - Lisbon, Portugal
Duration: 14 Oct 200817 Oct 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume5290 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th Ibero-American Conference on Artificial Intelligence, IBERAMIA 2008
CountryPortugal
CityLisbon
Period14/10/0817/10/08

Keywords

  • Constraint propagation
  • Delta domain variables
  • Finite set constraint variables
  • Graph constraint variables
  • Indexation

Fingerprint Dive into the research topics of 'Using indexed finite set variables for set bounds propagation'. Together they form a unique fingerprint.

  • Cite this

    Viegas, R. D., Correia, M., Barahona, P., & Azevedo, F. (2008). Using indexed finite set variables for set bounds propagation. In H. Geffner, R. Prada, I. Machado Alexandre, & N. David (Eds.), Advances in Artificial Intelligence - IBERAMIA 2008 - 11th Ibero-American Conference on AI, Proceedings (pp. 73-82). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5290 LNAI). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-540-88309-8_8