Range-consistent forbidden regions of Allen’s relations

Nicolas Beldiceanu, Mats Carlsson, Alban Derrien, Charles Prud’homme, Andreas Schutt, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

For all 8192 combinations of Allen’s 13 relations between one task with origin oi and fixed length ℓi and another task with origin oj and fixed length ℓj, this paper shows how to systematically derive a formula F (oj, oj, ℓi, ℓj), where oj and oj respectively denote the earliest and the latest origin of task j, evaluating to a set of integers which are infeasible for oi for the given combination. Such forbidden regions allow maintaining range-consistency for an Allen constraint.

Original languageEnglish
Title of host publicationIntegration of AI and OR Techniques in Constraint Programming
Subtitle of host publication14th International Conference, CPAIOR 2017 Padua, Italy, June 5–8, 2017 Proceedings
EditorsDomenico Salvagnin, Michele Lombardi
Place of PublicationCham Switzerland
PublisherSpringer
Pages21-29
Number of pages9
ISBN (Electronic)9783319597768
ISBN (Print)9783319597751
DOIs
Publication statusPublished - 2017
Externally publishedYes
EventInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2017 - Padova, Italy
Duration: 5 Jun 20178 Jun 2017
Conference number: 14th
https://cpaior2017.dei.unipd.it/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10335
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2017
Abbreviated titleCPAIOR 2017
CountryItaly
CityPadova
Period5/06/178/06/17
Internet address

Cite this

Beldiceanu, N., Carlsson, M., Derrien, A., Prud’homme, C., Schutt, A., & Stuckey, P. J. (2017). Range-consistent forbidden regions of Allen’s relations. In D. Salvagnin, & M. Lombardi (Eds.), Integration of AI and OR Techniques in Constraint Programming: 14th International Conference, CPAIOR 2017 Padua, Italy, June 5–8, 2017 Proceedings (pp. 21-29). (Lecture Notes in Computer Science ; Vol. 10335 ). Springer. https://doi.org/10.1007/978-3-319-59776-8_2