This chapter is from the book
This chapter is from the book
This chapter is from the book
Chapter 7—Combinatorial Searching
His Lady sad to see his sore constraint, Cride out, Now now Sir knight, shew what ye bee.
— EDMUND SPENSER, The Faerie Queene (1590)
The work under our labour grows, Luxurious by restraint.
— JOHN MILTON, Paradise Lost (1667)
Liberty exists in proportion to wholesome restraint.
— DANIEL WEBSTER (1847)
It is impossible to be an artist and not care for laws and limits. Art is limitation; the essence of every picture is the frame.
— GILBERT K. CHESTERTON, Orthodoxy (1908)
I surround myself with obstacles. Whatever diminishes my discomfort diminishes my strength. The more constraints one imposes, the more one frees one’s seif of the chains that shackle the spirit.
— IGOR STRAVINSKY, Poétique musicale sous forme de six leçons (1939)
7.2.2.3. Constraint satisfaction.
In Section 7.2.2.1 we solved numerous examples of XCC problems — exact covering with colors—which featured “items” and “options.” Then in Section 7.2.2.2 we resolved lots of SAT problems — Boolean satisfiability — which featured “literals” and “clauses.” All of these, and more, are instances of a combinatorial challenge that’s more general yet, the constraint satisfaction problem—often called the CSP for short—which we will see is based on “variables,” “domains,” and “constraints.”
The idea is simple: We’re given a finite list of variables (x1, x2, ..., xn), to which we can assign values that belong to given finite domains (D1, D2, ..., Dn). And we’re also given a set of constraints {R1, R2, ..., Rm}, each of which specifics that a certain subset of the values (x1, x2, ..., xn) must be mutually compatible. Some combinations of values are “good”; the others are “nogood.”
For example, let n = 5, and suppose that each domain is a set of letters:
)
Thus there are 2 × 2 × 3 × 2 × 2 = 48 possible settings of x1x2x3x4x5, from BCAED to SLUON. Let’s also impose three constraints:
)
This CSP has two solutions, easily found by hand (see exercise 1).
Every SAT problem is obviously a CSP in which all the domains are {0,1}. For example, problem 
in 7.2.2.2–(3) has four constraints,
)
Conversely, every CSP can be formalized as an equivalent. SAT problem, by using several SAT variables to represent each CSP variable x whose domain size d exceeds 2. For example, if the domain is {0, 1, ..., d − 1}, Section 7.2.2.2 discussed the “log encoding,” with l = [lg d] Boolean variables meaning that x = (xl−1 ... x1x0)2. There’s also the “direct encoding,” with d variables xk = [x = k], as well as the “order encoding,” which has d − 1 variables xj = [x ≥ j]. We also discussed a variety of ways to represent arbitrary constraints, in the form of one or more clauses involving such Boolean variables. Each of those encodings has its own virtues and weaknesses, depending on the application.
Every XCC problem can, similarly, be regarded as a CSP. One way is to have a variable xi for every primary item i, with domain Di equal to the set of options that contain i. The constraints are that xi and xj cannot be options that conflict: If xi = oi and xj = oj, where oi ≠ oj, then oi and oj cannot have a common primary item, nor can they have a common secondary item that’s colored differently in oi and oj. Conversely, exercise 7.2.2.1-100 presented one way to encode any CSP as an XCC problem.
Thus XCC, SAT, and CSP can each be reduced to the other two.
We’ve already learned how to construct excellent XCC solvers and excellent SAT solvers, so we might be tempted to stop there, regarding CSP as a problem that’s already been well solved. But we shall see that careful consideration of the CSP not only clarifies XCC and SAT, it also teaches us important new methods.
Related models.
Many groups of researchers have independently adopted conceptual frameworks that are identical to or very similar to the notions of variables, domains, and constraints. For example, a theory of relational structures has been developed as part of the branch of mathematics called “model theory,” which spawned “universal algebra.” A relational structure is a set D together with a set {R1, R2, ...} of relations or “predicates” defined on the elements of D. Each relation Ri depends on k elements, for some k = ki, and it defines the k-tuples of elements for which that predicate is true. [See P. M. Cohn, Universal Algebra (1965), Chapter V.]
Let’s be a little more precise. The Cartesian product of sets (D1, ..., Dn), denoted by D1 × ⋯ × Dn, is the set of all n-tuples (x1, ..., xn) such that xi ∈ Di for 1 ≤ i ≤ n. Thus, D1 × ⋯ × Dn is the set of all solutions to a CSP with domains (D1, ..., Dn), in the case when there are no constraints. An n-tuplc such as (x1, ..., xn) is often written simply as x1 .... xn, when commas aren’t necessary. We also write D × ⋯ × D = Dn when the n domains are all identical.
A k-ary relation on sets (D1, ..., Dk) is a subset of D1 × ⋯ × Dk. We write either R(x1, ..., xk) or x1 ... xk ∈ R when we want to say that the k-tuple (x1, ..., xk) satisfies relation R. The relation is called binary when k = 2, ternary when k = 3, quaternary when k = 4, and so on; it’s unary when k = 1. (Strictly speaking, there also are nullary relations: see exercise 5.)
The simplest nontrivial relational structures arise where there’s just a single binary relation. In fact, this case is so simple, we hardly ever think of it as a “relation structure” at all: We call it a directed graph. Indeed, we know well that a directed graph is a set V of vertices, together with a set A ⊆ V × V of arcs; and that’s exactly what it means to be a relational structure with a single binary relation. This case is so common, we usually use the special notation u→ν, instead of writing A(u, v) or uv ∈ A.
A simple example.
To warm up, let’s look at a little puzzle that appeared on a British TV show called The Crystal Maze in 1994. The task is simple — but you’ve got only two minutes to do it: “Place eight large disks, marked with the letters A through H, onto the eight circles shown; consecutive letters can’t be adjacent.”
)
We’re actually facing two challenges here, namely (i) solve the puzzle; and (ii) express it as a constraint satisfaction problem, so that a computer can solve it for us. We’ll tackle (ii), so as not to spoil the fun of (i). And we’ll allow ourselves ten minutes, say, to accomplish goal (ii).
What are appropriate variables, domains, and constraints? We’d better label the vertices of the graph, so that we can readily describe what we want to define. One approach, based on the labeling shown, is to have eight variables {x1, x2, …, x8}, one for each vertex, each with domain {A, B, ..., H}. Then there are seventeen constraints, one for each edge of the graph; for example, the constraint for edge 1 — 2 is
)
and the same relation is used for all of the other edges. It can be written much more succinctly, if we assume that the letters are represented by integer codes:
)
OK, that took three minutes. Are we done? Well, no, actually: the seventeen constraints we’ve specified do not obviously rule out the possibility that x1 = x8. We’re not allowed to put a disk on two different circles.
We could add eleven further constraints, namely xi ≠ xj for each of the yet-unconstrained pairs. But seasoned CSP solvers generally prefer to append a single global constraint instead, involving all of the variables at once:
)
Indeed, special methods have been devised for the “all-different” constraint, because it arises in so many different problems. With (14), we’ve satisfied (ii).
Five minutes to go. Is there a better way? Another possibility is to let the variables be {A, B, ..., H}, one for each disk, each with domain {1, 2, ..., 8}. Then only seven constraints are needed, one for each pair of consecutive letters: e.g.,
)
And each of these constraints has only 22 tuples, compared to 42 in (12). It’s a win! Of course we also need the global all-different constraint. (See exercise 13.)
If we only had more time, we could have discovered a completely different way to model problem (11) as a CSP, such as the approach in exercise 16.
Automating automobiles.
We’ve already seen dozens and dozens of significant examples of constraint-based problems when we studied exact covering and SAT. But we certainly haven’t exhausted all of the major applications, and several problems on our yet-unexamined list have been associated historically with the CSP. One of them, known as the car sequencing problem, is especially appropriate for us to study next, not only because its initials are “CSP” but also because it is problem 001 in CSPLIB — a noteworthy collection of benchmarks that was launched by I. P. Gent and T. Walsh in 1999 (sec LNCS 1713 (1999), 480–481).
Consider the portion of an automobile assembly line where optional features are being installed on newly made vehicles. Some of the cars will be made with moonroofs; some will have heated seats; and so on. The assembly line is divided into work areas, one for each special feature. Work area w has space for qw cars, where qw is the number of time slots needed to install feature w as the conveyor belt moves the cars along. If at most pw/qw of the cars need that feature, pw installers are on duty, one of whom will commence work when a car enters the area and walk with it until the installation is done. The car sequencing problem is the task of arranging a given set of cars into a sequence so that no subsequence of qw consecutive cars will include more than pw that need feature w.
)
Fig. 100. Cars of models A, B, . . . enter this assembly line at the far right, receiving optional features when they’re in an appropriate work area. If this sequence has specifications (16), the final car (F) will be delayed in the LED area, because three cars in a row want that feature. The car sequencing problem tries to avoid such delays.
For example, there might be six models using the following subsets of five features:
)
Suppose ten cars of models {A, A, A, B, B, C, C, D, E, F} are to be made. The sequence ABABACDCEF is almost correct, but it fails on the final car (see Fig. 100). Can you find a delay-free sequence? Notice that the left-right reflection of any solution is also a solution; we can rule out mirror images by requiring that model F, say, appears among the first five cars. Exercise 17 has the (unique) answer.
The car sequencing problem has boundary effects at the left and right that make it somewhat unrealistic. (Industrial assembly lines don’t really start out empty every day!) Still, it’s a nice clean problem, instructive to chew on.
An international competition was held in 2005, based on actual industrial data. It included additional constraints, such as the colors of paint to be used and the initial contents of the assembly line, and it inspired many creative solutions. [See C. Solnon, V. D. Cung, A. Nguyen, and C. Artigues, EJOR 191 (2008), 912–927.] The winning programs were based on local search methods analogous to WalkSAT, using “greedy” heuristics.
Line labeling in computer vision.
Speaking of history, let’s turn now to some fascinating aspects of computer vision that influenced much of the early work on constraint processing. When a camera photographs a scene, it makes a two-dimensional image of three-dimensional reality; interesting problems arise when we try to reconstruct the reality from the image.
We’ll work with an extremely simplified yet powerful model, as the original researchers did: Our “reality” will be a world of special polyhedral objects, where exactly three faces meet at each of the vertices. For example, an ordinary cube or tetrahedron or 
will qualify. But an octahedron will not, nor will an Egyptian-style pyramid, nor 
, because a vertex where four faces meet isn’t allowed. These three-faced concepts can be generalized, of course, but it’s helpful to start with a thorough understanding of the comparatively simple trihedral world.
More precisely, the 3D objects we shall deal with have no curved surfaces. They are defined by vertices, edges, and faces, where the vertices are “corners” at which edges and faces come together. All of the faces are “flat,” meaning that their points all lie on some plane. Each face is bounded by an exterior polygon, possibly with one or more interior polygons delimiting “holes” in the face. Each edge runs between two vertices and is part of the (infinite) line where the planes of two adjacent faces meet; it’s a segment of the polygonal boundaries of those faces. And significantly, each vertex is the endpoint of exactly three edges. We shall call such an object a three-valent polyhedral object, or 3VP for short. (See Fig. 101.)
Fig. 101. Examples of 3VPs (three-valent polyhedra): (a) A stylized sphinx. [68 vertices, 102 edges, 38 faces.] (b) The Szilassi polyhedron, defined in exercise 26. Each of its seven faces is adjacent to all of the other six(!). [14 vertices, 21 edges, 7 faces.] (c) A clasp formed from two identical, interlocked objects, each of which is a tetrahedron from which a large triangular wedge has been hollowed out. [20 vertices, 30 edges, 14 faces.] (d) The histoscape for the matrix 
, as defined in exercise 27. [20 vertices, 30 edges, 12 faces.] Many of the vertices, edges, and faces of these examples are invisible because they lie behind the parts that we can see.
The two-dimensional images shown here make sense to us, somehow, although significant depth information has been lost. In some mysterious way we’ve learned to rely on visual cues in order to understand what’s really present.
){kind=link}