JUCS - Journal of Universal Computer Science 12(11): 1466-1499, doi: 10.3217/jucs-012-11-1466
An Interval Constraint Branching Scheme for Lattice Domains
expand article infoAntonio J. Fernández Leiva, Patricia M. Hill
‡ University of Leeds, United Kingdom
Open Access
Abstract
Abstract This paper presents a branching schema for the solving of a wide range of interval constraint satisfaction problems defined on any domain of computation, finite or infinite, provided the domain forms a lattice. After a formal definition of the branching schema, useful and interesting properties, satisfied by all instances of the schema, are presented. Examples are then used to illustrate how a range of operational behaviors can be modelled by means of different schema instantiations. It is shown how the operational procedures of many constraint systems (including cooperative systems) can be viewed as instances of this branching schema. Basic directives to adapt this schema to solving constraint optimization problems are also provided.
Keywords
interval constraint, constraint branching, constraint solving, constraint optimization, constraint propagation