in A and would normally be rather small. Compared to m(m + n) for SM, this yields the one aspect favoring M1. One can take about (m + n)/k steps in the space of M1 for each step in the space of SM. However, the thrashing around necessary at each point to obtain a positive step will largely nullify this advantage.

This list of differences suggests constructing a sequence of methods that extend from M1 to SM, with decreasing spaces and operators and increasing cost per step (to pay for the additional sophistication). Much of the gain, of course, will come without changing problem spaces, but from acquiring better operator selection. There may be relatively few substantial changes of problem space. Figures 10.14 and 10.15 provide

Problem statement for M2, the monotone objective method
Given: the conditions of M1, plus

Find:

ƒ is monotone in the feasible region.

in the feasible region such that z is maximum.

Problem space PS2, main hill climbing

Elements: { on boundary of feasible region (at least one x = 0 or g = 0)}. Initial element: xo in feasible region (not obtained by M2).

Operators: {x}, where the point on boundary given by M2*.

x'

Initial element: x, given by M2 operator.

Operators: {Ax, with appropriate sign}, where ' = x + Ax.

Problem space PS1 for M1

Used as backup when PS2 terminates without optimum.

Figure 10.14. M2: monotone objective method.

Problem statement for M3, the consistent exchange problem

Given: the conditions of M2, plus

if an x is exchanged for other variables by moving along a maximal boundary, then Az has a consistent sign.

Find: in the feasible region such that z is a maximum.

Problem space PS3, main hill climbing

Elements: { on the maximal boundary of feasible set; i.e., no x can be changed to increase z, holding other x fixed}.

Initial element: xo, a feasible solution on the maximal boundary (not

obtained by M3).

Operators: {x}, where ' the point on the maximal boundary given by M3*.

Problem statement for M3°, M3-operator method

Given: the condition of M3, plus

is on a maximal boundary;

x = {x}.

Find: on the maximal boundary, such that exchange for x to increase

z is not feasible;

z increased.

Additional assumption for efficiency:

any system of k equations, {g(x) = 0}, can be solved for any set of k variables with the others fixed.

Problem space for M3*

Elements: {x}.

Initial element: x, given by M3 operator.

Operators: {Ax, with appropriate sign} and {▲ī, subsets of {x}}, where π' = x + Ax.

Figure 10.15. M3: consistent exchange method.

two that seem to reflect some of the major boundaries to be crossed in getting from M1 to SM.

Figure 10.14 shows method M2, which adds the assumption that the objective function, f, is monotone in the feasible region. In the LP problem of/ox is constant, but this is not required to justify the main conclusion; namely, that if a given change in a varible is good, more change in the same direction is better. The effect of this is to create new operators and, through them, a new space. The basic decision is always to drive a varia

ble to a boundary (in the direction of increasing z, of course). Thus the space for M2 becomes the boundary set of the original space for M1 (those points where at least one of the constraints, including the x≥0, attains zero). The operators in the space of M2 are full steps to a boundary (what are sometimes called macromoves in artificial intelligence). Now, finding the boundary is still a problem, although a more manageable one. Thus M2 has a second problem method, M2*, for this purpose. As described in Fig. 10.14 it can be a simple hill climber.

An additional strong assumption has been made in the procedure of M2, namely, that only changes in a single variable, x, will be considered. This reduces the number of operators, as well as making the operator submethod M2* simpler. It is not justified by the assumptions of the problem statement, however, and consequently M2 will terminate at suboptimal positions where no single variable can be changed to increase z without decreasing some other variables. (This is often called the maximal or the Pareto optimum set.) Rather than relax the operators to a wider class, the original method, M1, is held in reserve to move off the maximal set. (However, if done with small steps, this is extremely inefficient for the LP problem, since the system just jitters its way slowly up a bounding plane.)

The description of M2* gives an additional assumption: each equation g (7) can be solved directly for any x, given that the values of the other 's are determined. This permits direct calculation of the extreme value of ≈ on a boundary that is maximal. Slightly stronger conditions on the g's allow determination of the first constraint to become binding, without multiple evaluations.

Figure 10.15 shows method M3, which adds the assumption that the exchange rate (e) always has a consistent sign as one moves along the feasible region, in response to introducing a variable x (what we have called exchanging). Again, in the LP problem e is constant, but this is not required to justify the main conclusion: that in a maximal situation, if adjustments are made in other variables to allow a particlular variable to increase, and the gain from the exchange is positive, it will always be positive; hence the new variable should be exchanged for as much as possible, namely, until another boundary is reached. This assumption not only allows a better way of dealing with the maximal cul-de-sac than does M2, with its regression to M1, but also permits the problem space to be changed radically a second time.

The elements of the space now become the set of maximal points, thus a small subset of the space of M2. The operators remain the same; the individual variables. The application of an operator again cor

responds to the solving of a subproblem, hence is accomplished by a submethod, M2*. The problem is as follows: given x (with a positive exchange rate), to advance it as far as possible. This means solving the constraints simultaneously for the variables, so as to remain on a boundary. As a change in the selected x is made, the current x moves off the maximal boundary by violating either the constraints or maximality. Adjustments must be made in the other x's to restore these conditions. What the new clause in the problem statement provides is not a way of making the adjustments, but a guarantee that if a change is once found that does increase z (after adjustment) it should be pushed to the limit. We have not described M3*, other than to indicate the available operators. At its most general (i.e., assuming no other information), it requires a two-stage process, one to discover a good direction and the other to push it. The latter is again a two-stage process, one to change the selected and the other to make the adjustments. We have included an additional assumption, similar to the one for M2*, that a direct way exists of solving systems of contraints for some variables in terms of others. This clearly can make an immense difference in the total efficiency of problem solving but does not alter the basic structuring of the task. M3 is already a recognizable facsimile of SM. The space has been cut to all subsets of the variables, although the final contraction to subsets of m variables has not occurred. (It is implicit in the problem statement of M3, with some mild conditions on the g's, but has not been. brought out.) The operators of M3 and SM are the same. More precisely, they are isomorphic-the process of applying an operator is quite different in the two methods. There are still some steps to go. The kinds of methods that are possible for the operator need explication. They are represented in M3* only by the assumption that systems of equations can be solved. But the schemes in SM use special properties of linear systems. Similarly, we have not explored direct calculation of the exchange rates, with the subsequent replacement of comparison in the main method by comparison in the operator, to avoid expensive computation.

We have not carried this example through in complete detail, nor have we established very many points on the path from a crude hill climber to SM. The two points determined are clearly appropriate ones and capture some of the important features of the method. They are not unexpected points, of course, since linear programming is well understood. The viewpoint underlying the analysis is essentially combinatorial, and such aspects have been thoroughly explored (e.g., see [23]). If these intermediate problems have any peculiar flavor, it is that they become established where the search spaces change, and these need not always

correspond to nice mathematical properties, abstractly considered. Thus convexity is not posited and its implications explored; rather a change of search space is posited and the problem statement that admits it sought.

A single ancestral lineage should not be expected. Just as theorems can have many proofs, so methods can have many decompositions of their information. In fact, in one respect at least the line represented by M2 and M3 does violence to SM. It never recognizes the shift of problem into a set of equality constraints with the consequent change in dimensionality. Thus, the g's and the x's are handled separately, whereas it is a very distinct feature of the simplex procedure that it handles them uniformly. One could easily construct another line starting from SM, which would preserve this feature. (It would face a problem of making the transition to M1.)

The examples selected-linear programming and matrix inversionare certainly ones that seem most amenable to the kind of analysis we have proposed. If we considered methods, say, for determining inventory levels, the story might be different. Nevertheless, perhaps the case for continuity between weak and strong methods has been made plausible.

5. HUMAN BEHAVIOR IN ILL-STRUCTURED PROBLEMS

In the two issues discussed so far-the existence of weak methods, and the continuity between weak and strong methods-we have not seemed to be dealing directly with ill-structured problems. To re-evoke the concern of Reitman, the problem statements that we have exhibited seem quite precise. (Indeed, we took pains to make them so and in a more technical exposition would have completely formalized them.) According to our hypotheses the world is always formalized, seen from the viewpoint of the methods available, which require quite definite properties to operate. A human problem solver, however, would not feel that a problem was well structured just because he was using a method on it. Our second hypothesis identifies this feeling with the low power of the applicable methods.

The concern just expressed is still well taken. If we examine some problem solvers who are working on "really ill-structured" problems, what will we find? They will necessarily be human, since as noted earlier, men are the gatekeepers of this residual class of problems. Thus we cannot observe their problem-solving processes directly but must infer them from their behavior.

To have something definite in mind consider the following problem solvers and tasks: