Range-consistent forbidden regions of Allen’s relations

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

doi:10.1007/978-3-319-59776-8_2

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 proceeding › Conference Paper › Research › peer-review

Abstract

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

Original language	English
Title of host publication	Integration of AI and OR Techniques in Constraint Programming
Subtitle of host publication	14th International Conference, CPAIOR 2017 Padua, Italy, June 5–8, 2017 Proceedings
Editors	Domenico Salvagnin, Michele Lombardi
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	21-29
Number of pages	9
ISBN (Electronic)	9783319597768
ISBN (Print)	9783319597751
DOIs	https://doi.org/10.1007/978-3-319-59776-8_2
Publication status	Published - 2017
Externally published	Yes
Event	International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2017 - Padova, Italy Duration: 5 Jun 2017 → 8 Jun 2017 Conference number: 14th https://cpaior2017.dei.unipd.it/ (Conference website) https://link.springer.com/book/10.1007/978-3-319-59776-8 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	10335
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2017
Abbreviated title	CPAIOR 2017
Country	Italy
City	Padova
Period	5/06/17 → 8/06/17
Internet address	https://cpaior2017.dei.unipd.it/ (Conference website) https://link.springer.com/book/10.1007/978-3-319-59776-8 (Proceedings)

Access to Document

10.1007/978-3-319-59776-8_2

Link to publication in Scopus

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

Beldiceanu, Nicolas ; Carlsson, Mats ; Derrien, Alban ; Prud’homme, Charles ; Schutt, Andreas ; Stuckey, Peter J. / Range-consistent forbidden regions of Allen’s relations. Integration of AI and OR Techniques in Constraint Programming: 14th International Conference, CPAIOR 2017 Padua, Italy, June 5–8, 2017 Proceedings. editor / Domenico Salvagnin ; Michele Lombardi. Cham Switzerland : Springer, 2017. pp. 21-29 (Lecture Notes in Computer Science ).

@inproceedings{3ee1c2de24f74919831911b7539ab5f0,

title = "Range-consistent forbidden regions of Allen{\textquoteright}s relations",

abstract = "For all 8192 combinations of Allen{\textquoteright}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.",

author = "Nicolas Beldiceanu and Mats Carlsson and Alban Derrien and Charles Prud{\textquoteright}homme and Andreas Schutt and Stuckey, {Peter J.}",

year = "2017",

doi = "10.1007/978-3-319-59776-8_2",

language = "English",

isbn = "9783319597751",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "21--29",

editor = "Domenico Salvagnin and Michele Lombardi",

booktitle = "Integration of AI and OR Techniques in Constraint Programming",

note = "International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2017, CPAIOR 2017 ; Conference date: 05-06-2017 Through 08-06-2017",

url = "https://cpaior2017.dei.unipd.it/, https://link.springer.com/book/10.1007/978-3-319-59776-8",

}

Beldiceanu, N, Carlsson, M, Derrien, A, Prud’homme, C, Schutt, A & Stuckey, PJ 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. Lecture Notes in Computer Science , vol. 10335 , Springer, Cham Switzerland, pp. 21-29, International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2017, Padova, Italy, 5/06/17. https://doi.org/10.1007/978-3-319-59776-8_2

Range-consistent forbidden regions of Allen’s relations. / Beldiceanu, Nicolas; Carlsson, Mats; Derrien, Alban; Prud’homme, Charles; Schutt, Andreas; Stuckey, Peter J.

Integration of AI and OR Techniques in Constraint Programming: 14th International Conference, CPAIOR 2017 Padua, Italy, June 5–8, 2017 Proceedings. ed. / Domenico Salvagnin; Michele Lombardi. Cham Switzerland : Springer, 2017. p. 21-29 (Lecture Notes in Computer Science ; Vol. 10335 ).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Range-consistent forbidden regions of Allen’s relations

AU - Beldiceanu, Nicolas

AU - Carlsson, Mats

AU - Derrien, Alban

AU - Prud’homme, Charles

AU - Schutt, Andreas

AU - Stuckey, Peter J.

N1 - Conference code: 14th

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85020804195&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-59776-8_2

DO - 10.1007/978-3-319-59776-8_2

M3 - Conference Paper

AN - SCOPUS:85020804195

SN - 9783319597751

T3 - Lecture Notes in Computer Science

SP - 21

EP - 29

BT - Integration of AI and OR Techniques in Constraint Programming

A2 - Salvagnin, Domenico

A2 - Lombardi, Michele

PB - Springer

CY - Cham Switzerland

T2 - International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2017

Y2 - 5 June 2017 through 8 June 2017

ER -

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