System and method for representing and solving numeric and symbolic problems

Abstract

A system and method for representing and solving problems which allows a user to enter objects and attributes, and to form a table of at least two dimensions having object-attributes pairs. An object hierarchy is then implemented using the entered objects. The system allows the user to enter constructs to represent relationships among the object-attribute pairs, and also to enter objectives and constraints for the problem. The system allows the user to solve the problem manually or automatically by the system. A score is maintained reflecting how closely the constraints of a problem are to being satisfied and the degree of progress in the direction of the stated objectives of the problem. The system allows representation of hybrid numerical and symbolic problems, and provides solutions to linear or non-linear, discrete or continuous, and feasible or non-feasible constraint satisfaction and optimization problems.

Claims

What I claim is:

1. A machine system for representing a problem, comprising:

an I/O device for entering information into the machine system in the form of constructs, objects and attributes;

a digital computer for receiving and manipulating said constructs, objects and attributes form said I/O device, said digital computer comprising:

an electronic memory device for storing said constructs, objects and attributes;

first means for parsing and translating said constructs entered by said I/O device into a machine evaluable form;

a tabular representation implementer, wherein said tabular representation implementer automatically defines a tabular representation, wherein said tabular representation contains cells corresponding to object-attribute pairs;

second means for automatically defining dependencies from said machine evaluable form;

third means for automatically attaching said constructs to said object-attribute pairs and for attaching to said object-attribute pairs said dependencies of said second means;

fourth means for allowing said object-attribute pairs to inherit said constructs and/or dependencies from other object-attribute pairs; and

fifth means for operating on related object-attribute pairs as a function of said defined constructs and dependencies.

2. The machine system of claim 1, wherein said tabular representation defined by said tabular representation implementer comprises N dimensions, where N>1.

3. The machine system of claim 11, wherein a single one of said attributes in said tabular representation is used.

4. The machine system of claim 1, wherein said constructs entered by said I/O device include constructs selected from the set of formulas, triggers, rules, goals and critics.

5. The machine system of claim 4, wherein evaluation of said rules by said fifth means for operating take precedence over evaluation of conflicting formulas or triggers, and wherein said triggers take precedence over evaluation of conflicting formulas.

6. The machine system of claim 4, further comprising means for attaching a value to one of said object-attribute pairs, said object-attribute pair additionally associated with a formula or a trigger.

7. The machine system of claim 1, wherein said constructs entered by said I/O device are expressed using object variables.

8. A machine system for representing a problem, comprising:

an I/O device for entering one or more constructs, objects and attributes into the system, said constructs including defined targets and/or objectives of the problem;

a digital computer for receiving and manipulating said constructs, objects and attributes from said I/O device, said digital computer comprising:

an electronic memory device for storing said constructs, objects and attributes;

first means for automatically forming form said one or more objects and one or more attributes a table of at least two dimensions having object-attribute pairs;

second means for automatically implementing an object hierarchy using said one or more objects entered in said first means;

a parser, wherein said parser parses and/or interprets said one or more constructs, to form one or more procedural attachments;

third means for automatically attaching said one or more procedural attachments to said object-attribute pairs formed by said first means, to form dependencies between said object attribute pairs;

fourth means for entering a value into a first object-attribute pair;

fifth means for automatically changing the value of a second object-attribute pair related by said dependencies to a second object-attribute pair upon a change in value of said first object-attribute pair;

sixth means for changing the values of all object-attribute pairs that are related by said dependencies to said second object-attribute pair; and

seventh means for automatically indicating how close said targets and/or objectives of the problem are to being achieved.

9. The machine system of claim 8, further comprising means for representing targets and/or objectives to express relationships among any number of object-attribute pairs.

10. The machine system of claim 8, further comprising means for allowing said object-attribute pairs to inherit said targets and/or objectives from other object-attribute pairs.

11. A machine system for representing problems, comprising:

a digital computer for receiving and manipulating values of object-attribute pairs, said digital computer comprising:

an electronic memory device for storing said values of said object-attribute pairs;

a tabular representation of at least two dimensions divided into rows and columns, wherein intersections of said rows and columns are represented by cells corresponding to said object-attribute pairs;

means for associating a value with a first object-attribute pair;

means for automatically associating an object-oriented dependency and/or a rule with said first object-attribute pair, wherein said object-oriented dependency and/or rule causes said value within said first object-attribute pair to affect a value within a second object-attribute pair; and

means for allowing said first object-attribute pair to inherit said object-oriented dependency from a third object-attribute pair.

12. The machine system of claim 4, wherein said rule embodies messages which, when said rule is fired, are sent to a user,

said rule not affecting said value in said second object/attribute pair.

13. The machine system of claim 11, further comprising means for representing said object-oriented dependencies from a plurality of said first object-attribute pairs to said second object-attribute pair.

14. The machine system of claim 11, further comprising means for associating said object-oriented dependency representing relationships from a plurality of said first object-attribute pairs to said second object-attribute pair.

15. The machine system of claim 11, further comprising means for representing said object-oriented dependency from said second object-attribute pair to a plurality of said first object-attribute pairs.

16. The machine system of claim 11, further comprising means for associating said object-oriented dependency representing relationships from said second object-attribute pair to a plurality of said first object-attribute pairs.

17. The machine system of claim 11, further comprising means for representing rules to express relationships among any number of object-attribute pairs.

18. The machine system of claim 11, further comprising means for allowing a plurality of first object-attribute pairs to inherit said rules from a plurality of said second object-attribute pairs.

19. A machine system for solving a problem, comprising:

an I/O device for entering information into the machine system in the form of user-defined targets and/or objectives;

a digital computer for receiving and manipulating said user-defined targets and/or objectives from said I/O device, said digital computer comprising:

an electronic memory device for storing said user-defined targets and/or objectives;

first means for creating a combined objective function and constraints representative of said user-defined targets and/or objectives of the problem, said combined objective function containing decision variables capable of accepting a value;

second means for moving the value of said combined objective function in a given direction by manipulating said values of said decision variables;

third means for detecting active constraints;

fourth means for causing said combined objective function to move parallel to said active constraints;

fifth means for detecting non-linearity of said active constraints; and

a lift factor to allow said combined objective function to accurately parallel said active constraints.

20. A method for operating a digital computer to represent and solve a problem, said digital computer having an electronic memory device for storing said problem, comprising the steps of:

(1) entering objects and attributes to create a tabular representation of N dimensions in the electronic memory, where N>1;

(2) automatically forming object-attribute pairs form said objects and said attributes of step (1);

(3) automatically implementing an object hierarchy using said objects and said attributes of step (1);

(5) entering constructs using an I/O device;

(6) parsing and translating said constructs of step (5) into a machine evaluable form;

(7) automatically forming procedural attachments from said evaluable constructs of step (6);

(8) automatically attaching said procedural attachments of step (7) to said object-attribute pairs of step (3);

(9) entering a value into selected ones of said object-attribute pairs of step (3); and

(10) automatically varying values of said selected ones of said object-attribute pairs of step (3) to find at least a best balanced solution to the problem.

21. A machine system for representing problems, comprising:

a digital computer for receiving and manipulating values of cells, said digital computer comprising:

an electronic memory device for storing said values of said cells;

a tabular representation of at least two dimensions divided into rows and columns, wherein intersections of said rows and columns are represented by said cells;

means for automatically associating a value with a first cell;

means for automatically associating an object-oriented dependency and/or a rule with said first cell, wherein said object-oriented dependency and/or rule causes said value within said first cell to affect a value within a second cell; and

means for automatically representing dependencies from said first cell to a plurality of said second cell.

22. A machine system for representing and solving problems, comprising:

an I/O device for entering information into the machine system in the form of objects, attributes, and constructs including formulas, triggers and rules;

a digital computer for receiving and manipulating said constructs, objects and attributes from said I/O device, said digital computer comprising:

an electronic memory device for storing said constructs, objects and attributes;

a first module for parsing and translating said constructs entered by said first means into a machine evaluable form;

a second module for automatically defining a tabular representation where said tabular representation contains cells corresponding to object-attribute pairs;

a third module for automatically defining dependencies form said machine evaluable form;

a fourth module for automatically attaching said constructs to object-attribute pairs and for attaching said dependencies of said fourth means;

a fifth module for allowing said object-attribute pairs to inherit said constructs from other object-attribute pairs;

a sixth module for automatically operating on related object-attribute pairs as a function of said defined constructs and dependencies;

a seventh module for automatically utilizing weak and strong problem solving methods in conjunction with said dependencies and chosen values of said object-attribute pairs to find at least a best balanced solution to the problem; and

an eighth module for using heuristics for dynamically interleaving said weak and strong methods.

Description

BACKGROUND TO THE INVENTION

1. Field Of The Invention

This invention relates to a system and method for representing and solving complex problems. More specifically, the present invention relates to a system and method for representing and solving constraint satisfaction and optimization problems. Still more specifically, the invention relates to a system and method for representing and solving constraint satisfaction and optimization problems using an integrated combination of operations research and artificial intelligence techniques.

2. Related Art

Constraint satisfaction and optimization problems, in general terms, involve problems where an attempt is made to achieve certain goals, while maintaining the value of specified variables within designated boundaries. Although such problems have been studied for many years, many have long been considered very difficult if not impossible to represent and solve due to their complexity.

With the arrival of computer technology, it became possible to solve many of these previously unsolved problems. This was accomplished by customized computer programs that were developed to solve a specific problem or perhaps a particular class of constraint satisfaction and optimization problems. However, even with the advent of computers, many constraint satisfaction and optimization problems are still considered too difficult to easily and/or accurately represent and solve. One major reason for this relates to the present techniques used to represent and solve these problems.

There are two traditional approaches used to represent a constraint satisfaction and optimization problem. The first is a numerical approach used by mathematicians and those in the field of Operations Research (OR). This approach involves building mathematical models expressed in numerical terms using algebraic formulas or calculus.

The second traditional approach involves representing the problem symbolically. In other words, symbols, mnemonics, rules and predicates are used for expressing operations and operands, rather than mathematical equations. This approach is used by those working in the domain of artificial intelligence (AI), which is a discipline of the computer science field.

The approach that will work best for a particular problem will depend on the specific problem at issue. In general, each approach has advantages and disadvantages. An advantage of the numerical approach is that representation of a problem is concise, and has relatively little ambiguity. Also, there exist efficient procedures for solving some of the problems that can be expressed purely numerically.

A major disadvantage with the numerical approach is that many types of problems cannot be completely represented in the numerical form required by existing methods. When such a problem comes up, mathematicians in OR represent as much of the problem as possible numerically. That which they cannot represent numerically is temporarily ignored. After the represented portion of the problem is solved, the mathematicians ask themselves "what would the solution to the problem be if the previously ignored portions caused the problem to behave one way, or caused it to behave a different way, etc." Thus, the unrepresented portions of the problem cause the overall problem solving process to become one of trial-and-error. Such a process wastes much time and effort.

An advantage of the symbolic approach used in AI is that it is easier to represent certain types of problems which are more easily thought of symbolically (that is, in terms of rules and statements). An example of such a rule might look like "if Bob and Mary are married, schedule them to work on the same day." This type of problem, while easily represented symbolically, would be quite difficult to represent numerically.

The symbolic approach has some disadvantages versus the numerical approach. That is, it is difficult to apply numeric optimization procedures to a model which is stated in non-numeric terms. There are fewer general purpose procedures available for the solution of problems stated in terms of arbitrary predicates and rules.

In summary, the numerical approach more easily allows numerical components of a problem to be represented than the symbolic components, while with the symbolic approach, the symbolic components are more easily represented than the numerical components. Since real-world constraint satisfaction and optimization problems usually contain both "hybrid" approach which allows easy representation of problems having both of these components.

Although a single "hybrid" approach described above would be of great practical value, serious steps have not been taken toward developing a general purpose problem solver which can represent constraint satisfaction and optimization problems having both symbolic and numerical components. In most cases, such a hybrid approach has only been written about at the highest levels of conceptualization; see Simon, H. A., "Two Heads Are Better Than One: The Collaboration Between AI and OR", Interfaces, Pp. 8-15, Jul.-Aug., (1987). While the hybrid approach is still largely theoretical, there are a few examples where it has been implemented. However, these implementations relate only to the representation of specific problems. One example was used in a doctoral dissertation by Robert Donnelly at The University of Delaware (1988). Donnelly represented a problem called Aggregate Planning using a hybrid of numerical and symbolic approaches. This problem involved the scheduling of people, inventory, shifts, etc. As indicated above, the techniques Donnelly used to develop this representation only work for this particular problem. If the problem is changed slightly, the representation will no longer be effective, and a solution will not result.

Another example of implementation of the hybrid approach was reported in an article by Vasant Dhar; see Dhar, et al.. "Integer Programming vs. Expert systems: An Experimental Comparison", Communications of the ACM, Pp. 323-336, Mar. (1990). In this article, a hybrid approach was used to represent a specific employee scheduling problem. Again, this approach was not capable of being used to represent and ultimately solve other types of constraint satisfaction and optimization problems.

Thus, a tool which can easily represent many different types of problems having both numerical and symbolic components would be very useful. However, prior to the development of the present invention, no such general purpose tool has been available.

An example of an attempt to combine numerical and symbolic components is a product developed by mdbs, Inc., called Guru. Guru allows one to employ a spreadsheet environment (numerical component) as an interface to an expert system (symbolic component). However, because the expert system and spreadsheet portions are not homogeneously integrated, and because the product does not make use of OR techniques, it is still difficult, if not impossible, to represent and solve a multitude of constraint satisfaction and optimization problems. (There are commercial attempts to combine OR techniques and spreadsheet environment by providing add-on programs, which can solve linear programming, to commercial spreadsheets. An example of such an attempt is "What's Best" by General Optimization of Chicago, Illinois. These attempts, which are targeted at making the representation of the problem easier, use only numerical (spreadsheet) components. They are also targeted at representing and solving a limited class of problems, such as linear programming problems).

In addition to the difficulties involved with representing a hybrid numerical/symbolic constraint satisfaction and optimization problem, the actual solving of such a problem is also very difficult. Traditionally, once such a problem is represented, an expert analyzes the problem and decides which of a multitude of algorithms is best suited to solve it.

At present, programs exist to assist in solving certain types of problems. These programs are generally neither readily available nor user-friendly. An example of such a program is "Lindo" by Linus Schrage at the University of Chicago (available from Scientific Press, Redwood City, Calif.). Lindo will solve a problem if it is real and linear, and some specific integer programming problems. Lindo cannot solve general integer programming problems. For these problems there are no efficient algorithms. That is, even for the best known algorithms, the solution time grows exponentially with the size of these problems.

If the problem to be solved is non-linear, it becomes even more difficult to find and use a single algorithm. Therefore, it may be desirable to use several different algorithms to completely solve a particular non-linear problem.

Automated analysis of a problem and selection of an appropriate algorithm to effect a solution has been set forth in a dissertation by Jae Sik Lee at the Wharton School of Business (1989). However, once an algorithm has been selected, it is not changed during the solving process. Thus, solving becomes inefficient, and in some cases impossible by this method, since different algorithms may need to be used at various stages of the solving process. This is especially true where the problem itself changes dynamically during the solution process as may occur when the model is refreshed by new sets of values from an on-line data source.

In addition to the difficulty with the selection of an algorithm to effect a solution to a problem, there is also a problem with managing constraint satisfaction and optimization problems which are infeasible. By infeasible, it is meant that the problem has no solution which satisfies every constraint. In the real world, many problems which people attempt to solve turn out to be infeasible. Nonetheless, even when a problem is infeasible, the designer of the problem would often want to have the "best" answer possible, even if there is no absolute solution.

An example of the type of problems which are often infeasible are problems to select stocks for purchase. The goal of this kind of problem might be to buy stocks with a high rate of return and a low risk. Depending upon how "high" and "low" are defined, this problem may have no solution, since there may be no stocks yielding a "high" enough return and having a "low" enough risk. Thus, when people model real problems, they often include constraints which make feasible solutions impossible.

In the field of OR, infeasibility is traditionally handled by having an expert remodel the problem and manually trying various mathematical techniques until a model of the problem can be created which admits a feasible solution. Thus, the approach is to modify the constraints of the problem until the problem becomes feasible. Using the above example, the rate of risk may be increased or the yield decreased until a stock is found to exist which provides a solution to the problem. However, in the business world, the "best" answer (best balanced solution) to the original infeasible problem may nonetheless be of great value. The difficulty is that the mathematical end of OR is very literal in nature, and is traditionally not concerned about partial or "best" answers. Either a feasible solution exists, or the result is deemed worthless. This philosophy and the general techniques used in OR are thus not conducive to solving infeasible problems.

The field of AI does not have the same kind of general techniques permeating through it the way that OR does, since the techniques used have been problem-specific. Thus, with AI, there are few pervading philosophies that would inhibit the search for "best" solutions where no feasible solutions exist. However, for the very reason that there are no traditional techniques or philosophies, it is still very difficult to solve infeasible problems.

In addition to being poorly equipped to handle infeasible problems, the traditional approaches of both AI and OR consider only one goal at a time. For example, consider the above noted problem to find a stock having both a high rate of return and a low risk. This is an example of a problem having two goals. Traditionally, the way to solve such a problem is to concentrate on one goal at a time. Thus, one would either pick a level of risk and compute the stock having the highest rate of return, or pick a level of return and compute the stock having minimum risk. If both goals are not considered simultaneously, it becomes difficult to find an optimal solution of a complex problem (or a best balanced solution if the problem is infeasible). Business problems in particular often create a constant conflict between multiple goals.

Some specialized systems called "Multiple Goal Programming Systems" exist which are designed to solve problems with multiple goals. These systems require that weights be assigned to individual goals either from explicit information, or from direct user input. These systems are usually used as part of linear programming packages, and as such are not complete problem solving systems, nor would they be good for solving non-linear problems. In addition, a substantial amount of user interaction is required in interacting with the system. Consequently, these systems become very inefficient when dealing with large, complex problems.

Thus, what is needed is a robust problem solving tool which can efficiently represent and solve constraint satisfaction and optimization problems having both numerical and symbolic elements, involving both continuous and integer quantities, and involving any number of objectives and constraints, using a variety of problem solving techniques, and which can find an optimal solution to feasible problems or a best balanced solution to infeasible problems. The present invention provides such a tool.

SUMMARY OF THE INVENTION

In summary, the present invention is a system and method for (a) representing and (b) solving problems. A feature of the present invention is that the representation portion may be implemented and used separately and apart from the solving portion, and vice versa. With regard to representation of the problem, the present invention allows a user to enter objects and attributes, and to form a table of at least two dimensions having object-attribute pairs. An object hierarchy is then implemented using the entered objects. Arithmetic and logical relationships between object-attribute pairs can be defined by entering constructs (such as goals and formulas). Once entered, the constructs are parsed, translated, and then attached to an appropriate entity.

The present invention also allows the user to enter values into the object-attribute pairs. In addition, the constructs can cause specified object-attribute pairs to change in response to a change in value of some other object-attribute pair. Since a change in one object-attribute pair can have an effect on another, which can then affect another, etc., the present invention provides a mechanism for propagating these changes in a logical order.

The problem solving portion of this invention is designed to maintain a score which reflects both how closely constraints of a problem are to being satisfied and the degree of progress in the direction of the stated objectives of the problem. The invention then attempts to achieve the best possible result. To do this more quickly and efficiently, the present invention utilizes numerical methods called weak and strong methods. Further, the present invention uses methods at times interleaving the two approaches.

The present invention is most effective and useful when both the representation and problem solving portions are used together in an integrated fashion.

BRIEF DESCRIPTION OF THE DRAWINGS

Various objects, features, and attendant advantages of the present invention can be more fully appreciated as the same become better understood with reference to the following detailed description of the present invention when considered in connection with the accompanying drawings, in which:

FIG. 1 is a high-level diagram of the environment of one embodiment of the present invention.

FIG. 2a is a high-level diagram of one embodiment of the present invention broken down logically into two portions.

FIG. 2b is a high-level diagram of the environment of an embodiment of the present invention using a local area network.

FIG. 3 is a high-level diagram of the environment of an embodiment of the present invention using multiple processors.

FIG. 4 is a high-level diagram of the structure of the Problem Representation Facility (PRF).

FIG. 5 is a diagram of available constructs.

FIG. 6 is a diagram demonstrating an n-dimensional tabular representation.

FIG. 7 is a diagram of the structure of the object-oriented language with inference engine.

FIG. 8 is a diagram of the operation of the PRF.

FIG. 9a is a diagram of the entire object hierarchy for a small three-dimensional example.

FIG. 9b is a diagram of the order that the object hierarchy is searched using a four-dimensional example.

FIG. 10 is a diagram of the operation of how a construct is parsed, translated, and attached.

FIG. 11 is a diagram showing how a construct is represented internally.

FIG. 12 is a diagram showing the operation of the dependency machinery.

FIG. 13 is an expanded diagram showing the operation of the propagation algorithm of FIG. 12.

FIG. 14 is an expanded diagram showing the operation of the propagation of the recomputation of FIG. 13.

FIG. 15 is a high-level diagram of the Problem Solving Engine (PSE).

FIG. 16 is a diagram of the operation of the weak methods.

FIG. 17a is an expanded diagram showing the operation of the star search of FIG. 16.

FIG. 17b is an expanded diagram showing the operation of the stopping criteria of FIG. 16.

FIG. 18 is an expanded diagram showing the operation of the generation of a new point of FIG. 16.

FIG. 19 is a diagram of the operation of the strong methods.

FIG. 20 is an expanded diagram of the operation of the optimization of FIG. 19.

FIG. 21 shows the structure of the PSE.

FIG. 22 shows the structure of the weak methods.

FIG. 23 shows the structure of the strong methods.

FIG. 24 is an example of the tabular representation used in the present invention, and a Sample Problem.

FIG. 25 shows an example of a formula used in the Sample Problem.

FIG. 26 shows an example of a trigger used in the Sample Problem.

FIG. 27 shows an example of a rule used in the Sample Problem.

FIG. 28 shows an example of a critic used in the Sample Problem.

FIG. 29 shows an example of an objected used in the Sample Problem.

FIG. 30 shows an example of a target used in the Sample Problem.

FIG. 31 shows the Sample Problem being solved.

FIG. 32 shows a third dimension being added onto the Sample Problem.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

I. General Overview

This invention relates to a system and method for (a) representing and (b) solving complex problems. More specifically, the present invention is capable of representing and solving constraint satisfaction and optimization problems having symbolic and numerical components.

It should be understood that the representation portion of this invention may be implemented separately from the problem solving portion, and vice versa. In general, the invention is most effective and advantageous when both the representation and the problem solving portions are used together in an integrated fashion.

One of the significant features of the present invention is that it is very robust, in that it will always provide a result to a problem. If the problem is infeasible, the present invention provides at least what it considers the "best balanced solution" (and can provide an optimum solution where possible, given enough time). As indicated above, the "best balanced solution" is the result that the present invention has calculated to be "closest" to solving the problem.

The present invention performs the above-noted function by viewing the constraints of a problem as something that can be violated. Thus, constraints are treated as goals rather than absolute guidelines. The present invention tries to get as close to the goals as it can, and will always come up with a result.

An advantage of treating constraints as goals is that it allows the present invention to violate these constraints. This allows the present invention to find solutions which may be somewhat outside the bounds of the constraints, but which a user would nevertheless find significant.

For example, assume that a problem to optimize production has as one constraint that a maximum of 200 man-hours per week can be used on a certain project. Also assume for purposes of this example that 205 man-hours would increase production by 25%, and that a user has indicated that the constraint of 200 man-hours is not a critical constraint. If constraints are never violated at all, then the fact that the extra 5 man-hours would increase production so dramatically would never be ascertained. The present invention allows these constraints to be violated when it detects that great improvement toward achieving goals would occur by doing so. The fact that the extra 5 man-hours produced such extreme results would probably be of great interest to a manager, even though the constraints set for the problem were somewhat violated.

Regarding infeasible problems, treating the constraints as goals also allows the present invention to obtain a best balanced solution. Where a problem is infeasible, the present invention will attempt to produce a result having a specified amount of variation from the goals (the goals for these problems being unattainable). Thus, to obtain the best balanced solution, constraints are permitted to be violated. In a preferred embodiment, the amount of "violation" (that is, the precision to which the constraints are to be regarded) can be scaled and weighted by the user.

It should be noted that "scaling" indicates the precision of values with which the user is concerned, while "weighting" taking into account the scale of the values). As an example of scaling, a problem can be entered into the present invention which tries to achieve a return rate between 9% and 12% with a precision of 0.1%, while also trying to receive revenues in the range of $1,000,000 to $1,500,000 with a precision of $1,000. As an example of weighting, a problem can also be entered into the present invention where there is a "normally" weighted constraint which, for example, mandates that of 12 employees only 3 work during a given shift. This constraint will have lower priority than a "critically" weighted constraint which, for example, could mandate that no employee will be scheduled for more than 8 hours on a given shift. Objectives can be scaled and weighted in a similar way. Constraints (entered as "targets" by a user) and objectives are the way goals are entered into the present invention, and will be discussed further below.

Another advantageous feature of the present invention is that it can consider multiple goals (objectives and constraints) simultaneously. This allows for the solving of problems in which goals are in conflict. The stock purchase problem is an example of a goals-in-conflict problem. Further, since the best balanced solution to an infeasible problem is at least partially a subjective one, the present invention gives the user the ability to attain a more satisfactory result by allowing the user to change the weighted importance of the goals of the problem. Thus, one goal can be relaxed in favor of another, until the user has achieved a desired result. The best balanced solution automatically produced is what the present invention calculates to be the best result (that is, the result which minimizes the total, weighted and scaled violations of the constraints of the problem, and achieves the best values for the objectives given these constraints).

In performing the above-noted functions, the present invention uses a combination of object-oriented and rule-based methods. In using object-oriented methods, the present invention allows specified entities to be entered as "objects", and then allows these objects to have certain properties or behaviors based upon "attributes" which are assigned to the objects. Traditionally, a typical example of an object which might be used in a problem in the automobile industry might be "automobile", and its attributes might consist of "price", "acceleration", "weight", etc. The specific way in which the present invention creates relationships among objects is discussed below.

In the present invention, the objects are set up hierarchically so that objects which are lower in the object hierarchy can inherit the behaviors (associated with "attributes") of objects higher in the hierarchy. In this way, behaviors which are universal to some or all of the objects need be defined only once, with the objects lower in the hierarchy inheriting the behaviors of those higher in the hierarchy.

Using the above example, objects below "automobile" in the hierarchy might be "Toyota", "Buick", and "Ford", which would represent the automobiles being examined in the problem. In this example, the object "automobile" is referred to as an "object class", with the objects "Toyota", "Buick", and "Ford" being referred to as instances of the class "automobile." The inverse way that these relationships are characterized are by "is a" or "isa" relations. Thus, in this example, "Ford" isa "automobile", "Buick" isa "automobile", and "Toyota" isa "automobile."

If "automobile" is given the behavior that "weight must be under 6,000 pounds, then "Toyota", "Buick", and "Ford" will inherit this behavior by default. In a preferred embodiment of the invention, the inheritance of behaviors for each object can be overridden, and other behaviors inserted instead. For example, it might be required that "weight" must be under 5500 pounds for the "Toyota" instance of "automobile." In this case this behavior would be associated directly with the object "Toyota", and all other automobiles would continue to inherit the default behavior from the "automobile" object class.

A preferred embodiment of the present invention allows for a richer object hierarchy than that described above. Specifically, in addition to the isa/instance relation between objects (which may be thought of as a member/set relation), the present invention allows for an ako("a kind of")/subclass relation between objects. The ako/subclass relation may be thought of as a subset/set relation.

Continuing the automobile example, suppose it is desirable to differentiate between different model-year automobiles. At the top of the object hierarchy would still be "automobile", but under it would be, for example, the subclasses "1989-auto" and "1990-auto." The instances of "1989-auto" would be "1989-Toyota", "1989-Buick", and "1989-Ford." The instances of "1990-auto" would be "1990-Toyota", "1990-Buick", and "1990-Ford."

As noted above, it is possible to associate behaviors not only with "automobile" but at intermediate levels in the hierarchy as well as at the bottom of the hierarchy. For example, if weight must be less than 5750 for all 1990 automobiles, this behavior would be associated with the "weight" attribute of the object class "1990-auto", and only its instances would inherit this behavior. (It should be noted that in a preferred embodiment of the present invention "automobile" is actually represented as year-auto, as will be clear from the more detailed discussions. "automobile", for example, is used only for purposes of simplicity and illustration).

To take the above example even further, suppose it is desirable to now ascribe some behavior to all Toyotas and have the instances "1989-Toyota" and "1990-Toyota" inherit this behavior. In the hierarchy set forth above, there is no "Toyota" object with which to associate this behavior. In a preferred embodiment of the present invention this problem is solved by the use of "multiple inheritance." This feature allows objects to inherit behaviors from any one immediate superclass (by "immediate superclass" is meant a superclass on the same level of the hierarchy).

Continuing the present example, if "Toyota" is added as a subclass of "automobile" and established the relations that "1989-Toyota" isa "Toyota" and "1990-Toyota" isa "Toyota", it would be possible for "1989-Toyota", for instance, to inherit behaviors from either "1989-auto" or "Toyota" since it is in an isa/instance relation to both these objects.

In the preferred embodiment of the present invention, a user does not directly set up the object hierarchy described above. Instead, a user describes the problem being represented in terms of the dimensions of the problem and the objects (or attributes) within these dimensions.

In the above-noted example, the dimensions and associated objects (or attributes) entered by a user would be:

dimension 1. (attributes): "weight", "price", "acceleration";

dimension 2. "automobile" with objects "Toyota", "Buick" and "Ford";

dimension 3. "year" with objects "1989" and "1990."

An N dimensional tabular representation of objects and attributes is shown in FIG. 6. In the above example, DIM X would correspond to "automobile" with X.sub.1, X.sub.2, and X3 corresponding to "Toyota", "Buick", and "Ford." DIM Y would correspond to "year" with Y1 and Y2 corresponding to 1989 and 1990, respectively. The attributes such as "weight" would be A.sub.1, etc.

In the above-noted example, a three dimensional table is created. As indicated by the dimension DIM Z in FIG. 6, a fourth dimension to the problem can be added. In fact, in a preferred embodiment of the present invention, any number of dimensions can be added. Thus, N dimensional tables can be created.

When a user enters dimension and object names when describing a problem, the present invention synthesizes the dimension and object names to build an object hierarchy similar to the one referred to in the above example. The exact synthesis of dimension and object names used by the present invention is only a preferred embodiment. Thus, other object-oriented schemes are contemplated by the present invention as well. A detailed description of the process by which the present invention builds this object hierarchy and the precedence of inheritance maintained in it will be described in detail below.

It has been noted above that in the present invention "behaviors" may be associated with the attributes of objects at any level in the object hierarchy. These behaviors are in most cases defined (from an implementation point of view) by the use of "procedural attachments." For instance, the formula "acceleration =velocity / time" could be associated (that is, entered by the user) with the object "automobile."This formula is represented in the preferred embodiment of the present invention as a "to-compute" procedural attachment, and is said to be "attached" to the "acceleration" attribute of the object "automobile." The use of formulas and procedural attachment in the present invention will be described in greater detail below.

In addition, values (as well as procedural attachments) may be associated with the attributes of objects at the lowest level of the object hierarchy (these attributes of objects at the lowest level are referred to as object-attribute pairs). For example, assume that velocity, time and acceleration are all attributes of the problem. Further assume that the value of the object-attribute pair "1989-Ford" "velocity" is 100 ft./sec., and the value of the object-attribute pair "1989-Ford""time" is 10 sec. If the "acceleration" of "1989-Ford"is desired, it may be computed by inheriting the to-compute procedural attachment from "automobile" (which is a representation of the formula noted above). Thus, a value of 10 ft./sec./sec. would be associated with the object-attribute pair "1989-Ford" "acceleration."

Throughout the rest of this document, object-attribute pairs will be indicated by the name of the object and attribute separated by a period. Thus, "1989-Ford.acceleration"would represent an object-attribute pair. However, it is noted that in a preferred embodiment of the present invention, the internal representation of the delimiter is a dash ("-") rather than a period.

A central concept of the present invention is the notion of dependencies. While the implementation of this concept in the present invention will be described in detail below, a brief example at this time will be beneficial. In the formula "acceleration=velocity/time", acceleration is the dependent variable and velocity and time the independent variables. The dependency implicit in this formula is maintained by the present invention. Thus, if the value of the object-attribute pair "1989-Ford.velocity" is changed to be 200 ft./sec., the formula for "acceleration" is automatically recalculated for "1989-Ford" and the new value 20 ft./sec./sec. is asserted to the object-attribute pair "1989-Ford.acceleration."

The present invention also contemplates that rules can be utilized by allowing one or more rules to be entered by the user. Rules can be made to fire (that is, the conditions of the rules are true, and the actions of the rule executed) r depending upon the value of specified object-attribute pairs. Thus, the present invention allows for the intermingling of object-oriented and rule-based methods.

It should be noted that formulas, rules and values are what are known generally as "constructs", which are a basic building block entered by a user in representing a problem. The constructs noted above are examples of constructs which are contemplated by the present invention, and are not meant to be limiting. A larger non-limiting list of constructs contemplated for use with the present invention is set forth below.

In providing an environment in which a user can easily represent and solve a problem using the object-oriented facility described above, the present invention provides a tabular representation within which a problem can be represented. An example of a preferred embodiment of this tabular representation is shown in FIG. 24. In essence, an interface is provided by the present invention between a tabular representation environment, and the sophisticated object-oriented/rule-based environment described above. The tabular representation and the object-oriented/rule-based environment of the present invention are treated as a single entity, making interaction between the two very natural. It is this natural interaction between the tabular representation and object-oriented/rule-based environment that allows the present invention to represent and solve both numeric and symbolic components of a problem.

A preferred embodiment of the overall environment in which the present invention operates is shown in FIG. 1. Examples of this environment include (but are not limited to) an IBM PS/2 personal computer and an IBM RS/6000 workstation. It should be understood that the environment of the present invention is not limited to any type or brand of computer, and thus contemplates microcomputers to supercomputers. Additionally, dedicated hardware can also be implemented to operate the present invention.

Referring to FIG. 1, the present invention (shown as a problem solver 108) is loaded into a RAM 106 during operation. Input is received via an I/0 device 112, after which the input passes through a buffer 110 and then to a RAM 106 via a Bus 114. It should be understood that the I/0 device can be any standard input device, such as a disk, tape, keyboard, mouse, touch screen, or any compatible or equivalent means for manually or automatically entering information or commands.

In order for a user to observe the results as information is entered into the present invention and as progress is made in the course of solving a problem, a preferred embodiment also contemplates the use of a visual display device 116 as an example of an output means. Other output means could include printers, magnetic or optical disks, tape, etc.

In a preferred embodiment, the present invention can be divided into two main portions, as shown in FIG. 2a. The first portion is called a Problem Representation Facility (PRF) 208. The second portion is called the Problem Solving Engine (PSE) 204. The PRF 208 is the portion which allows a user to represent a problem in terms of objects, attributes and constructs, and then allows for manipulation of selected values of the problem in order to come up with a result based upon defined goals.

The PSE 204 automatically manipulates in an intelligent way certain values of the represented problem (called decision variables) sent to it by the PRF 208 in order to quickly solve the problem. The PRF 208 also sends to the PSE 204 a list of expressions representative of the goals, decision variables, and dependencies relating each expression to the set of decision variables which affects it, as defined in the problem. It should be noted that the PSE 204 could be constructed to determine the dependencies independently, either by symbolic examination of the expressions along with examination of the symbolic representation of the rest of the model, or by empirical analysis of the way the variables affect the values of the expressions.

In a preferred embodiment, the PSE 204 maintains a "score", which is a numeric quantity which reflects both how closely the constraints are to being satisfied and the degree of progress toward achieving the objectives. In the preferred embodiment, the components of this score, or the magnitude of change of those components, are displayed to the user by the PRF 208 whenever an improvement to the score has been made.

After the PSE 204 manipulates the values of the decision variables in some fashion, it evaluates the expressions, and checks the resultant score. Depending upon the result of this manipulation, the PSE 204 will continue to manipulate certain decision variables in an attempt to obtain the best score possible. While a user can manually manipulate variables to solve a problem using only the PRF 208, the PSE 204 is important for finding a solution more quickly.

In a preferred embodiment of the present invention, a user can interrupt the PSE 204 at any point in its operation, observe the best point the PSE 204 has found so far, manipulate variables manually using the PRF 208, and then restart the PSE 204. Thus, manual and automatic solution of a problem may be combined. In addition, the user may interrupt the PSE 204 and alter the problem itself using the PRF 208 by modifying any of the constructs such as formulas or rules. Again, the PSE 204 may be restarted to search for a solution for the modified problem.

Thus, the present invention seeks a best balanced solution, while also allowing for the solving of a problem at a greater speed than if a user manipulated the same decision variables in the PRF 208 manually. One of the features that allows the PSE 204 to assist in solving a problem is the ability of the PSE 204 to use heuristics to dynamically interleave various problem-solving techniques. Which problem solving method(s) gets used will depend upon the characteristics of the specific problem being solved. In this way, the present invention is better able to handle complex problems such as NP complete problems. For these problems, it finds a "good" solution (not necessarily the optimum solution) in significantly less than the time it takes using traditional problem-solving methods to find an optimum.

In the preferred embodiment, the user selects one of several stopping criteria to determine when the PSE 204 should stop trying to improve the score. Because the user may cause the PSE 204 to search for an arbitrarily long time, the PSE 204 will, given enough time, try every point in the search space of the decision variables. Naturally, the precision of the points found as solutions is limited by the granularity (non-continuity) of the representation of the values as numbers which is due to the limited precision of the implementation of the language. Thus, within the above mentioned limits, the PSE 204 will eventually find the optimum solution.

An alternative configuration which is contemplated by the present invention utilizes a local area network (LAN) environment as shown in FIG. 2b. FIG. 2b shows a LAN 210 having workstations 1 to n (shown collectively as 206) and a Server 202. In this embodiment, the PSE 204 resides on Server 202, while a PRF 208 resides on each of the workstations 206. Thus, each of the workstations 206 has its own PRF 208, all of which share a single PSE 204 on the Server 202.

The present invention is particularly well suited for the LAN environment, since in a preferred embodiment there is relatively little communication between the PSE 204 and PRF 208 in the course of solving a problem. In the configuration shown by FIG. 2b, many versions of the PRF 208 could benefit from the superior performance available only on the server. Of course, it should be understood that many servers can also be used and tied together in conjunction with the present invention.

It should be noted that a preferred embodiment of the present invention contemplates that at any given time, one or more instances of the PSE 204 could be spawned and devoted to solving a problem. This notion particularly contemplates a multi-user environment such as a LAN or a mainframe where the PSE 204 is receiving more than one problem from one or more PRF 208. Also, in a preferred embodiment, the PSE 204 will be able to directly evaluate expressions representative of constraints and objectives. That is, it is contemplated that each instance of the PSE 204 receives from the PRF 208 a representation of the problem. In another embodiment, the PSE 204 does not directly evaluate expressions by virtue of having received a representation of the problem, but rather communicates with the PRF 208 to receive and send these expressions.

FIG. 3 shows another embodiment of the present invention, in which a multi-processing environment having n multi-processors is used. An example of a multi-processing environment contemplated by the present invention is an IBM PS/2 personal computer with multiple 80486 processors, or and IBM RS/6000 workstation with multiple RISC processors, or a heterogeneous network comprising these or any other environment having a processor. In this embodiment, the search for the solution of the problem is accomplished by pursuing n schedules of the search simultaneously, preferably using n instances of the PSE 204 within the present invention 108'. These schedules can be thought of as a "view" of the problem. For each view, different values and/or different problem solving techniques are executed concurrently with other views. The present invention begins with a single view (that is, as a single instance of the PSE 204), and creates additional views by spawning additional instances of the PSE 204 as required by the problem, and within the limits of the number of processors available.

When the improvement made by an instance of the PSE 204 is larger than some threshold (which may be adjusted to minimize inter-process communication) that improvement may be communicated to some or all of the other n-1 instances of the PSE 204, allowing them to all work on the "best" point in parallel. Once determined, these schedules are then sent to RAMs 1 to n (shown collectively as 106'), and then are acted upon by corresponding CPUs (shown collectively as 102'). The methods by which a preferred embodiment of the present invention solves a given problem allows the present invention to take advantage of multiple processors. Thus, a problem can be solved more quickly than if only a single CPU were acting upon the problem. Of course, it should be understood that the present invention can take advantage of multiple processors whether a single computer is used with multiple CPUs, or multiple CPUs are used by utilizing multiple computers in the same or different geographical locations.

II. Problem Representation Facility (PRF)

A. Overview Of Problem Representation Facility

An overview of the PRF 208 will now be described with respect to FIG. 4. Referring to FIG. 4, the PRF 208 comprises several interrelated portions and concepts which will be described below.

1. Graphical User Interface

In a preferred embodiment of the present invention, a user interacts with the present invention via a graphical user interface (GUI) 402. In essence, the (GUI) 402 is a collection of software modules that allow a user to enter values and constructs into the present invention, as well as entering the various objects and attributes to create n dimensional tables as indicated above.

In a preferred embodiment of the present invention, graphical subroutines are used to create the (GUI) 402. This includes graphical subroutines which create, for example, dialogue boxes and menus. These graphical subroutines allow input to the present invention to be entered through any standard input device, such as a keyboard, mouse, or digitizer pad. In a preferred embodiment of the present invention, the graphical subroutines are standard, commercially available graphical subroutines. One such example is a commercial package called XVT, manufactured by Graphical Software Systems.

Using the (GUI) 402 as described above allows the present invention to be compatible across different software platforms. For example, in a preferred embodiment, the present invention will run under both OS/2 using Presentation Manager (both from IBM) and UNIX using OSF/Motif. This relates not only to the (GUI) 402 portion of the present invention, but to the entirety of the present invention as well.

The (GUI) 402 thus provides a visual aid to assist a user in entering values and constructs into the present invention in order to represent a problem. Of course, other interfaces such as a windowing character-based interface or command-line interface could also be used.

Regarding the actual entering of these values and constructs, a preferred embodiment of the present invention allows the user to enter this information using one of two protocols. The first protocol is referred to as a "natural language", and the second protocol is referred to as a "representation language." These two protocols, as well as their respective translators (shown as 404 and 406, respectively), will be discussed below.

2. File Interface

In addition to interacting with the invention through the (GUI) 402, a preferred embodiment of the present invention allows a user to interact with the present invention in whole or part through a file interface 403. The file interface 403 allows the user to enter into a standard text file all the objects, attributes, values and constructs that would have been entered interactively using the (GUI) 402. The user can create this text file using any text editor, such as Emacs or WordPerfect. This text file is then processed by the natural language translator 404 and representation language translator 406.

When saving a problem (or "model") created using some combination of (GUI) 402 and file interface 403, a preferred embodiment of the present invention allows a user to save the problem in either "image" format or in text file format. The image format is a non-readable "compiled" representation of the model. The text file format is an ascii-readable text file that reproduces all the values and constructs exactly as entered by a user. This text file may then be further edited by the user and reevaluated as described above. In addition, this text file serves the function of providing a user with what can be considered written documentation of the problem.

3. Natural Language Translator

The natural language translator 404 allows the user to input constructs in a format similar to English. For example, in a preferred embodiment, a formula such as "return: =profit -cost" could, by virtue of the natural language translator 404, be written as "return is equal to profit minus cost."Another way that this could be written as contemplated by the present invention is "let return be profit minus cost." Of course, it should be understood that the present invention contemplates a natural language translator 404 that can translate any number of natural language formats.

In essence, the purpose of the natural language translator 404 is to give a user flexibility in deciding how to enter constructs to create a problem. It is a particularly advantageous feature for users who are not accustomed to expressing information in more formal command languages. It should be noted that in the preferred embodiment of the present invention, the natural language translator subsumes the representation language translator mentioned below. That is, a user may freely mix natural language constructs with those of the formal representation language. There is no necessity to inform the system that a construct is intended as natural language or representation language.

4. Representation Language Translator

For users who are more accustomed to expressing terms in a more concise, formal language, a preferred embodiment of the present invention also provides a representation language translator 406 which allows a user to enter constructs using a representation language. For the above-noted example, if the same equation were written using the representation language, the equation would simply appear as "return: =profit-cost."

As indicated above, equations can also be written which consist of elements of both the representation language and the natural language. For example, a formula such as "return: =profit minus cost" can be used.

It should be noted that the specific examples of the protocol used for both the natural language and representation language were only examples of a preferred embodiment of the present invention. In general, the present invention contemplates the use of any number of different types of specific protocols.

It should also be noted that for the examples shown above, only the attributes have been set forth. References to the objects themselves have been dropped, since the examples were of a "general" formula. The effect of entering such a formula would be to associate it with the object class highest in the hierarchy for the current "table", thus making the formula applicable to all objects below it in the hierarchy. This concept will be discussed further below.

5. N Dimensional Tabular Representation and Object hierarchy

The N dimensional tabular representation 408 refers to the general concept and implementation thereof of multiple dimensions of objects, with the first dimension always being fixed as the attributes. (Note that minimum value of N is always 2, as it makes no sense in the preferred embodiment of the present invention to define a problem lacking either objects or attributes.) The N dimensional tabular representation 408 gives the user an enhanced conceptual framework for envisioning a problem, as well as an interface for allowing a user to enter constructs at various levels within the object hierarchy 410 that the present invention creates. In addition, in a preferred embodiment of the present invention, values can be entered at the lowest level (that is, the object-attribute level) within the object hierarchy 410 (although it should be understood that the present invention also contemplates values being entered at other levels as well). This representation 408 is internally implemented by the object hierarchy 410 so that it can accomplish the features indicated above.

The automobile industry example used above will now be used to illustrate the manner in which the present invention creates both the N dimensional tables and an associated object hierarchy 410. Recall that in the aforementioned example the user entered the following information:

dimension 1. (attributes): "weight", "price", "acceleration";

dimension 2. "automobile" with objects "Toyota" and "Buick"

(we will omit "Ford" in the interest of simplicity);

dimension 3. "year" with objects "1989" and "1990."

The user will also give the table a name, say "auto-table" for automobile industry table, and the present invention will create a three-dimensional table as described above. In the preferred embodiment of the present invention an object "autotable"is said to be created as an instance of the object "table." This is not central to the invention, but mainly allows the various tables in memory at to be organized efficiently with data that pertains to them.

In the present invention, a "cell" is an intersection of all the rows and columns of a table, and thus corresponds to an object-attribute pair at the bottom of the object hierarchy 410 that is created for the table. In the above-noted example, one such cell (or object-attribute pair) would be referred to as "1989.Toyota.weight." The internal object that is being referenced in the cell of this table is "1989-Toyota"and the attribute is "weight." Note that while the user may think of the representation in terms of the objects "1989" and "Toyota", in the internal object hierarchy 410 that is created by the present invention these objects do not exist. It should be noted that throughout most of the application, the term "object-attribute pair" rather than "cell" will simply be used.

A preferred embodiment of the present invention creates its internal representation of objects by forming a concatenation of the cross product of the specific user-entered object "names" (such as "1989" and "Toyota"). In the above-noted example, the following objects would be created by the present invention: "1989-Toyota", "1990-Toyota", "1989-Buick", and "1990-Buick". For each of the preceding four objects, new objects are created by concatenating the dimension name with the specific user-entered object name, and working from the outermost dimension inward until the innermost dimension (dimension 2--attributes play no role in this process) has a general name (i.e., the name of a dimension). Thus, for "1989-Toyota" two new object classes would be created in turn, "year-Toyota"and "1989-automobile." These object classes are added to the object hierarchy 410 by adding isa links to them from the initial object (that is, "1989-Toyota" isa "year-Toyota"and "1989-Toyota" isa "1989-automobile"). For "1989-Buick"we add the object class "year-Buick", and the relations "1989-Buick"isa "year-Buick" and "1989-Buick" isa "1989-automobile."This process is repeated for "1990-Toyota" and "1990-Buick."

Next, for each object class that has just been created (for example, "year-Toyota"), new object classes are created by generalizing any specific names one at a time, working from the outermost dimension inward. For the example "year-Toyota", only one new object class is created, "year-automobile"(which in this case is the highest object class in the hierarchy). Lastly, ako links are added from the previous layer of object classes in the hierarchy to these newly created object classes. The following relations will then be created: "year-Toyota" ako "year-automobile", "1989-automobile" ako "year-automobile", "year-Buick" ako "year-automobile", and "1990-Buick" ako "year-automobile." The resulting object hierarchy 410 is depicted in FIG. 9a. It should be noted that techniques other than concatenating names as indicated above could also be used to achieve the same general result. For example, objects could inherit from objects of arbitrary name, but identical meaning. Also, multiple dimensions could be implemented by arrays of objects.

It should be noted that the description above regarding what constitutes a first, second, etc. dimensional problem is only for purposes of ease of understanding. Thus, this problem could also be considered as a problem of some other dimension. In addition, it should be pointed out that an individual object hierarchy 410 is created and utilized each time a problem is entered by a user. As mentioned above, all values entered into the present invention are associated with the attributes of objects at the bottom of the object hierarchy 410 (that is, object-attribute pairs). Constructs such as formulas that define the way these values are computed or cause computation of other values, however, may be associated with an object at any level in the object hierarchy 410. The exact means of this association will be described in further detail below.

It should be noted that the object hierarchy 410 that has been created from the user's input by the present invention, and the order in which it is searched for behaviors in the inheritance) corresponds exactly to the intuitive notions about the objects themselves. That is, the order of the search up the object hierarchy 410 is exactly the order in which the hierarchy (as described above) was built. What this results in is a breadth-first search of the object hierarchy 410. More specifically, the isa links are first searched from left to right. Then, the ako links are searched from left to right. (See generally Knuth, Donald, "The Art Of Computer Programming" (Volume I), Addison-Wesley, 1973).

Again using the preceding example, suppose a formula is being accessed to compute the value of "1989-Toyota.acceleration."The search up the object hierarchy 410 for this formula commences at "1989-Toyota" and proceeds to "year-Toyota" and then to "1989-automobile", and so on. The object "year-Toyota" can be thought to represent Toyotas for all years, while "1989-automobile" represents all automobiles for the year 1989. One can see the logic with associating the behavior of a 1989 Toyota first with Toyotas of all years, and then with all 1989 automobiles. In this way, any behaviors associated with "year-Toyota" will take first priority, followed by behaviors associated with "1989-Automobile", etc.

The preceding example of the creation and search process of the object hierarchy 410 for a three-dimensional problem is the means by which the present invention creates a hierarchy for a problem of any dimensionality. FIG. 9b, for instance, represents a vertical "slice" of the object hierarchy 410 for a four dimensional problem in which the dimensions are country, year, and product. The numbering of the links in it indicates the order in which the isa and ako links are searched upward from the object "Japan-1988-pI."

It should be noted that the breadth-first search as described above entails some redundancy, in that there are links to objects which have already been searched. More specifically, in the example shown in FIG. 9, the link numbers 5, 7, 10, 11, 12, 13 and 14 are redundant. Where the construct being searched for is at the highest point in the hierarchy, links 10 through 14 are not searched. In the case that an inheritable construct is not found at the highest point, all redundant links are searched. In the preferred embodiment of the present invention, however, this redundant search takes place only once, as the results of the search (and failure thereof to find any inheritable behaviors) is associated with the object at the bottom of the hierarchy. Note that this "caching of failure" does take up some extra memory, and that many different searching and caching schemes would be sufficient to implement the object hierarchy search. The notion of "caching" generally as used in the present invention will be discussed further below.

As indicated above, if the present invention searches up the object hierarchy 410 and detects an inheritable construct in any of the object classes, the behavior of that construct will be inherited, and the search will terminate. Since the search up the hierarchy is from most to least specific, this scheme allows a general construct to be overridden for specific cases. Thus, if the general formula "return:=profit-cost" were entered and consequently affiliated with the most general object class, then entering a more specific construct would override the general formula for certain object-attribute pairs.

Returning to our three-dimensional automobile example, and assuming that the attributes, "profit", "cost", and "return"have been added to the problem, assume that a user enters the formula "return: =profit-cost." Since no objects are specified with this formula, it is considered a general or non-specific formula, where the objects are considered to be general (that is, at the highest level of the object hierarchy 410). Thus, in a preferred embodiment of the present invention, this formula is an equivalent short-hand version of the formula "year.automobile.return: =year.automobile.profit -year.automobile.cost." The effect of entering this formula is that it will be applied to all objects at the bottom of the object hierarchy 410. In terms of the resulting 3 dimensional table, it will apply to all object-attribute pairs that correspond to the "return" attribute along both the X and Y axes.

Using a specific illustration, if the object-attribute pair "1988-Toyota.profit" was given a value of 100, and the object-attribute pair "1988-Toyota.cost" was given a value of 80, then for the object-attribute pair "1988-Toyota.return" the present invention would generate the value of 20. Thus, the object-attribute pair "1988-Toyota.return" would be said to "inherit" the formula.

As indicated above, the N dimensional tabular representation 408 also allows a user to use constructs in a somewhat more limiting way. For example, a user could use the above-noted formula only for automobiles in year 1988. Such a formula could be written as "1988.return: =1988.profit 1988.cost". If the user wanted the formula only to relate to Toyotas for all years, the formula could appear as "Toyota.return: =Toyota.profit - Toyota.cost." Again, it should be understood that the representation of the formula noted above, as with the representation of constructs shown generally, is only a preferred embodiment of the present invention, and that these constructs can be written in many different ways.

In addition to allowing the creation of a table of N dimensions, the present invention also allows multiple tables of any dimension to be created. Once created, these tables can then be interlinked to each other. An example of the use of two tables can be seen from FIG. 24 In this example, two separate but interrelated tables (one designated "project", and the other designated "proj-sum") are shown. It should be noted that for the table designated proj-sum, the object and attributes have been transposed (that is, the attributes lie along the X-axis rather than the Y-axis). The present invention also allows a user to define a "model" to represent a problem in terms of multiple tables. In the example from FIG. 24, the two tables represent a "Capital Budgeting"problem. These features are pointed out only to show that they are features of a preferred embodiment of the present invention.

5. Dependency Machinery

The dependency machinery 412 is the mechanism which enforces the relationships (that is, dependencies) set up within the object hierarchy 410 by the constructs. This dependency machinery 412 can be better understood by an explanation of what it does. Using the above-noted example to illustrate, if the formula "return: =profit-cost" were entered into the present invention, then this formula will be at the top level of the hierarchy (that is, at year-automobile). In other words, this construct could be said to be attached to the "return" attribute of "year-automobile."In addition, the following two dependencies would be added: "year-automobile.profit affects return" and "year-automobile.cost affects return." This means that a change in value of any object-attribute pair where the attribute is "profit" or "cost" will affect the value of the corresponding object-attribute pair having the attribute "return." It will be further explained below how these dependencies are represented internally.

The dependency machinery also serves to propagate dependencies. For example, if a change in value to a first object-attribute pair causes a change in value to a second object-attribute pair, then it is quite possible that this latter change will cause further changes to other object-attribute pairs. If this occurs, the dependency machinery of the present invention determines what object-attribute pairs will be affected, and determines the most logical order to effect the propagation.

From the above, it will be seen that the dependencies created and manipulated by the dependency machinery 412 of the present invention can be thought of as object-oriented dependencies. In other words, the dependencies are formed which can be thought of as belonging to a specific object, but which may in fact be inherited by many objects lower in the object hierarchy 410. In terms of the tabular representation, what this means is that the dependencies between any number of cells in a typical table can many times be represented by just a few procedural attachments to an object class in the multiple inheritance object hierarchy 702, which will be discussed further below.

6. Object-Oriented Language With Inference Engine Tool

In the present invention, the object-oriented language with inference engine tool 414 is a basic building block of the present invention.

The object-oriented language portion of this tool 414 allows for access from a higher level language. In a preferred embodiment of the present invention, this access is made in the form of function or subroutine calls.

In a preferred embodiment of the present invention, the hierarchies and dependencies are actually set up and kept track of by the object-oriented language portion of this tool 414. When the constructs of an object class are entered by a user, the dependency machinery 412 ultimately manipulates the dependencies created, but the object-oriented language is used to create and keep track of these dependencies relative to their hierarchical situation (for example, it keeps track of inheritance of behaviors and retrieval of values of object-attribute pairs).

When a construct such as a formula is entered by a user in either "natural language" or the "representation language" of the present invention, that construct will be translated and represented internally by components known as procedural attachments (as mentioned above). The object-oriented language portion with inference engine tool 414 is then able to manipulate the constructs in this format.

With regard to the inference engine of the object oriented language with inference engine tool 414, a preferred embodiment of the present invention allows for both forward and backward chaining rules to be implemented as constructs. Using rules allows complex relationships to be stated between object-attribute pairs and other object-attribute pairs. In essence, rules allow for implementing the logic that if certain conditions hold true for one or more object-attribute pairs, then some particular action will be taken regarding at least one other object-attribute pair.

The object-oriented language and inference engine tool 414 used in the present invention is a standard type of object-oriented environment. Consequently, there are commercially available products which are equivalent to the object-oriented language and inference engine used by the present invention. Such products are ART by Inference Corp., and KEE by Intellicorp.

7. Lisp Interpreter

A preferred embodiment of the object-oriented language and inference engine tool 414 of the present invention is written using a version of the LISP programming language. As was the case for the object-oriented language and inference engine tool 414 itself, any standard LISP interpreter 416 would serve the purpose. Examples of such LISP interpreters include "Lucid Common Lisp" by Lucid, inc., and "Franz Lisp" by Franz, inc.

Of course, the object-oriented language and inference engine tool 414 could be written using any general purpose programming language. Examples of such programming languages include Prolog, Pascal, C, and C++.

B. Sample Problem

A detailed description of the PRF 208 will be explained using the Sample Problem set forth below, with reference to FIGS. 24-32. This Sample Problem is a capital budgeting problem, and portions of it are similar to the automotive industry example referred to above.

The general idea of this capital budgeting problem is that there are 10 possible projects to choose from. The goal is to choose those projects which will maximize return-to-risk ratio (specified by "rr-ratio").

A constraint used in this problem is that only a certain amount of money can be used to invest in the projects. A country is associated with each of these projects. The problem includes a "war-risk" factor associated with each project. In this problem, the calculation of war risk is accomplished using rules.

In this problem, the second dimension is "project", and the objects in that dimension (that is, the projects which can be chosen) are "p1, p2,...p10." FIG. 32 shows a third dimension being added, where the dimension is "year", and the objects are "1988, 1989, 1990."

C. Constructs

FIG. 5 shows a list of constructs used in a preferred embodiment of the present invention. As indicated above, a construct basically refers to certain building blocks (such as formulas) which allow a user to build the representation of a problem. These constructs can be thought of as belonging to a specific object-attribute pair, a more general object class-attribute pair (that is, an attribute of an object class), or an entire table. A brief description of constructs available forth below.

1. Rules

A rule allows a user to express relationships between different object-attribute pairs. More specifically, a rule can be thought of as an IF-THEN statement having the property whereby IF certain arithmetic and/or logical statements about the values of object-attribute pairs all hold true, THEN certain arithmetic and/or logical operations will be applied to other object-attribute pairs. As indicated above, the evaluation of these rules uses the inference engine functionality of the object oriented language with inference engine tool 414.

The information to which a rule refers is generally known as a knowledge base. In a preferred embodiment of the present invention, this knowledge base can be derived from information within the object-attribute pairs themselves, and/or information from an external source, such as a database. In effect, the value of any object-attribute pair referenced by the present invention may be retrieved from or written to an external database. This external referencing of values can be applied to constructs other than rules. A preferred embodiment of the present invention also allows such external sources to be easily accessed.

FIG. 27 shows a rule being entered into the Sample Problem. This rule uses general variables (which are used to stand for an object, attribute, or value) which, in a preferred embodiment of the present invention, allow the rule to be used flexibly. Referring to FIG. 27, this rule checks to see IF the value of "taken" equals "yes" for some instance of "projects", and IF the instance has a country, and IF that country has no war, THEN "war-risk" for that instance of "projects" will be set to zero.

Again, it should be understood that the specific protocol used in presenting this and other constructs of the present invention is only a preferred embodiment of the present invention.

2. Critics

A critic is basically a passive rule. In other words, it allows the same IF-THEN structure of regular rules in that the user can define a series of events and actions to be taken. However, with a critic, the actions to be taken are limited to the display of a user-defined message. This allows a user to receive commentary about certain actions taken by the problem.

FIG. 28 shows an example of a critic being entered into the present invention. Here, if the object-attribute pairs "p3.Taken" and "p4.Taken" both equal "yes", then a message is sent to a user. Thus, critics are a way to express expertise or commentary about the state of a problem without actually taking any action which would otherwise affect the state of the problem.

3. Formulas, Triggers and Values

A formula is an expression that defines the way that a single value of an object-attribute pair is to be computed. For example, "return: =profit-cost-fee" is an example of a formula. Thus, any number of operands can be used in defining a formula, but there will only be one result. FIG. 25 shows an example of a formula being entered into the sample problem.

In contrast to a formula, a trigger allows one or more effects to occur upon the occurrence of a single event. More specifically, when the value of an object-attribute pair is altered in some way, a trigger will cause different actions to take place on other object-attribute pairs. Using the Sample Problem, a trigger can be written such that if p3 is taken, (that is, if p3.taken="yes") then take p5 and p8 (that is, make p5.taken="yes" and p8.taken="yes"). FIG. 26 shows an example of a trigger being entered, indicating that if an instance of "projects" is not taken, then for that instance, "war-risk" will be set to zero.

A "value" is just a setting or assignment which is associated with a particular object-attribute pair. These values can be numerical, or they can be symbolic, such as "yes" or "no." As indicated above, in a preferred embodiment of the present invention, an object-attribute pair can contain a value, in addition to having associated with it (that is, having attached to it) some other construct such as a formula or trigger.

As indicated above, the constructs used in some examples to represent non-specific object classes are short-hand for the full construct name which could otherwise be used.

4. Goals

Goals are constructs which enable a user to express what the user wants in the way of a solution to a problem. In a preferred embodiment of the present invention, goals can be divided up into two different types of constructs called targets and objectives. An objective allows the user to choose one or more object-attribute pairs to be maximized or minimized. Using the Sample Problem and referring to FIG. 29, it is a goal of the problem that rr-ratio be maximized.

In contrast to objectives, targets allow a user to express what values or range of values the user wishes an object-attribute pair to attain (or maintain). For example, a user might want to maintain that, for a particular problem, "cost" should be less than 500. If the user enters "cost<500" then for each object-attribute pair where the attribute is "cost", the present invention will try to maintain cost below 500. If a user only wanted more specific costs to be less than 500, then more specificity would be required. For example, "p2.cost<500" would limit only the value of the object-attribute pair corresponding to p2.cost to less than 500, as opposed to all object-attribute pairs having "cost" as the attribute.

In other systems, those things which the current inventions calls "targets" might be described, instead, as constraints. Indeed, that which is referred to above as a "constraint" was initially derived from the entering of a target. However, the term "target" will be used in this portion of the application, as it reflects the intention of approaching desired conditions as closely as possible, even when they cannot all be met.

FIG. 30 shows a target being entered into the Sample Problem where it is desired that the total cost (t cost) be greater than or equal to 1000.

In a preferred embodiment of the present invention, goals can be entered by a user as being weighted or scaled. Weight represents the relative importance of a particular goals (objectives and targets). Scale represents the relative precision to which a target is to be approached, or in the case of objectives, the coarseness with which to regard incremental changes in the objective.

In an alternative embodiment, scale or precision can also be used as part of the termination criteria for the PSE 204.

5. Decision variable

A decision variable is a construct which allows a user to select object-attribute pairs which the PSE 204 is allowed to vary in order to achieve the best score. These decision variables need to be values that are independent of other object-attribute pair values. The PRF 208 detects which object-attribute pairs are candidates for becoming decision variables (by noting those object-attribute pairs that are not affected by some object-attribute pair, but which do affect at least one other object-attribute pair), and then allows a user to decide from these candidates which will actually be used as decision variables.

When an object-attribute pair is selected, the user enters a legal range over which the decision variable is allowed to vary. In the Sample Problem, examples of decision variables would be those object-attribute pairs where the attribute is r "taken", (that is, p1.taken, p2.taken, ...). Here, the range of variance would be either the value "yes", or the value "no." If numbers were at issue, then a range would be set between two numeric values.

6. Object Variable

An object variable is not a construct in the sense that it affects object-attribute pairs or causes action to be taken depending upon their values, but in a preferred embodiment of the present invention it does provide a user a convenient way to express other constructs. More specifically, they can be used to represent "wildcard macros" for a construct such that the construct will be effectively replicated for each instance of an object. In this way, a user will not have to physically type out each construct. For example, referring to the automobile problem above, the formula "?auto.total-profit: =total year.?auto.profit" (where "?auto" is the object variable and total is a function which totals the values of all object-attribute pairs associated with a designated object class) is equivalent to writing the formulas "Toyota.total-profit: =total year.Toyota.profit", "Buick.total-profit: =total year.Buick.profit", and "Ford.total-profit: =total year.Ford.profit."

D. Object Oriented Language With Inference Engine Tool

The object oriented language with inference engine tool 414 provides an object-oriented environment for other portions of the present invention, and will now be further described below with regard to FIG. 7. This tool 414 can be divided into three sections having separate, but related functions. The implementation of the object oriented language module 701 itself of the tool 414 can further be divided between a Multiple Inheritance Object Hierarchy Module 702, and a Procedural Attachment Module 704. These modules, as well as the Inference Engine Module 706, are described below.

1. Object Oriented Language Module

a. Multiple Inheritance Object Hierarchy Module

The Multiple Inheritance Object Hierarchy Module 702 is the portion of the Object Oriented Language Module 701 that performs the task of implementing the object hierarchy 410, and then of maintaining it. Essentially, this module 702 receives information relating to the objects and attributes that are entered by a user, and builds an object hierarchy 410 from that information.

Once the object hierarchy 410 is built, information relating to the constructs entered by the user can be accepted by the Multiple Inheritance Object Hierarchy Module 702. This module 702 will attach the constructs to their appropriate location within the hierarchy.

The above concept can better be explained with regard to the Sample Problem. As indicated above, the formula "return: =profit-cost" is non-specific, and will affect all of the object-attribute pairs where "return" is an attribute. This formula thus belongs with the highest (most general) object class, which in this case is year-project. When a user enters this formula, the Multiple Inheritance Object Hierarchy Module 702 will tell the present invention where in the object hierarchy 410 this formula is to be attached. In this case, this formula would be attached to the "return" attribute of the object class year-project. The actual way that constructs such as formulas are attached will be described below with regard to the Procedural Attachment Module 704.

Once an object hierarchy 410 is constructed and constructs are attached to the object hierarchy 410, the Multiple Inheritance Object Hierarchy Module 702 also performs the hierarchical searching for constructs up the object hierarchy 410. Thus, if the value of an object-attribute pair is desired, the Multiple Inheritance Object Hierarchy Module 702 first checks if that object-attribute pair has a "to-compute" procedural-attachment (procedural attachments are also commonly referred to as demons) attached to it directly (that is, it checks the most specific point in the hierarchy, namely, the fully specified object-attribute pair itself).

If no "to-compute" demon is directly attached to the object-attribute pair, then the Multiple Inheritance Object Hierarchy Module 702 will check the object hierarchy 410 it built to see if that particular object-attribute pair has a "to-compute" demon that it is to inherit. Using the Sample Problem, if the value of a specific object-attribute pair such as "1988-p1.return" is desired, the Multiple Inheritance Object Hierarchy Module 702 would first check for any constructs directly attached, and then would search up the hierarchy. When the formula "return: =profit-cost" is eventually found at the object class "year-project", then the "behavior" (computation) associated with the formula will be inherited by 1988-p1.return. The end result will be the assertion of a value to 1988-p1.return. The specific way in which the search of the object hierarchy 410 is performed in a preferred embodiment of the present invention was discussed above with regard to FIGS. 9a and 9b.

In a preferred embodiment of the present invention, the Multiple Inheritance Object Hierarchy Module 702 is used in a similar fashion to maintain and search other procedural attachments, such as "if-set" and "affects" procedural attachments, as will be explained below.

b. Procedural Attachment Module

Procedural Attachment in general refers to techniques for associating with an object-attribute pair a way to determine what the value of that object-attribute pair (or some related object-attribute pair(s)) should be. As indicated above, constructs such as formulas which are entered into the present invention by a user are translated into various procedural attachments. It is these procedural attachments that actually define relationships between various object-attribute pairs as defined by a problem. In the present invention, the Procedural Attachment Module 704 implements and maintains these procedural attachments.

In a preferred embodiment of the present invention, it is the procedural attachments which actually become attached to the object-attribute pairs. Thus, when a construct is said to be attached to an object-attribute pair, it is more specifically a procedural attachment which becomes attached. Also in a preferred embodiment of the present invention, only the formula and trigger constructs, as well as the dependencies implicit in formulas, triggers, and rules, are translated into procedural attachments which become attached to object-attribute pairs. The actual way in which the constructs are translated into procedural attachments in a preferred embodiment of the present invention will be discussed below with regard to FIG. 10, and the attachment of constructs generally will also be discussed further below with regard to FIG. 11.

In a preferred embodiment of the present invention, there are several procedural attachments which are used. One is called a "to-compute" procedural attachment, which indicates the arithmetic/logical expression to be computed to arrive at value for the object-attribute pair to which the "to-compute" is attached. Another is an "affects" procedural attachment, which indicates what object-attribute pair(s) are affected by a change in value of the object-attribute pair to which the "affects" procedural attachment is attached. Another is called an "if-set" procedural attachment, which, when the value of the object-attribute pair to which the "if-set" is attached is changed, actually initiates a re-computation of one or more other object-attribute pairs.

It is noted that conventionally, a "to-compute" procedural attachment is often referred to as an "if-needed" procedural attachment, and an "if-set" procedural attachment is often referred to as an "if-added" procedural attachment. In a preferred embodiment of the present invention, the "if-set" procedural attachment calls a function which propagates the various dependencies which may be affected by a change in a particular object-attribute pair.

An example of how the procedural attachment module 704 utilizes procedural attachments in a preferred embodiment of the present invention will be discussed using the Sample Problem in 2 dimensions, and the formula "p1.return: =p1.profit-p1.cost." When this formula is entered by a user, a "to-compute" procedural attachment is attached to p1.return, indicating the specific formula above (that is, indicating exactly how to compute a value for p1.return). Thus, this procedural attachment indicates the formula that is needed to arrive at the value that is to go into the object-attribute pair p1.return.

With regard to the other object-attribute pairs which are a part of the formula (that is, p1.profit and p1.cost), each of these object-attribute pairs would have an "affects" procedural attachment attached to them, indicating that a change in their value would affect the object-attribute pair p1.return. In addition, they would also each have an "if-set" procedural attachment attached to them, indicating that if the value of either is changed, a re-computation of the object-attribute pair they affect is to be initiated. It is emphasized, though, that it is the "to-compute" procedural attachment attached to p1.return that actually determines how the re-computation will take place. Because of this, it can be said that the formula itself is "attached" to p1.return.

Another example is set forth below which relates to the trigger construct. Assume that a user enters a trigger which indicates that if p1.taken ="yes", then p5.taken="yes." The present invention would attach "if-set" and "affects" procedural attachments to the object-attribute pair pI.taken, indicating that a change in its value will affect the object-attribute pair p5.taken. In addition, a "has-demons" procedural attachment is associated with pI.taken that corresponds to the computation indicated by the trigger itself. Thus, if and only if the value of pI.taken is changed, the trigger will be evaluated and the value of p5.taken may be changed accordingly. In general, the trigger is said to be "attached" to pI.taken.

It should be noted that the concept of procedural attachment is closely intertwined with that of multiple inheritance and the object hierarchy. For example, when the value of an object-attribute pair such as p1.cost is changed, there may not be a procedural attachment such as an "if-set" attached directly to that object-attribute pair. However, it may be attached to project.cost (that is, the more general object class). Thus, the present invention must search up the object hierarchy 410 to find this procedural attachment.

2. Inference Engine Module

A preferred embodiment of the present invention contemplates the use of both forward chaining rules (that is, data-driven rules) as well as backward chaining rules (that is, goal-driven rules). Forward chaining rules can be thought of as a kind of generalized trigger. With a trigger, if the value of an object-attribute pair is changed, then the values of other object-attribute pairs may be changed. Rules are similar in that when one or more object-attribute pairs are changed, conditions are evaluated to see if some action should be taken with regard to the same or other object-attribute pairs. A difference, though, between rules and triggers, is that rules can be "triggered" by taking into account the state of many object-attribute pairs, whereas triggers can only be "triggered" by the change in value of a single object-attribute pair.

The rules that are contemplated for use with the present invention can refer either directly to the object-attribute pairs, or as part of an external source such as a database which can then be easily accessed by the present invention. An example of a simple rule is given above with regard to FIG. 27.

E. Overview of General Operation Of Problem Representation Facility

An overview of the operation of the PRF 208 will now be explained below with reference to FIG. 8.

The first four blocks shown (802, 804, 806 and 808) indicate the way in which a problem is represented in a preferred embodiment of the present invention. Block 802 indicates that the user first sets up the object-attribute pairs in an N dimensional table. In order to do this, the user enters the dimensions, objects and the attributes that are to be used in the problem. As indicated above, each new dimension entered adds an additional dimension to the N dimensional tabular representation, and to the problem itself.

Once the dimensions, objects and attributes have been entered, the present invention then creates from this information the object hierarchy 410, as indicated by block 804. As indicated above, the hierarchy goes from most specific to least specific (that is, the more specific objects inherit behaviors from the more general object classes). The creation of the object hierarchy 410 is implemented procedurally as described above by the Object Oriented Language With Inference Engine Tool 414 as the user enters the dimensions, objects and attributes of the problem.

Once at least a minimal object hierarchy 410 has been implemented, the present invention then allows a user to enter constructs, as indicated by block 806. Thus, once the object-attribute pairs are established, the user is free to enter (or attach) values, formulas, etc. to these object-attribute pairs. Furthermore, additional dimensions, objects and attributes can be added after constructs are entered.

In the preferred embodiment of the present invention, after a construct is entered, the present invention parses the construct, translates it to a form evaluable by the Lisp Interpreter 416, adds any dependencies, and then attaches the construct to its appropriate location, as indicated by block 808. As indicated above, the use of a Lisp Interpreter 416 is used in a preferred embodiment of the present invention, and it should be noted that any technique for interpreting the procedures of the translated construct would suffice. Such a technique is not limited to the use of interpreters and could include, for example, the use of a compiler.

As used here, "parsing" means that the present invention translates the constructs into canonical form which can be further "translated" to evaluable expressions (as mentioned above, the present invention contemplates an embodiment which uses a compiler, wherein the expressions would be further compiled to executable code). "Add dependencies" means that the present invention interprets from the constructs (if the constructs are formulas, triggers, or rules)what dependencies are implicit in those constructs, and associates them with the appropriate object-attribute pair.

Once the dependencies have been so added, then the constructs are "attached" to their proper places. If the constructs are formulas or triggers, procedural attachments are attached to the proper object-attribute pair. The events indicated by block 808 will be explained in more detail below with regard to FIG. 10.

The portion of the present invention discussed above and indicated by blocks 802, 804, 806 and 808 broadly represent that portion of the present invention which is used in the representation of a problem. In order to then obtain a result for a problem, a user needs to be able to assign values to object-attribute pairs, and then evaluate the effect that the propagation of values has on the goals (or more specifically, on the score) of the problem. In a preferred embodiment of the present invention, the user is given the ability to manually make assignments of values, and then to note the effect that each of these assignments has. This is indicated by block 810, and allows a user to easily perform a "what-if" analysis on the problem. However, it can take an unreasonable amount of time to manually try different values for different object-attribute pairs in order to obtain an optimum result, especially for a complex problem.

The PSE 204 described in detail further below automates and expedites the value assignment (and goal optimization) procedure. In general, the PSE 204 tries to achieve the best score by intelligently manipulating only certain values of object-attribute pairs and only by certain amounts, so that every conceivable combination of possible values need not be tried. As indicated above, in a preferred embodiment, the PRF 208 computes which of the object-attribute pairs could be decision variables based upon which object-attribute pairs are independent, and then allows a user to choose which ones are actually to be used as decision variables in solving the problem. The information regarding which object-attribute pairs were chosen by a user to be decision variables is then sent to the PSE 204.

While it is possible to find a solution to a problem using only the PRF 208, the PSE 204 makes problem solving far more practical. However, by allowing a user to manually manipulate the values in the problem, the user can become convinced that their representation of the problem appears to be operating correctly, and can easily conduct a "what-if" analysis.

F. Parse, Translate, Add Dependencies and Attach Constructs

A more detailed description of the treatment of constructs as they are entered into and processed by the present invention is described below with regard to FIG. 10.

The constructs can be entered into the present invention (as indicated by block 1001) using any number of input devices. Once entered, the constructs are processed by a Natural Language Translator Module 1002 (which contains the natural language translator 404 described above with regard to FIG. 4). This module will convert constructs entered in natural language format into representation language format. Where a construct is entered using a combination of the natural language and representation language, the Natural Language Translator Module 1002 will convert those portions of the construct written in the natural language into the representation language. Since a user is always given the option of entering constructs using natural language in whole or in part, in a preferred embodiment of the present invention, the entered constructs are always processed by (that is, passed through) the Natural Language Translator Module 1002.

After the constructs have passed through the Natural Language Translator Module 1002, they are then directed to a Conversion Module 1004 which converts the constructs from a user token (that is, a user-entered construct which may be in a short-hand form) to an internal object name (that is, a form which will be recognized and fully understood by subsequent portions of the present invention). Thus, if a user enters a construct in a short-hand manner, then the conversion module 1004 will add onto the construct the omitted objects in general form. Again, using the Sample Problem above, when the formula "return: =profit-cost" is entered by the user, the Conversion Module 1004 will convert it into "year.project.return: =year.project.profit-year.project.cost." Similarly, if the formula "1988.return: =1988.profit-1988.cost" is entered by the user, the Conversion Module 1004 will convert it into "1988.project.return: =1988.project.profit -1988.project.cost."

In a preferred embodiment of the present invention, the objects in the above example would not actually internally be given the name of the objects as the user entered them, but would be given a modified name indicating which table they belong to. The reason for this is that there might be two different tables in which the user entered objects having identical names. In order to avoid possible confusion, the Conversion Module 1004 adds a suffix on the end of each object identifying that object with a particular table. Thus, the Conversion Module 1004 supplies objects to the constructs if they were left off by the user, and also gives the objects an internal name to identify them with a particular table.

Once the constructs are converted by the Conversion Module 1004 as noted above, they are then acted upon by the Translate Construct Module 1006. This actually converts the constructs into an even lower-level language which can be evaluated by the present invention. For formulas and triggers, the constructs will be converted into a language which can be understood by the Object-Oriented Language With Inference Engine Tool 414. In a preferred embodiment, this language is LISP. In the case of rules and critics, these constructs are converted into a form which is executable by the inference engine portion of the Object-Oriented Language With Inference Engine Tool 414. In this way, this module 1006 can convert the constructs into a form that can be acted upon by the Object-Oriented Language With Inference Engine Tool 414.

While the Translate Construct Module 1006 is translating formulas, triggers and rules, the Add Dependency Module 1008 records any dependencies implicit in these constructs in the following fashion: For formulas, assert (as will be described below) that each object-attribute pair referred to in the right hand side (rhs) of a formula affects the object-attribute pair referred to on the left hand side (lhs). For triggers, assert the opposite--that the object-attribute pair on the lhs of the trigger affects each object-attribute pair on the rhs. For rules, assert that each object-attribute pair on the lhs of the rule affects every object-attribute pair on the rhs of that rule.

In a preferred embodiment of the present invention, dependencies for rules are not maintained for the purpose of propagating values. The propagation of values in rules is handled automatically by the Inference Engine Module 706. Dependencies for rules are maintained solely for the purpose of correctly maintaining "variables of interest", which will be described later in detail.

Dependencies are stored (that is, asserted) as "affects" (for rules as "r-affects") procedural attachments from the object-attribute pair from which they originate. This is shown in the following two examples. First, for the formula "project.return: =profit-cost", the "affects" procedural attachment to the object-attribute pair, "project.profit" is "return." The same "affects" procedural attachment is added to "project.cost."

Second, consider the trigger which indicates that if p1.taken="yes" then p5.taken: ="yes", else p7.taken: ="yes." To the object-attribute pair "pI.taken" will be added (by module 1008) the "affects" procedural attachment which is "p5.taken p7.taken."

In a preferred embodiment of the present invention, the goals are also converted into rules. This is done for ease of implementation, in that if there is at least one object variable in a goal, it is easier to convert the goal into a rule. The reason for this is that goals are not "attached" to a particular object or class, but may refer to many different objects, and thus it would be otherwise difficult to instantiate the object variable(s).

Once the constructs have been broken down to a lower level form by the Translate Construct Module 1006, and dependencies have been added by the Add Dependency Module 1008, the present invention then utilizes the Object Oriented Language With Inference Engine Tool 414. In the following description, it should be noted that modules 1008, 1010 and 1014 incorporate portions of the Tool 414. While the modules described above and below could be broken up in any number of ways, the modules are depicted and described in their current form for purposes of conceptual simplicity.

The Procedural Attachment Module 1010 creates procedural attachments out of the formula and trigger constructs. Thus, these constructs are converted into procedural attachments ("to-compute" and "has-demons", respectively), by this module 1010.

From here, block 1014 attaches the constructs (or, more specifically in the case of formulas and triggers, the procedural attachments) to their proper places. In addition to formulas and triggers, the rules, critics and goals also are attached. A more specific description of the way that these constructs are attached is described with reference to FIG. 11 below.

It is noted that the organization of the modules described above is just one embodiment of the present invention. It should be understood that the present invention contemplates other organizational schemes as well.

FIG. 11 shows how the attachment of a construct is viewed by the present invention. A data value is merely attached as a value of some object-attribute pair.

As indicated with regard to FIG. 7 above, a formula is said to be "attached" to the object-attribute pair containing the value operated upon by the operands of the formula (although it is actually the "to-compute" procedural attachment that is attached). Also as indicated above, the operands of the formula will each have an "if-set" and "affects" procedural attachment attached to them as well.

Also with regard to FIG. 7 above, a trigger is attached as a "has-demons" procedural attachment to the object-attribute pair containing the value which is to affect other object-attribute pairs. As indicated above, also attached to this object-attribute pair is at least one "affects" procedural attachment.

Regarding rules, goals, and critics, even though these constructs can be made to affect individual object-attribute pairs, they are said to actually be attached to the "table" from which they were implemented. The reason for this is that each rule, goal and critic can refer to any number of object-attribute pairs, and thus they do not really belong to one particular object-attribute pair or object class. Consequently, what is done is to attach these constructs in such a way that they are indexed so that they attach to a particular table. For example, in a preferred embodiment of the present invention, a rules attribute is established within a table that has the internal names of the different rules that belong to that table. Thus, each time a new rule is added, the name of that rule is added to the rules attribute of the table. For this particular purpose, the table itself is considered an object.

A decision variable is said to be attached to the "independents" attribute of the model. In this way, it is said to be attached to (and thus belongs to) the entire model (that is, the entire problem).

In essence, with regard to formulas and triggers, the present invention provides the user with a high-level way of writing procedural attachments. The present invention serves to break down the high-level construct into a lower-level object-oriented language that the Object-Oriented Language With Inference Engine Tool 414 can manipulate, and attach to the various entities within the object hierarchy 410. In another embodiment of the present invention, if the user were familiar with Lisp, rather than writing the construct, (s)he could write a function call that attaches a "to-compute" to an object-attribute pair and write the Lisp code directly. So in essence, part of the function of the present invention is to provide an interface to an object-oriented programming environment. Again, it must be noted that this invention can be implemented using any formal procedural language used to program general purpose computers. The presence of a Lisp interpreter only facilitates the interpretation of formula constructs, but these constructs could be interpreted directly by other interpreters, or, as an alternative, the constructs could be translated to a form, such as machine language, which can be evaluated directly by the CPU 102.

G. Operation of Dependency Machinery

The operation of the dependency machinery 412 is now described in detail below with reference to FIG. 12.

Once a problem has been represented, and the object hierarchy 410 and constructs are in place, a user will want to solve the problem (or at least determine a "good" solution). This may be done by manipulating the values of object-attribute pairs manually, by permitting the PSE 204 to do it automatically, or by some combination thereof. In any event, the dependency machinery 412 of the present invention (working in conjunction with the Object Oriented Language With Inference Engine Tool 414) will propagate the dependencies, and thus cause changes made to values of the object-attribute pairs to affect other object-attribute pairs in accordance with the problem entered by a user. As indicated above, the dependency machinery 412 of the present invention is set in motion when the value of an object-attribute pair is changed, as is shown by block 1201. When this occurs, the dependency machinery 412 causes the object hierarchy 410 to be searched for inheritable "behaviors" (see FIG. 9 and related discussion above). More specifically, the object hierarchy 410 is checked at block 1202 to see if there are any "if-set" procedural attachments attached at some level of object class. Also as indicated with regard to FIG. 9, the first object checked is the lowest member of the object hierarchy 410 (which is the actual object-attribute pair that was modified).

If no "if-set" procedural attachment is found attached directly to the object-attribute pair, then the dependency machinery 412 proceeds to search up the object hierarchy 410 (see FIG. 7 and related discussion above). At each object class, the present invention will check for any "if-set" procedural attachments that the object-attribute pair of the changed value can inherit, as indicated by decision block 1204. If none are found, then the present invention determines if the hierarchical search has reached the top level (that is, the highest object class), as indicated by block 1206. If the search has reached the top level without finding any "if-set" procedural attachments, then there were no dependencies for the object-attribute pair to inherit. Thus, the change in the value of the object-attribute pair did not have any effect on any formulas or triggers in the problem.

If the result of decision block 1206 is "no", then any rules affected by the change in value that are "ready to fire" (that is, all conditions of the rule have become true) are "fired" (that is, their actions are executed), as indicated by block 1212. The reasoning for this is explained below with regard to block 1404 in FIG. 14. If, however, an "if-set" procedural attachment is found (either directly attached to the changed object-attribute pair or else inherited), then the propagation algorithm is executed, as indicated by block 1210.

The explanation of the operation of the dependency machinery 412 up to this point accounts for the object-attribute pairs affected directly by the attached construct alone. However, it is likely that if a change in a first value causes a change in a second value by virtue of a first construct, the change in this second value will cause a change in other values by virtue of other constructs. Thus, a change in one value could cause a whole propagation of values via a multitude of constructs. The propagation algorithm mentioned above with regard to block 1210 handles these propagations in a logical fashion. This propagation algorithm is executed each time that an "if-set" procedural attachment is found. A r more detailed discussion regarding this propagation algorithm is presented below with reference to FIG. 13.

The basic premise behind the propagation algorithm 1210 is that when a value is changed in an object-attribute pair, all the object-attribute pairs that would be affected by virtue of their dependencies are put into a logical order, and any redundant recomputation is eliminated. After the order has been computed, the procedural attachments are then executed. In general, the object-attribute pairs are ordered so that their corresponding procedural attachments will be put into the order only after all values which they require have themselves been computed by other procedural attachments. For example, for the formula "return: =profit-cost", any formulas or triggers which would affect the object-attribute pair corresponding to "return" would not be evaluated until all formulas or triggers which affect the object-attribute pair corresponding to "cost" are evaluated first.

The order of propagation (that is, the order in which the object-attribute pairs are to be evaluated) is cached and pushed onto a stack so that the object-attribute pairs can be "popped off" (that is, removed) one by one during the actual execution of the propagation. In addition, caching allows the order of the propagation to be computed only once, so long as only values are manipulated. However, if any constructs themselves are added, deleted, or otherwise modified, then the order of the propagation would have to be re-computed.

The propagation algorithm described above will now be further explained with reference to FIGS. 13 and 14. The present invention first tests whether the dependencies of the changed object-attribute pair have already been cached, and therefore ordered. This is indicated by decision block 1302. Thus, what is tested is whether the problem itself has been changed (rather than just a value). If the answer to decision block 1302 is "yes", then the present invention will not re-compute the order of propagation.

If the dependencies have not been cached, then the dependencies are first translated and specified (if the corresponding objects are in non-specific form) at block 1304. This means first of all that the object-attribute pairs that will be affected by the change in the initially changed value are determined. This is accomplished by following the "affects" dependencies from the object-attribute pair having the initially changed value to all other object-attribute pairs that are directly or indirectly (that is, by virtue of other "affects" dependencies) affected.

"Translate and specify" also means that the dependencies are translated from a non-specific form into a form where the objects are specific, and thus a specific object-attribute pair is referred to. For example, assume that the formula "return: =profit-cost" has been entered by a user in the Sample Problem. Then, if the object-attribute pair "1989-p2.cost" is changed, the present invention will search up the object hierarchy 410 until it finds the dependency "year-project cost affects return." This dependency is translated and specified in this case into the dependency "1989-p2.cost affects 1989-p2.return." Any direct dependencies or inherited dependencies from "1989-p2.return" will then be translated and specified, and so on, until the entire resulting chain of dependencies has been translated and specified.

At block 1306, the order of propagation of the translated and specified dependencies is computed using a Topological Sort. The Topological Sort of the type used in this invention is standard, and can be found in most textbooks on sorting or advanced data structures. See, for example, Knuth, Donald, "The Art Of Computer Programming" (Volume I), Addison-Wesley, 1973.

In addition to sorting as indicated above, the Topological Sort also serves to detect whether the propagation is cyclic. An example of a construct that would give rise to cyclic propagation be the formula "profit: =profit+4." Such a construct would cause certain object-attribute pairs to affect themselves.

In a preferred embodiment of the present invention, the user will be alerted to the existence of a cyclic construct. However, since it is possible that the user intended to implement a cyclic construct (and in keeping with the general robust character of the present invention), the present invention will not terminate if a cyclic construct is entered. It merely will alert a user of this fact.

Once the results of the Topological Sort have been obtained, then the sorted object-attribute pairs are pushed onto a propagation queue, and cached for later use, as indicated by blocks 1308 and 1310. When cached, the dependencies are attached to the particular object-attribute pair that started the whole propagation sequence. This keeps track of what sequence of sorted object-attribute pairs are to be used when the value of a particular object-attribute pair is changed.

From the sequence of events shown above, it should be noted