The SkyBlue Constraint Solver and Its Applications
Author: Michael Sannella
In Vijay Saraswat and Pascal van Hentenryck (eds), Principles and
Practice of Constraint Programming: The Newport Papers, MIT Press,
1995.
Abstract
The SkyBlue constraint solver uses multi-way local propagation to
efficiently maintain constraints organized in a constraint hierarchy. As
individual constraints are added and removed, SkyBlue executes
method procedures associated with each constraint to incrementally
resatisfy the constraints. SkyBlue is a successor to the DeltaBlue
algorithm, which has two significant limitations: cycles of constraints are
prohibited, and constraint methods can only have a single output variable.
SkyBlue relaxes these restrictions, satisfying cycles of constraints by
calling external solvers and supporting multi-output methods.
This paper compares SkyBlue to other constraint solvers, describes the
SkyBlue algorithm and discusses several applications that have been built
using SkyBlue. The SkyBlue algorithm description introduces several new
concepts including method vines (used to select which methods to
execute) and walkbounds (a generalization of DeltaBlue's
walkabout strengths).
full paper (compressed postscript)
Constraints home page