Constraint hierarchies

Constraints allow programmers and users to state declaratively a relation that should be maintained, rather than requiring them to write procedures to maintain the relation themselves. They are thus useful in such applications as programming languages, user interface toolkits, and simulation packages. In many situations, it is desirable to be able to state bothrequired andpreferential constraints. The required constraints must hold. Since the other constraints are merely preferences, the system should try to satisfy them if possible, but no error condition arises if it cannot. Aconstraint hierarchy consists of a set of constraints, each labeled as either required or preferred at some strength. An arbitrary number of different strengths is allowed. In the discussion of a theory of constraint hierarchies, we present alternate ways of selecting among competing possible solutions, and prove a number of propositions about the relations among these alternatives. We then outline algorithms for satisfying constraint hierarchies, and ways in which we have used constraint hierarchies in a number of programming languages and systems.