SODA

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]

[img]
Preview
PDF
5Mb

Abstract

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