Systematic Versus Stochastic Constraint Satisfaction

1 Introduction: Eugene C. Freuder

Constraint satisfaction problems (CSPs) involve finding values for problem variables that satisfy restrictions on which combinations of values are allowed [Freuder and Mackworth, 1994; Tsang, 1993] . They have many appli­ cations, including planning and scheduling, design and configuration, vision and language, temporal and spatial reasoning. The map coloring problem is a simple ex­ ample, where the problem variables correspond to coun­ tries, the values to colors, and the constraints specify that neighboring countries cannot have the same color.

In constraint satisfaction, as in many areas of AI, there is competition between systematic methods for prob­ lem solving, which will, if necessary, explore the en­ tire problem space, and stochastic methods, which can involve an element of random choice as to which por­ tions of the problem space will be examined. System­ atic CSP aproaches include search and inference tech­ niques. Stochastic approaches include those influenced

*This material is based on work supported by the National Science Foundation under Grant No. IRI-9207633.

tThis work was partially supported by NSF grant IRI9157636, by the Electrical Power Research Institute (EPRI), and by grants from Toshiba of America, Xerox Northrop and Rockwell.

tThis work has been supported by the Air Force Of­ fi ce of Scientific Research under contract 92-0693 and by ARPA/Rome Labs under contracts F30602-91-C-0036 and F30602-93-C-00031 .

Matthew L. Ginsberg+

CIRL

University of Oregon Eugene, Oregon 97403 U.S.A. gins berg@cs. uoregon. ed u

Edward Tsang

Department of Computer Science University of Essex Essex C04 3SQ, United Kingdom edward@essex.ac. uk

by physical metaphors (hill climbing, simulated anneal­ ing) and those influenced by biological metaphors (neu­ ral networks, genetic algorithms). Each of our panelists is prepared to speak for one of these four approaches (but will not be restricted to that limited advocacy role).

Though our primary focus is on systematic versus stochastic, there are also interesting issues of search ver­ sus inference on the systematic side, and physical versus biological on the stochastic side. On the other hand, there are intriguing possibilities for conjoining the sys­ tematic and the stochastic.

Stochastic methods are generally incomplete: they cannot guarantee that they will find a solution, or prove that a solution does not exist. Systematic methods can. However, stochastic methods are sometimes very fast. Are stochastic methods inherently faster? Or are there some types of problems for which stochastic methods are better suited, and some types of problems for which systematic methods are better suited?

If and when stochastic methods are faster, why are they faster? There are actually at least three factors that these methods generally have in common - randomness, locality, incompleteness. Which are really operative fac­ tors?

Is the random element important? Why? There is of­ ten a local nature to stochastic search, decision making based only on local features of the problem space: how can making less informed decisions be helpful? Is there actually a positive advantage to randomness or locality; or is it simply unproductive to spend more time to make informed or global choices? On the surface it seems plau­ sible that one could gain something - speed - by giving up something - completeness: but can we explain how this tradeoff works?

Do the successes of stochastic methods really depend on their being non-systematic, or can they be incorpo­ rated into systematic methods? For example, an early success with constraint satisfaction using neural net­ works, led to a hill climbing technique, that led to or­ dering heuristics for systematic backtrack search. The systematic version did at least as well as the hill climb­ ing in at least one of the tested problem domains [Minton et al. , 1992] .

Stochastic methods often begin by transforming a problem into a more "atomistic" representation, e.g. in terms of SAT propositional variables or neural network nodes. These representations would appear to lose, or at least deemphasize, higher level organizational infor­ mation; are they succeeding in spite of that, or because of it? Are these methods succeeding because they em­ phasize the lower level "microstructure" of problems, the consistency patterns as opposed to the higher level pat­ terns of constraints or subproblems [Freuder, 1994]?

Some additional provocative questions for the stochas­ tic side:

• Time versus Space. Are stochastic methods buying speed with unreasonable space demands? To what extent do these methods only appear to solve large problems because they have a large representation of a small problem?
• Learning versus Cheating. Are stochastic methods being fairly tuned for a given problem domain, or unfairly biased?
• Consistency Computation versus Control Computa­ tion. How would stochastic methods fare on prob­ lems where there is a high cost associated with de­ termining consistency of individual values, enhanc­ ing the effectiveness of inference that avoids consis­ tency checking?

Some additional provocative questions for the system­ atic side:

• Completeness versus Responsiveness. To what ex­ ent is completeness a red herring: if we cannot wait for the complete answer, is not the systematic method de facto incomplete?
• Intelligence versus Brute Force. Does systematic reasoning pay off or is intelligence just overhead?
• Optimal versus Satisficing. Will repeated applica­ tion of stochastic methods find a "good enough" solution faster than a systematic search for the best solution?

Ultimately the most provocative question for both sides may be:

• Rather than competing, can we cooperate?

Can the two communities learn from each other? Which differences are important and which superficial, or even misleading? Can methods usefully combine ideas from both communities? There has been exciting recent progress in that direction ([Ginsberg and McAllester, 1994; Verfaillie and Schiex, 1994; Yokoo, 1994]).

2 Systematic vs Stochastic Greedy Algorithms: Rina Dechter

Systematic algorithms have two properties [Pearl, 1984]: (1) Do not leave any stone unturned (completeness), and (2) do not turn any stone more then once (efficiency). Most classical research in heuristic search focused on such algorithms, some examples of which are A* and backtracking. Recently, greater attention is shifting to­ wards a class of greedy nonsystematic algorithms that we will call Stochastic greedy {SG ) . These algorithms may leave "many stones unturned" and may also "turn the same stone multiple times" (as do many complete algo­ rithms).

Here are some facts: first, it can be demonstrated that many large problem instances that are practically un­ solvable by systematic algorithms are solved efficiently using stochastic-greedy methods [Minton et al., 1992; Selman et al., 1992]. Secondly, it was also observed that for many problem instances SG methods are less effective than systematic search, even when the problem is satis­ fiable [Konolige, 1994; Kask & Dechter, 1995]. Third, SG methods are highly ineffective for inconsistent prob­ lems. Finally, constraint satisfaction problems are NP­ complete and therefore finding one "best performing" algorithm on every proble~ instance is unlikely.

The important problem is not finding which paradigm is the winner, but rather how to exploit identified class­ superior algorithms within one meta framework. For ar­ gument's sake, let us call an algorithm "class-superior" if there exists a reasonable-size class of problem instances over which the algorithm is proven superior, be it ex­ perimentally or theoretically. Let us also assume that we have identified a collection of classes and their cor­ responding class-superior algorithms and that no algo­ rithm dominates other on all classes. I make two claims: (1) that this hypothetical picture is where we stand to­ day, and (2) that it makes no sense given such a picture to talk about a winner. Instead it makes more sense to talk about "integration" of algorithms among those identified as class-superior.

SG algorithms should surely be added to the arse­ nal of class-superior algorithms, as should incomplete and polynomial consistency enforcing (if we consider the immense class of unsatisfiable problems) [Mackworth & Freuder, 1984].

A brute-force approach of combining class-superior al­ gorithms would be by parallel integration. Namely, to run all algorithms in parallel and stop with the first one to finish [Hogg & Williams, 1994] (sequential integra­ tion is another brute-force option where algorithms are run in sequence, each being stopped after a specified amount of time). A second approach would be to un­ derstand what problem features make a given algorithm run more effectively (e.g., identify tractable classes) and to exploit those features in the combining rule yielding a case-based integration. Lastly, algorithms that address different and orthogonal aspects of the search (e.g., look­ back vs look-ahead enhancements to backtracking) can be integrated into one umbrella algorithm (unconditional integration) which may improve on each individual par­ ticipating algorithm over the union of their preferred instances. Such an integrated algorithm can replace its individual components in the arsenal of class-superior al­ gorithms for further case-based or parallel-based integra­ tion (e.g, backjumping integrated with Dynamic variable ordering (DVO), outperforms both) [Frost and Dechter, 1994]. Another proposed integration is dynamic back­ tracking that integrates backjumping with some look­ ahead ideas [Ginsberg, 1995].

Research in constraint networks in the last decade has lead to substantial understanding resulting in a list of class-superior algorithms, including backtracking­ style algorithms like backjumping, backmarking, con­ straint learning, forward-checking, dynamic variable or­ dering; structure exploiting algorithms like adaptive­ consistency, tree-clustering, and cycle-cutset decompo­ sition; as well as consistency enforcing algorithms like arc and path consistency algorithms [Dechter 1990].

To be able to exploit SG algorithms within an inte­ grated algorithm, similar understanding should be ac­ quired. Here are some sample questions: Are there poly­ nomially recognizable conditions under which SG meth­ ods are guaranteed to provide a solution and in poly­ nomial time? Can some form of preprocessing help SG methods? Can some form of learning during search help? Is there a set of enhancement schemes which are unani­ mously desirable?

In our efforts to answer some of these questions we fo­ cused on trying to improve SG performance on problems with sparse structure using two approaches: by using consistency enforcing algorithms prior to SG [Kask & Dechter, 1995] and by adapting the SG algorithm to be sensitive to the problem's structure [Pinkas and Dechter, 1995].

A note on "local vs global" search. SG methods are often called local while systematic methods are associ­ ated with "global" search. The notion of "locality" is dependent on the selected search space definition with its associated neighborhood relation. What is local in one space is global in the other. Backtracking is a lo­ cal search procedure that can be viewed as selecting the next state with the maximum gradient increase of some look-ahead function.

3 Systematic and N onsystematic Search: Matthew L. Ginsberg

There seems to be a great deal of confusion here re­ garding the question of whether or not systematic search methods can be applied to problems of interesting size. Tsang, for example, says:

Complete algorithms alone have little chance of solving realistic CSPs [constraint sat­ isfaction problems]. For example, the problem of assigning 30 jobs to 10 machines (satisfyinE certain constraints) has a search space of 10 3 nodes.

So what? Neither a systematic nor a nonsystematic approach needs to search the entire space in order to solve a satisfiable problem. Perhaps what Tsang is trying to say is simply that there is no point in trying to search enormous search spaces in their entirety. Assuming that P =/= N P, it's hard to argue with that.

The upshot of this observation seems to be that if a large problem is unsatisfiable, finding a proof of unsatis­ fiability is likely to be impossible for any approach. One can conclude from this that the principal claimed ad­ vantage of systematic methods, that they can eventually report a problem as unsolvable, is illusory.

Of course, that's simply not true. There are many large problems that are clearly unsatisfiable. Can United Airlines schedule all of its daily flights using only 17 air­ craft? Surely not - and we don't need to examine the entire space of possible schedules in order to prove it. So we can probably say the following:

Observation 1 Some - but not all - large unsatisfi­ able problems are unlikely to be solvable using system­ atic search methods. All unsatisfiable problems of any size are unsolvable using nonsystematic methods.

Contrary to the nonsystematic community's propa­ ganda, unsatisfiable problems are important, and can sometimes - not always - be solved using systematic methods.

The claimed advantage of the nonsystematic meth­ ods comes from their superior performance on satisfi­ able problems. There has been a great deal written and said about this [Langley, 1992; Minton et al., 1992; Selman et al., 1992], and I won't repeat it here. A reasonable summary appears to be that the symbolic approaches (min-conflicts, GSAT and so on) uniformly outperform nonsymbolic methods (simulated annealing, neural nets, etc.) and that:

Observation 2 When solving a satisfiable problem, it is important to be able to follow local gradients.

All of the claimed performance advantage of the stochastic or other nonsystematic methods appears to be based in their ability to move locally through the search space; systematic methods typically lack this property. 1 But nowhere is it suggested that nonsystematicity in and of itself is an attractive property; how could it be?

In spite of their inability to follow local gradients, sys­ tematic approaches are competitive with nonsystematic ones on a wide variety of problems; job-shop schedul­ ing is a typical example [Harvey and Ginsberg, 1995; Smith and Cheng, 1993; Smith, 1992]. One explanation for the performance of the systematic approach is that some measure of systematicity is needed to escape the local minima that arise in realistic problems.

When solving a mix of problems including both sat­ isfiable and unsatisfiable instances, it is clear that sys­ tematicity and the ability to follow local gradients are both important. Given the job-shop scheduling results, it appears that both can be important even if we restrict our attention to satisfiable problems alone.

1 Dechter's suggestion in this panel that "Backtracking is a local search procedure that can be viewed as selecting the . .. maximum gradient increase of some function" misses the point. We want to follow local gradients of a function that measures solution quality, not one that happens to mimic our particular search procedure.

One member of the panel (Dechter), reaching the same conclusion, suggests that the algorithms run in parallel or that we strive to "understand what problem features make a given algorithm run more effectively ... yielding a case-based integration." She suggests that algorithm development should perhaps be regarded as less impor­ tant than this integration, saying that, "The important problem is . . . how to exploit identified class-superior algorithms within one meta-framework."

This seems to me to miss the mark completely. Far more sensible would be for the constraint-satisfaction community to focus at least some of its effort on the de­ velopment of new systematic techniques that follow local gradients. Both dynamic backtracking [Ginsberg, 1993] (misdescribed by Dechter as an integration of backjump­ ing and lookahead) and partial-order dynamic backtrack­ ing [Ginsberg and McAllester, 1994] are preliminary at­ tempts in this direction. The work is much more diffi­ cult than simple and continued experimentation on ever­ larger randomly generated problems, but seems far more likely to lead to results of practical importance.

4 Stochastic Search For Model Finding: Bart Selman

Recent work on stochastic search for solving constraint satisfaction problems has shown that that such meth­ ods can be surprisingly good at finding globally optimal solutions. For example, in our work on Boolean satisfi­ ability testing we have found that, when given a set of propositional clauses, a greedy local search method can often find a truth assignment that satisfies all clauses in the input set [Selman et al., 1992]. This came as a surprise to us, since we assumed that local search meth­ ods would tend to get stuck in local optima, and thus might find good near-optimal solutions, but not com­ pletely satisfying assignments. In dealing with combina­ torial optimization problems, finding good near-optimal solutions is quite useful, but in many AI applications, near-satisfying assignments are of little value. For ex­ ample, in satisfiability encodings of planning problems, a near-satisfying assignment corresponds to a plan with a "magic" step, i.e., a physically infeasible operation. So, the fact that stochastic search methods often find completely satisfying solutions significantly widens the range of potential applications of such search methods. (See also [Minton et al., 1992].)

One obvious drawback is that stochastic search can­ not be used to prove the inconsistency of a set of con­ straints. This is a problem in applications based on the­ orem proving. One way to show that a formula a follows from a theory I:, is to show that I: with the negation of a is inconsistent. Unfortunately, since stochastic search methods are incomplete, they cannot be used to prove inconsistency, simply because these methods do not sys­ tematically explore all possible models. Therefore, in order to take full advantage of stochastic search meth­ ods, it is necessary to formulate tasks not in terms of theorem proving, but rather in terms of model finding.

It has recently been shown that systematic methods can be improved by taking advantage of principles be­ hind stochastic (or local) search. This has led some people to suggest that perhaps in the end we will be able to develop systematic methods that will be as good as stochastic search methods at showing the consistency of a set of constraints, but, in addition, can also discover in­ consistencies. As a consequence, there may not be much practical difference between model-finding and theorem proving. I will argue that this is unlikely. Mqre specifi­ cally, I will discuss the fundamental asymmetry between the task of showing a set of constraints to be consistent versus showing them to be inconsistent. Of course, this issue is closely related to the traditional distinction be­ tween NP and co-NP. I will argue that this is not just an interesting theoretical distinction but that there are good reasons to believe that this distinction has con­ crete practical consequences. The difference has been ignored in the past because of the traditional emphasis on systematic search methods, for which the distinction between NP and co-NP has no practical consequences. The recent work on stochastic search, however, suggests that there may in fact be a real difference in practical terms. Consider, for example, randomly generated sat­ isfiability problems. Stochastic search methods can be used to find satisfying assignments of hard random 3SAT formulas with up to 2500 variables. However, the cur­ rent best systematic methods can show the inconsistency of formulas with only up to about 400 variables [Craw­ ford and Auton, 1993]. Moreover, a theoretical analysis of resolution proofs has shown that the shortest reso­ lution proofs of most hard inconsistent instances are of exponential size [Chvatal and Szemeredi, 1988] . Since backtrack-style search can often be viewed as a variant of resolution, the exponential lower-bound on resolution places a hard limit on what one can expect from most backtrack-style procedures. What is needed to tackle larger formulas are more powerful proof systems, such as extended resolution, where one allows new variables to be introduced in the proof. Such systems might give us shorter proofs of the inconsistency of certain large instances; unfortunately, we do not yet know whether shorter proofs actually exist for, e.g., the hard random problems, nor do we know how to to search automati­ cally for such shorter proofs.

In summary, the recent work on stochastic search methods has revealed an interesting asymmetry: it is generally easier to find a satisfying assignment of a con­ sistent set of constraints, than to show a set of con­ straints to be inconsistent. This asymmetry suggests that it is preferable to formulate problems in terms of model-finding instead of as theorem proving tasks. A tantalizing possibility is that in order to handle certain larger inconsistent sets of constraints, we may have to develop stochastic methods that search for short proofs expressed in more powerful proof systems.

5 Case for Stochastic Search: Edward Tsang

This debate is important because research direction is of­ ten more important than the development of techniques. In the past the majority of research in constraint satis­ faction has focussed on complete search algorithms and heuristics to be employed by them [Tsang, 1993] . Given the NP-complete nature of constraint satisfaction prob­ lems (CSPs), should complete algorithms be given so much attention and incomplete search algorithms so lit­ tle? What should their roles in constraint satisfaction applications be?

The advantage of tackling problems with complete al­ gorithms is obvious. However, it is also important to re­ alize their limitations. The fact is, complete algorithms alone have little chance of solving realistic CSPs. For ex­ ample, the problem of assigning 30 jobs to 10 machines (satisfying certain constraints) has a search space of 10 30 nodes. Even if we generously assume that a very, very efficient complete search algorithm only needs to look at one in every 10 10 nodes in the search space, it still needs to examine 10 20 nodes. If a machine can examine 10 10 nodes per second (which would be incredible, and require the compatibility checks to be very inexpensive compu­ tationally), then given that roughly 3 x 10 7 seconds are available in a year, this innocent looking 30-variables10-values-each problem would require about 300 years to solve! Developing interactive systems to solve such problems by complete methods is out of the question.

Complete algorithms have other limitations. In some applications, one prefers to find optimal or near opti­ mal solutions. Complete algorithms (such as branch and bound) need to explore the whole search space to estab­ lish that the solution found is optimal, and this is lim­ ited by the combinatorial explosion problem (explained above) . Moreover, when a problem has no solution, most complete algorithms developed so far can only report that no solution exists. What one may need is a near­ solution to guide one through constraint relaxation.

All this does not mean that complete algorithms are completely useless, but that they are very limited in their applications. They could be used for small problems. When a problem is decomposable, they could be used to solve some of the subproblems. In any case, one should always evaluate the possibility of complete algorithms being able to solve the given problem within the time available before looking at other methods.

Stochastic methods that have been looked at for con­ straint satisfaction include hill climbing (HC) [Minton et al., 1992], connectionist methods [Davenport et al., 1994], genetic algorithms (GAs) [Warwick and Tsang, 1994] and simulated annealing (SA) [Ghedira, 1994; Davis, 1987].

No one should believe that the networks that peo­ ple develop in connectionist methods realistically resem­ ble the brain. Neither does any GA model evolution closely. But nature often gives us invaluable inspiration, and these methods have already demonstrated their ef­ fectiveness in various domains, including constraint sat­ isfaction.

There are many reasons why the above mentioned stochastic methods, which sacrifice completeness for ef­ ficiency, are practical answers to real life CSPs. One im­ portant advantage of these methods is that they can be designed to terminate within a specified time period. Be­ sides, domain knowledge can be incorporated into these methods-for example, knowledge can be used in the formulation of a connectionist network and in the representation to be used by a GA.

Another important issue is that the above mentioned stochastic methods have great potential to be extended to tackle constraint optimization problems and partial constraint satisfaction problems. For example, penalties for violating individual constraints and costs for assign­ ing certain values to individual variables can be incorpo­ rated into the weights of the connections and the fitness functions of a GA. In contrast, the role of problem re­ duction techniques in constraint optimization problems is far from clear, and the usefulness of most of the search strategies, including lookahead and learning, are doubt­ ful in optimization problems.

One important criteria for evaluating how promising a technique is lies in the current development of hardware. (Arguably, advances in hardware has been much more significant than advances in software in the past decade or two.) Parallel architectures have become more and more readily available. Previous research and the above example have shown that a polynomial number of pro­ cessors is not going to be sufficient to contain the com­ binatorial explosion problem in complete search meth­ ods. On the other hand, connectionism by nature can easily take advantage of the availability of parallel ar­ chitectures. GAs have also been shown to be able to exploit parallelism effectively. (e.g. see [Muhlenbein et al., 1991]).

Reliability is often the greatest concern when using stochastic methods. Indeed, some stochastic methods can easily be trapped in local optima, but connection­ ism and GAs can be very reliable. For example, [Daven­ port et al., 1994] showed that GENET has a remarkably high success rate in solving CSPs (in fact, it has never missed a solution in binary CSPs). [Pinkas and Dechter, 1995 to appear] shows that connectionist methods can be complete for certain types of problems. Quite a lot of success has been found by GAs in finding near-optimal solutions.

Real life constraint satisfaction applications often in­ volve large numbers of variables and large domains. One is often given limited time to solve such problems; e.g. a schedule may need to be produced every night. Some applications demand interactive systems to be produced. Limited by the combinatorial explosion problem, com­ plete algorithms are unlikely to be able to meet the re­ quirements of these applications.

Some applications require that optimal or near­ optimal solutions be found. In other applications, when the problem is insoluble, near-solutions may be preferred to a report suggesting that the problem is insoluble. Complete algorithms have little to offer to these require­ ments.

Stochastic methods, especially connectionism and GAs, have had a lot of success in real life applications, so they should receive much more attention by con­ straint satisfaction researchers than they have so far. The questions that should interest us are: which stochas­ tic method to use when? How reliable is a particular stochastic method? How many times does a particular stochastic method miss solutions when they exist? How successful is a particular stochastic method in finding near-optimal solutions (how close are they to the opti­ mal)? These (rather than complete search algorithms) should be the focus of future constraint satisfaction re­ search.

To summarize, complete search algorithms suffer from the combinatorial explosion problem in general and therefore cannot be expected to solve most real life prob­ lems. In order to bring constraint satisfaction research out of the laboratory and put it into applications, atten­ tion should be shifted to stochastic search in constraint satisfaction in the future.