Title: Constraint Hierarchies
Authors: Alan Borning, Bjorn Freeman-Benson, and Molly Wilson
Lisp and Symbolic Computation, Vol. 5 No. 3, (September 1992),
pages 223-270.
Reprinted in Constraint Programming, B. Mayoh, E. Tougu, J.
Penjam (Eds.), NATO Advanced Science Institute Series, Series F: Computer
and System Sciences, Vol 131, Springer-Verlag, 1994, pages 75-115.
Abstract
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 both required and preferential 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. A constraint 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.
full paper:
compressed postscript;
pdf