www.ConstraintTheory.org

[The following is an excerpt from the new book, "Constraint Theory: Multidimensional Mathematical Model Management" by Dr. George Friedman.  It is being excerpted here to give you a flavor of the book and to give you a feel for how complex even the most straightforward of systems can get, and a sense of how Constraint Theory can help you get your arms around very complex, multi-dimensional models.]

A decision-making manager was authorized to initiate the preliminary design of a new system development by his board of directors.  In the true spirit of systems engineering, he realized the importance of making the best decisions as early in the system development process as possible.  Accordingly, he gathered a team of the best specialists available, along with a systems analyst to help organize the math model that he hoped would guide him to strategic systems tradeoffs and decisions.  

The chief systems engineer stressed that, in order for an “optimum design” to exist, it was necessary to define a total systems optimization criterion, T: 

 where:

P was the political index of acceptability by the board of directors,

E was the system effectiveness, and

C was the life cycle cost of the system.  

The operational chief, expressing a weariness with the overly aggressive use of new and unproved technology on most of his previous systems, wanted to stress that most of the total system cost should be applied to operations and support, not new systems development.  Thus, he contributed this limitation: 

where D, the development cost, was to be limited to 30% of the total cost.

The operations and support specialist, attempting to predict the level of cost after production and delivery were complete, provided: 

where:

S is the total support cost

X is the cost of ops and support if there were no new technology

D is the development cost for the system, including new technology.

The systems costing and estimating specialist contributed the obvious: 

taking care that all ambiguities between development, operations and support costs were clearly defined and resolved.

The reliability, maintainability and availability specialist provided: 

where: 

K₂ is a constant,

A is the probability that the system is ready when called upon.

Finally, the operations analyst provided this definition of effectiveness: 

where:

M is the mission success probability, given the equipment is available

D is the amount spent on development

D_max is the budget requested by the developers

All these inputs from the specialists were reviewed for reasonableness by the systems analyst and integrated into the “model” shown in Table 1-1.

“There appear to be no internal inconsistencies,” reported the analyst to the manager.  “Indeed, this model is enormously simpler than any I have ever dealt with for years.”

The manager, who claimed many years of systems engineering experience, observed, “I see the model is imbedded in an eight-dimensional space and is constrained by six equations.  Therefore, there should be two “degrees of freedom.”  Since I’m most concerned with the total system optimization criterion, please compute plots of T = f₇(S,P) for me.”

“Sorry, said the analyst, that is not an allowable computation on this model. Although the total model seems to have two degrees of freedom, that freedom does not exist uniformly throughout all parts of the model.  In particular, the submodel composed of relations 2, 3 and 4 is concerned only with the variables C, D and S.  Therefore, in the three-dimensional subspace of CDS, we have three equations and three unknowns; thus there are no degrees of freedom, and these variables are constrained to a point or a set of points.  Since it is such a constrained variable, S obviously cannot act as an independent variable for the computational request, T = f₇(S,P).”

The manager did not like the word, “obviously”.  “There must be something wrong with the model,” he asserted.  The specialists got huffy.

The analyst assured the manager, “There are no inconsistencies or internal contradictions in this model.  Once we’ve agreed to accept some inaccuracy due to simplification, all the equations are ‘correct’ and perfectly valid mathematically.  Each of the relations referring to CDS space was contributed by a separate specialist.  Because of this interaction between three disciplines, C, D and S are determined and can no longer be considered as variables.  Any computational request which includes C, D or S as an independent variable must be considered unallowable.  Your request was not mathematically well-posed.”

“All right,” conceded the manager, “then let me see T = f₈(M,A).”

“Sorry again,” said the analyst, “that request is also not allowable.  Consider the relations 5 and 6 which are concerned with variables S, A, E, D and M.  As we’ve just discussed, S and D are held to constant values because of the internal constraint applied from another part of the model.  By applying M and A as independent variables, we are applying external constraint to the SAEDM space.  Thus, we have only one variable, E, which is neither internally or externally constrained, and which must conform to the two equations, 5 and 6.  Having two equations with only one unknown is a clear case of local overconstraint.  This computational request is also not well posed.”

The manager sighed, “Then what computations are allowable of the form, T = f(p,q)?”

The analyst replied, “only these three: T = f₉(E,P), T = f₁₀(M,P) and T = f₁₁(A,P).  All other computations of the form T = f(p,q) either overconstrain  or underconstrain  some part of the model.”

These computations were plotted and given to the manager, along with the constant values for C, D and S.  After studying these results, the manager said, “OK, next I’d like to see some tradeoff curves.  Please show me the tradeoff between M and P, everything else being equal.”

“By ‘everything else being equal’ do you mean: ‘hold all other variables at constant values?’” asked the analyst.

“Yes, I suppose so,” responded the manager, fearing the worst.

“In that case the desired tradeoff is not allowable,” said the analyst.  “Once we agree that C can no longer be considered as a variable, E is the only variable that connects the submodel containing M with the submodel containing P.  If E is held to a constant value as you want, then the two submodels are essentially disconnected and the M vs. P tradeoff cannot be computed.”

“What tradeoffs would be allowable?”

“If we hold T only at a constant value, then M vs. P, A vs. P and E vs. P are allowable computations.”

After all the allowable  computations were performed and examined, the manager asked, “How were you able to come to your conclusions on the various computational allowabilities so rapidly?  Do you have a method that provides you special insight?”

The analyst showed the manager Figure 1-1.  “Fundamentally, I attempt to get a right-brain view of the topology of the model.  Look at relation 5 for example.  In Figure 1-1a, I represent the relation by a square and show its three relevant variables S,E,A, -- represented by circles -- connected to it.  Note that there are no arrowheads on these connections, since we don’t know in advance what the computational path will be.  In Figure 1-1b, the arrowheads indicate that S can be computed if A and E are known inputs.  Similarly, Figures 1-1c and 1-1d show the computational flow directions for the computations of A and E respectively.”

“Now, let’s expand our perspective to include relation 6 and its relevant variables, A,E,M and D.  Looking at Figure 1-2, we see that variables A and E are common to both relations 5 and 6; they do not have to be repeated.  Note that the topology has developed a little circuit.”

“Continuing in this manner, we can include the entire model, shown in Figure 1-3.  This structure is called a bipartite graph which provides a right-brained view of the topological structure  of the model of Table 1-1.  It’s really a metamodel  since it does not contain the actual equations of the original model -- just the structural information necessary to determine internal consistency and computational allowability.  As in all bipartite graphs, there are two distinct types of junctions: squares represent the relations, and circles represent the variables.  The arcs, or “graph edges” connect each relation to the variables that are relevant to it.  The “degree,” d, of each junction is defined as the number of edges which intersect it.”

Figure 1-1. A right-brain view of relation 5, introducing the concept of representing relations by squares and variables by circles, as well as demonstrating that computation can flow through the relations in many directions.

“This bipartite graph  can be considered as a network for information flow.  The squares are essentially multidirectional function generators -- or algorithmic processors -- such that any output can be generated if all the other edges provide input.  The circles are essentially scalar measurements of the value of the variable that they represent.” 

“The above use of the bipartite graph  for the representation of a math model can be easily extended to the representation of a computational request.  In the general format of a computational request, one specifies a dependent variable (the output) and a set of independent variables  and variables held constant (the input.)  These input variables essentially have constraint applied to them – in addition to the constraint applied to them by their relevant relations  – and thus additional squares are appended to the bipartite graph.

Figure 1-2. The perspective is expanded to include both relations 5 and 6, which share variables A and E.

Figure 1-3. The Bipartite Graph: A Metamodel displaying consistency and computability.

For example, assume that it is desired to have variables M and P be independent variables and variable A be held constant.  As is shown in Figure 1-4, the squares identified with “I” are appended to M and P, while the square identified with “C” is appended to variable A.  In summary, the squares representing relations of the model imply intrinsic constraint , while the squares representing inputs to a computational request apply extrinsic constraint .  To emphasize this difference, the intrinsic constraint squares have a single border while the extrinsic constraint squares have a double border.”

Figure 1-4.

“Before a computational request is made, the edges of a bipartite graph model have no directionality.  Once the request is made, the input variables now apply constraint to their neighbors and the edges take on a directionality which is determined by the request.  Essentially, the computation or constraint “flows” across the graph.”

“For treelike graphs, the rules to map the sequential propagation of information -- or computation, or constraint -- are simple in the extreme: for d edges intersecting a square, information will propagate if there are (d-1) inputs and one output; for d edges intersecting a circle, information will propagate if there is one input and (d-1) outputs.”  (See Figures 1-1 and 1-4.)  Note that a square with but a single arc intersecting it will automatically transmit constraint to the circle it is connected with, since in this case, d=1 and (d-1)=0, thereby requiring no inputs to generate its output.

“For graphs which contain circuits, mapping propagation is a little more complex.  Once we have gone as far as we can with the sequential rules above, we may require the rule of simultaneous propagation in the vicinity of a circuit: if a connected subgraph exists which contains an equal number of unpropagated squares and circles, then all its variables may be computed as if they were within a set of simultaneous equations.”

“Now I can show you how easy it was to determine the computability of your computational requests.  Looking at Figure 1-5, we can easily see that relations 2, 3 and 4 form a submodel with an equal number of squares and circles.  This denotes three simultaneous equations covering three unknown variables and we should expect to be able to solve for the three variables, converting them from unknown variables to fixed parameters.  Thus, your request, T = f₇(S,P) is unallowable since it assumes S is variable rather than a fixed parameter.  For the same reason, C and D cannot be independent variables either.  This type of constraint imposed on the model is called intrinsic because it existed even before you made any computational request.”

“Now look at Figure 1-6, which shows constraint propagating from left to right along variables C, D and S for the above explained reason.  When you requested the computation T = f₈(M,A) you established the two independent variables as a source of extrinsic constraint which propagates into the model and hopefully gives us a computation of T.  Let’s see what happens when we employ the sequential propagation rules for constraint flow.  Since M and A are extrinsic sources of constraint and D is an intrinsic source, we can satisfy the (d-1) inputs and one output rule for equation 6, thus producing a computation for variable E.  With A as an extrinsic source and S as an intrinsic source, we can satisfy the (d-1) inputs and one output rule for equation 5, thus producing another computation for variable E.  This is a case of local overconstraint, making the requested computation unallowable.”

Figure 1-5. T = f₇(S,P) is not allowable.

S cannot be an independent variable.

“Don’t get discouraged, allowable computations exist also.  Figure 1-7 displays the computational paths to compute T = f₉(E,P).  Note how the extrinsic constraint flows from E and P combine with the intrinsic flow from C to satisfy the (d-1) inputs and one output rule to equation 1, resulting in the computation of T.  Also note that the entire model was not necessary for this computation, as equations 5 and 6 were irrelevant to it.”

Figure 1-6.  T = f₈(M,A) is not allowable

because of overconstraint on E

“Figure 1-8 shows a case where both sequential and simultaneous computational flow is used to satisfy the request, T = f₁₀(M,P).  As originally constructed, the submodel comprised of the equations 5 and 6, together with their relevant variables S,A,E,D and M had two equations and four variables -- ‘two degrees of freedom’ as you put it.  Now, with the application of intrinsic constraint from S and D and extrinsic constraint from M, the extra degrees of freedom collapse to zero and we are left with two equations and two variables for this submodel.  We can expect to solve these two simultaneous equations in two unknowns to obtain both A and E.  Now applying the intrinsic constraint flow from C, the simultaneous constraint flow from E and the extrinsic constraint flow from P to equation 1, we can compute T.  Thus, this request is allowable.  In this case, the entire model was involved with the computation.”

“Figure 1-9 shows the computational paths for the allowable request T = f₁₁(A,P). The intrinsic input from S with the extrinsic input from A permit equation 5 to compute E which, using the 1 in, (d-1) out rule, propagates to both equations 6 and 1.  This input from E plus the intrinsic input from C and the extrinsic input from P permits 1 to compute T as requested.  By the way, this same bipartite graph shows that M = f₁₂(A) is also allowable.”

Figure 1-7. T = f₉(E,P) is allowable

The constraint flow rules work OK

 “Now the term, ‘tradeoffs , with everything else held equal’ is fraught with ambiguity and most often used with insufficient rigor.  Figure 1-10 displays how holding E at some constant value effectively decouples M and P into different, non-communicating subgraphs, rendering this tradeoff request unallowable.

If any combination of C, D and S were to be held constant, two types of problem emerge.  First of all, the value to which they were held constant might not agree with the values computed from the 2, 3 and 4 simultaneous equations.  Even if they did agree, then propagating constraint across the graph would yield an underconstraint  at equation 1 -- there would be an insufficient number of inputs to provide the desired computation of P.  The same underconstraint situation occurs if the variable held constant is A.  In fact, the only variable that can be held constant in order to provide the M vs P tradeoff is T.”

Figure 1-8. T = f10(M,P) is allowable

A new BNS is formed; then the flow is OK

Figure 1-9. T = f₁₁(A,P) is allowable

M = f₁₂(A) is also allowable

Figure 1-10.  M = f₁₃(P) “Tradeoff” is not allowable

holding E constant decouples M and P is allowable

THE MANAGER AND ANALYST CONTINUE THEIR DIALOGUE

The manager absorbed all these inputs soberly and after reviewing the results of his requested computations as well as others which were allowable on the original model, he complained, “I certainly can’t argue with your mathematical rigor.  But I’m still disappointed that I didn’t get more insight out of this model for my preliminary design phase -- I expected more, somehow.  It seems that whether a computation is allowable or not is like the flip of a coin.”

“It’s worse than a coin flip; much worse.  You have just observed a very common and generally unappreciated feature of most math models,” the analyst responded.  “Indeed, the vast majority of all possible computational requests on almost all models are unallowable.  Some of the author’s graduate students performed an exhaustive analysis of the likelihood of computational allowability on 6- and 8-dimensional connected models of a variety of topologies.  The results are presented in detail in Appendix A, but the general allowability likelihoods were surprisingly low.  Of the 150 computational requests made on the 6-dimensional model, less than 15% were allowable.  Of the 1078 computational requests made on the 8-dimensional model, less than 6% were allowable.  As the dimensionality of the model increases to dozens or hundreds of variables to address modern complex systems, then we can expect the allowability likelihood to diminish even further.  Needless to say, this is far worse than a coin flip.”

“But don’t lose hope, you can still ‘negotiate’ a more useful model with your team of specialists -- after all, they have an even more limited systems view than you about the structure of the model and know even less about your intended use of it.”

“For example, let’s examine the three relations, 2, 3 and 4, that caused the inadvertent source of intrinsic constraint.  Equation 4 is merely a definition between three types of cost -- this certainly seems OK.  Equation 3 is the result of experience of how support costs increase with new technology developments -- this is OK based on the experience of many past systems and assumes that there will be no investment in the development phase to reduce supportability costs.  But now look at equation 2; it is not a representation of a definition or an experienced relationship, it is a policy statement by a person who is attempting to limit development costs so he can spend more on operations and support.  If, instead of demanding that K₁ = 0.3, he permitted K₁ to merely be another variable in the model, the model dimensionality would increase to nine, and more importantly, the intrinsic source of constraint due to equations 2, 3 and 4 would be relieved (see Figure 1-11).  By this reasonable negotiation, we increase the candidates for independent variables to include C, D, S and also K₁.  In fact, the operational chief who furnished equation 2 in the first place can now run studies to determine what value of K₁ will maximize the systems level criterion, T, rather than arbitrarily fixing it at 0.3.”

“Very interesting,” admitted the manager, “I can see a constructive integration between left- and right-brain views.  It would be extremely difficult to initiate negotiations of this type without the visibility provided by your bipartite graphs. 

I’m surprised I haven’t seen this methodology before.  But most real world problems are vastly more complex than this example, are they not?  Wouldn’t analysts be driven crazy if they tried to work with snake charts that were many square meters in area?”

“You’re absolutely correct,” agreed the analyst.  “Meaningful models quickly get large and even rigorous graphs become like a bundle of snakes, as you put it, and not really amenable to the analysis by inspection shown in the example.  Figure 1-12 displays the flow graph for a specific computational request on a model that’s about p times larger than the example.  The author actually was able to do consistency and allowability analysis on this size model without using computer aids.  This was possible because the rules, and later, the theorems were developed using comprehensible models of low dimension, and then extending them rigorously to higher dimensionality.  For example, the model depicted in Figure 1-13 -- again about another p times larger than Figure 1-12 -- would undoubtedly boggle the mind of even the most focused analyst unless computer aids were available.   In order to communicate with the computer, a new construct -- called the ‘constraint matrix’ -- which has all the information inherent in the bipartite graph will be employed.”

Figure 1-11. Changing K₁ from a constant to a variable permits C, D, S, and K1 to act as independent variables in computations.

Figure 1-12. A sequential computational flow in a model about p times larger than the example.

“Is there a name to this process?  How difficult would it be to become proficient in this technique?  What would the mathematical prerequisites be?” asked the manager.

“The name of the process is ‘Constraint Theory ’.  It is based on the author’s PhD dissertation [2] and subsequent published papers [3].  The only mathematical prerequisites are the simplest 5% of set theory and graph theory.  Just read this book; it is written for practical engineers, not professors or journal editors.”

Figure 1-13. A model about another p times larger certainly invites computer assistance.

[ Home ]

Copyright © 2005 Well Posed Systems, Inc.
Last modified: April 05, 2005