Chapter 3 – Constraint Propagation

Publisher Summary This chapter discusses that constraint reasoning involves various types of techniques to tackle the inherent intractability of the problem of satisfying a set of constraints. Constraint propagation is one of those types of techniques. It is central to the process of solving a constraint problem and indispensable for constraint reasoning. The chapter examines that constraint propagation embeds any reasoning, which consists in explicitly forbidding values or combinations of values for some variables of a problem, because a given subset of its constraints cannot be satisfied otherwise. It is in constraint reasoning that this concept shows its most accomplished form. There is no other field in which the concept of constraint propagation appears in such a variety of forms, and in which its characteristics have been analyzed. The chapter reviews that it formalizes all constraint propagation approaches within a unifying framework and discusses the main existing types of constraint propagation.