System and method for representing and solving numeric and symbolic problems

• US 5,195,172 A
• Filed: 07/02/1990
• Issued: 03/16/1993
• Est. Priority Date: 07/02/1990
• Status: Expired due to Term

• Current Assignee: Quantum Leap Research, Inc.
• Original Assignee: Quantum Development Corporation
• Inventors: Johnson, Apperson H., Philips, Irene H., Elad, Joseph B., Chester, Daniel L., Kirk, Jeffrey C., Kramer, Laurence A., Zickus, Susan M., Saniga, Erwin M.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Downs, Robert W.
• Application Number:
  US07/546,447
• Time in Patent Office: 988 Days
• Field of Search: 364/513, 364/200, 364/900, 364/600, 364/419, 395/22, 395/12, 395/62, 395/925, 395/50, 395/60
• US Class Current: 706/62
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

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

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.

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.

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.

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.

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

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.