System and method for representing and solving numeric and symbolic problems

• US 5,428,712 A
• Filed: 11/23/1992
• Issued: 06/27/1995
• 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., Norman, William M. III, Saniga, Erwin M.
• Primary Examiner(s): Downs, Robert W.
• Application Number:
  US07/980,282
• Time in Patent Office: 946 Days
• Field of Search: 395/51, 395/12, 395/11, 395/62, 395/925, 395/600, 395/53
• US Class Current: 706/46
• 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 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. A score is maintained reflecting how closely the constraints of a particular problem are to being satisfied and the degree of progress in the direction of stated objectives of the problem.

Claims

1. A machine system for solving an optimization or constraint satisfaction problem, comprising:

a digital computer, said digital computer comprising;

one or more memory devices for storing weak and strong problem solving methods, decision variables having decision variable values, and heuristics;

first means for utilizing said weak and strong problem solving methods to manipulate the decision variable values to find at least a best balanced solution to the problem; and

second means for utilizing said heuristics to dynamically alternate between said weak and strong problem solving methods.

2. The machine system of claim 1, wherein said weak methods, used by said first means for utilizing, comprise the usage of at least one of the following techniques:

generation of a new point, star search, line search, and trycombos search.

3. The machine system of claim 1, wherein said strong methods, used by said first means for utilizing, further comprise usage of at least one of the following techniques:

simplex, unconstrained gradient, and constrained gradient.

4. The machine system of claim 1, further comprising means for generating N instances of the system for solving a problem, working in parallel on M processors, wherein each instance has a schedule to search a search space.

5. The machine system of claim 1, wherein said weak methods, used by said first means for utilizing, further comprise a penalty factor which permits constraints to be combined with a pure objective function, said weak methods also comprising means for finding a maximum/minimum penalty factor for use in said constraints combined with said pure objective function.

6. The machine system of claim 1, wherein said weak problem solving methods, used by said first means for utilizing, further comprise means for maintaining a balanced distribution of M values over N variables where N is less than, greater than, or equal to M.

7. The machine system of claim 1, wherein said weak problem solving methods, used by said first means for utilizing, further comprise means for generating new trial values within the full range for symbolic, integer and real valued decision variables.

8. The machine system of claim 1, wherein said weak problem solving methods, used by said first means for utilizing, further comprise means for dynamically determining and adjusting a best range of variation for decision variables.

9. The machine system of claim 1, wherein said weak problem solving methods, used by said first means for utilizing, further comprise means for using two local optima to move along a crease valley during optimization.

10. The machine system of claim 1, wherein said weak problem solving methods, used by said first means for utilizing, alternate between using star search trycombos, variables of interest and line search techniques and wherein said strong problem solving methods alternate between using reduced gradient, Polak Ribiere and linear optimization techniques.

11. The machine system of claim 1, wherein said weak problem solving methods, used by said first means for utilizing, further comprise means for using variables of interest in generating new points.

12. A machine system for solving an optimization or constraint satisfaction problem, comprising:

a digital computer for receiving and manipulating information in the form of user-defined targets and/or objectives of the problem, said digital computer comprising;

one or more memory devices for storing said user-defined targets and/or objectives,

a pure objective function and constraint functions representative of said user-defined targets and/or objectives, said pure objective function and constraint functions containing decision variables capable of accepting a value;

first means for performing a test on said pure objective function and constraint functions to determine local linearity; and

second means using linear techniques for manipulating said values of said decision variables to attempt to achieve said targets and/or objectives when the results of said test indicate local linearity, and using non-linear techniques for manipulating said values when the results of said test indicate local non-linearity.

13. A machine system for solving an optimization or constraint satisfaction problem, comprising:

a digital computer for receiving and manipulating information in the form of user-defined targets and/or objectives of the problem, said digital computer comprising;

one or more memory devices for storing said user-defined targets and/or objectives,

a pure objective function and constraint functions representative of said user-defined targets and/or objectives, said pure objective function and said constraint functions containing functions of decision variables capable of accepting a value;

first means for determining the proximity of constraint boundaries; and

second means for using a combination of constrained and unconstrained optimization techniques for manipulating said values of said decision variables to attempt to achieve said targets and/or objectives, based on the proximity of constraint boundaries.

14. A method for operating a digital computer to solve an optimization or constraint satisfaction problem, the digital computer having an electronic memory device for storing said problem, comprising the steps of:

(1) storing, in the electronic memory device, weak and strong problem solving methods, decision variables having decision variable values, and heuristics;

(2) utilizing said weak and strong problem solving methods to manipulate the decision variable values to find at least a best balanced solution to the problem; and

(3) using said heuristics for dynamically interleaving alternating between said weak and strong problem solving methods.

15. The method of claim 14, wherein said weak problem solving methods of said step (2) comprise the step of maintaining a balanced distribution of M values over N variables where N is less than, greater than, or equal to M.

16. The method of claim 14, wherein said weak problem solving methods of said step (2) comprise the step of generating new trial values within the full range for symbolic, integer and real valued decision variables.

17. The method of claim 14, wherein said weak problem solving methods of said step (2) comprise the step of dynamically determining and adjusting a best range of variation for decision variables.

18. The method of claim 14, wherein said weak problem solving methods of said step (2) comprise the step of using two local optima to move along a crease valley during optimization.

19. The method of claim 14, wherein said weak and strong problem solving methods of said step (2) comprise the step of combining a plurality of objective functions in a scheme which infers weight and scale factors for a combined objective function.

20. The method of claim 14, wherein said weak problem solving methods of said step (2) comprise the step of using variables of interest in generating new points.

21. The method of claim 14, wherein said weak methods comprise the step of using at least one of the following techniques:

generation of a new point, star search, line search, and trycombos search.

22. The method of claim 14, wherein said strong methods comprise the step of using at least one of the following techniques:

simplex, unconstrained gradient, and constrained gradient.

23. The method of claim 14, further comprising the step of generating N instances of the method for solving a problem, working in parallel on N processors, wherein each instance has a schedule to search a search space.

24. The method of claim 14, wherein said weak methods comprise the step of using a penalty factor permitting constraints to be combined with a pure objective function, said weak methods also comprising the step of finding a maximum/minimum penalty factor for use in said constraints combined with said pure objective function.

25. A method for operating a digital computer to solve an optimization or constraint satisfaction problem, wherein the problem comprises a set of constraint and/or objective functions, said digital computer having an electronic memory device for storing said problem, comprising the steps of:

(1) creating a pure objective function and constraint functions representative of user-defined targets and/or objectives of the problem in the electronic memory device, said pure objective function and said constraint functions containing functions of decision variables capable of accepting a value;

(2) determining the proximity of constraint boundaries; and

(3) using a combination of constrained and unconstrained optimization techniques for manipulating said values of said decision variables to attempt to achieve said targets and/or objectives, based on the proximity of constraint boundaries.

26. The method of claim 25, wherein said step (3) further comprises the step of alternating between using reduced gradient, Polak Ribiere and linear optimization techniques.

27. The method of claim 25, wherein said step (3) comprises the step of empirically determining when a problem is locally linear, and using gradient information as coefficients for a phase of linear optimization.

28. The method of claim 25, wherein said step (3) comprises the step of maintaining a measure of the degree of non-linearity of said constraint boundaries and using said measure to manipulate said values of said decision variables to keep the search within the boundaries of the constraints.

29. The method of claim 25, comprising the step of employing said constrained and unconstrained optimization techniques so that solutions to the problem will approach feasibility if feasibility is not possible or will maintain feasibility if feasible points are found.

30. A device for representing and solving problems in the form of objects, attributes and constructs, comprising:

a computer-readable medium for use with a digital computer;

a first module for parsing and translating said constructs 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 from said machine evaluable form;

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

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 alternating between said weak and strong methods;

said computer-readable medium for storing computer program logic representative of said objects, attributes and constructs and of said modules.