An Interval Constraint Branching Scheme for Lattice Domains

Antonio J. Fernández (University of Málaga, Spain)

Patricia M. Hill (University of Leeds, United Kingdom)

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: constraint branching, constraint optimization, constraint propagation, constraint solving, interval constraint

Categories: D.3.3, I.1.2