Range-consistent forbidden regions of Allen's relations

Beldiceanu, Nicolas and Carlsson, Mats and Derrien, A. and Schutt, A. and Stuckey, P. (2016) Range-consistent forbidden regions of Allen's relations. [SICS Report]



For all 8192 combinations of Allen's 13 relations between one task with origin oi and fixed length li and another task with origin oj and fixed length lj, we give a formula F(min(oj), max(oj), li, lj), where min(oj) and max(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 are useful e.g. in a range-consistency maintaining propagator for an Allen constraint in finite domain constraint programming.

Item Type:SICS Report
Uncontrolled Keywords:global constraint, Allen relation
ID Code:6020
Deposited By:Vicki Carleson
Deposited On:04 May 2016 13:57
Last Modified:06 May 2016 11:27

Repository Staff Only: item control page