140 Chapter 5.Constraint Satisfaction Problems on the Hubble Space Telescope requires very precise timing of obse are contnuous-valu variab must obey a van e,and power constraint The best-known ntinuo of linear programming problems straints can be solved in time polynomial in the numb er of varial ferent types o constraints and objective unctions have also been studied- -quadratic programming,seconc order conic programming,and so on. In addition to examining the types of variables that can appear in CSPs,it is useful to NARY CONSTRAINT look at the types of constraints.The simplest type is the unary constraint,which restricts the value of a single variable.For example.it could be the case that South Australians actively dislike the color green.Every unary constraint can be eliminated simply by preprocessing the domain of the corresponding variable to remove any value that violates the constraint.A BINARY CONSTRAINT binary constraint relates two variables.For example.SA NSW is a binary constraint.A binary CSP is one with only binary constraints,it can be represented as a constraint graph,as in Figure 5.1(b). Higher-order constraints involve three or more variables.A familiar example is pro- vided by cryptarithmetic puzzles.(See Figure 5.2(a).)It is usual to insist that each letter in a cryptarithmetic puzzle represent a different digit.For the case in Figure 5.2(a)),this would be represented as the six-variable constraint Alldiff(F,T,U,W,R,O).Alternatively,it can be represented by a collection of binary constraints such as..The addition constraints on the four columns of the puzzle also involve several variables and can be written as O+0=R+10,X: X1+W+W=U+10,X2 X2+T+T=0+10:X3 X3=F where X,X2,and X3 are auxiliary variables representing the digit(0 or 1)carried over into the next column.Higher-order constraints can be represented in a constraint hypergraph such as the one shown in Figure 5.2(b).The sharp-eyed reader will have noticed that the Alldiff constraint can be broken down into binary constraints-FTFU,and so on. In fact,as Exercise 5.11 asks you to prove,every higher-order,finite-domain constraint can be reduced to a set of binary constraints ifenough auxiliary variables are introduced.Because of this.we will deal only with binary constraints in this chapter. The constraints we have described so far have all been absolute constraints,violation of which rules out a potential solution.Many real-world CSPs include preference constraints indicating which solutions are preferred.For example,in a university timetabling problem Prof.X might prefer teaching in the morning whereas Prof.Y prefers teaching in the after- noon.A timetable that has Prof.X teaching at 2 p.m.would still be a solution(unless Prof.X happens to be the department chair).but would not be an optimal one.Preference constraints can often be encoded as costs on individual variable assi nments -for example,assigning an afternoon slot for Prof.X costs 2 points against the overall objective function.whereas a morning slot costs 1.With this formulation,CSPs with preferences can be solved using opti-140 Chapter 5. Constraint Satisfaction Problems of experiments on the Hubble Space Telescope requires very precise timing of observations; the start and finish of each observation and maneuver are continuous-valued variables that must obey a variety of astronomical, precedence, and power constraints. The best-known category of continuous-domain CSPs is that of linear programming problems, where con- LINEAR PROGRAMMING straints must be linear inequalities forming a convex region. Linear programming problems can be solved in time polynomial in the number of variables. Problems with different types of constraints and objective functions have also been studied—quadratic programming, second￾order conic programming, and so on. In addition to examining the types of variables that can appear in CSPs, it is useful to UNARY CONSTRAINT look at the types of constraints. The simplest type is the unary constraint, which restricts the value of a single variable. For example, it could be the case that South Australians actively dislike the color green. Every unary constraint can be eliminated simply by preprocessing the domain of the corresponding variable to remove any value that violates the constraint. A BINARY CONSTRAINT binary constraint relates two variables. For example, SA 6= NSW is a binary constraint. A binary CSP is one with only binary constraints; it can be represented as a constraint graph, as in Figure 5.1(b). Higher-order constraints involve three or more variables. A familiar example is pro￾CRYPTARITHMETIC vided by cryptarithmetic puzzles. (See Figure 5.2(a).) It is usual to insist that each letter in a cryptarithmetic puzzle represent a different digit. For the case in Figure 5.2(a)), this would be represented as the six-variable constraint Alldiff (F, T,U, W, R, O). Alternatively, it can be represented by a collection of binary constraints such as F 6= T. The addition constraints on the four columns of the puzzle also involve several variables and can be written as O + O = R + 10 · X1 X1 + W + W = U + 10 · X2 X2 + T + T = O + 10 · X3 X3 = F where X1, X2, and X3 are auxiliary variables representing the digit (0 or 1) carried over into AUXILIARY VARIABLES the next column. Higher-order constraints can be represented in a constraint hypergraph, CONSTRAINT HYPERGRAPH such as the one shown in Figure 5.2(b). The sharp-eyed reader will have noticed that the Alldiff constraint can be broken down into binary constraints—F 6= T, F 6= U, and so on. In fact, as Exercise 5.11 asks you to prove, every higher-order, finite-domain constraint can be reduced to a set of binary constraints if enough auxiliary variables are introduced. Because of this, we will deal only with binary constraints in this chapter. The constraints we have described so far have all been absolute constraints, violation PREFERENCE of which rules out a potential solution. Many real-world CSPs include preference constraints indicating which solutions are preferred. For example, in a university timetabling problem, Prof. X might prefer teaching in the morning whereas Prof. Y prefers teaching in the after￾noon. A timetable that has Prof. X teaching at 2 p.m. would still be a solution (unless Prof. X happens to be the department chair), but would not be an optimal one. Preference constraints can often be encoded as costs on individual variable assignments—for example, assigning an afternoon slot for Prof. X costs 2 points against the overall objective function, whereas a morning slot costs 1. With this formulation, CSPs with preferences can be solved using opti-