Constraint Propagation as Information Maximization

This paper draws on diverse areas of computer science to develop a unified view of computation: - Optimization in operations research, where a numerical objective function is maximized under constraints, is generalized from the numerical total order to a non-numerical partial order that can be interpreted in terms of information. The distinction is essential in our definition of constraint satisfaction problems. As application we treat constraint satisfaction problems over reals. The chaotic algorithm analyzed in the paper combines the efficiency of floating-point computation with the correctness guarantees of arising from our logico-mathematical model of constraint-satisfaction problems. The early history of constraint processing is written in three MIT theses: Sutherland's, Waltz's, and Steele's [16, 20, 14]. Already in this small selection one can discern two radically different approaches. Sutherland and Steele use relaxation: starting form a guessed assignment of values to variables, constraints are successively used to adjust variables in such a way as to satisfy better the constraint under consideration. These authors followed an old idea brought into prominence under the name of relaxation by Southwell [15]. He associated with each of the problem's variables a domain; that is, the set of all values that are not a priori impossible. Each constraint is then used to eliminate values from the domains of one or more variables affected by the constraint that are incompatible with that constraint. In this paper we are concerned with the latter method, which we call the domain reduction method.