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.


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