
Generalized Local Propagation:
A Framework for Solving Constraint Hierarchies
Hiroshi Hosobe,1 Satoshi Matsuoka,2 and Akinori Yonezawa1
1 Department of Information Science
2 Department of Mathematical Engineering
University of Tokyo
31, Hongo 7chome, Bunkyoku, Tokyo 113, JAPAN
fdetail@is.s, matsu@ipl.t, yonezawa@is.sg.utokyo.ac.jp
Abstract. `Constraint hierarchy' is a nonmonotonic system that allows programmers to describe overconstrained realworld problems by specifying constraints with hierarchical preferences, and has been applied to various areas. An important aspect of constraint hierarchies is the existence of efficient satisfaction algorithms based on local propagation. However, past localpropagation algorithms have been limited to multiway equality constraints. We overcome this by reformulating constraint hierarchies with a more strict definition, and proposing generalized local propagation as a theoretical framework for studying constraint hierarchies and local propagation. Then, we show that global semimonotonicity in satisfying hierarchies turns out to be a practically useful property in generalized local propagation. Finally, we discuss the relevance of generalized local propagation with our previous DETAIL algorithm for solving hierarchies of multiway equality constraints.
Keywords: constraint hierarchies, nonmonotonicity, local propagation, multiway constraints.
1 Introduction
Constraint hierarchies allow programmers to describe overconstrained realworld
problems by specifying constraints with hierarchical strengths or preferences
[1, 2], and have been applied to various research areas such as constraint
logic programming [11, 13], constraint imperative programming [3], and graphical
user interfaces [8, 9]. Intuitively, in a constraint hierarchy, the stronger a
constraint is, the more it influences the solutions of the hierarchy. For example,
the hierarchy of the constraints strong x = and weak x = 1 yields the solution
x 0. This property enables programmers to specify preferential or default constraints
that may be used in case the set of required or nondefault constraints
are underconstrained. Moreover, constraint hierarchies are general enough to
handle powerful constraint systems such as arithmetic equations and inequalities
over reals. Additionally, they allow `relaxing' of constraints with the same
strength by applying, e.g., the leastsquares method.