FRAMEWORK FOR FINDING ONE OR MORE SOLUTIONS TO A PROBLEM

• US 20110137830A1
• Filed: 10/01/2010
• Published: 06/09/2011
• Est. Priority Date: 12/04/2009
• Status: Active Grant

• Current Assignee: The MathWorks, Inc.
• Original Assignee: The MathWorks, Inc.
• Inventors: KERR-DELWORTH, Paul, LURIE, Roy, OZYURT, Burhanettin Derya
• Granted Patent: US 9,026,478 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 7/06 Simulation on general purpose computers

Abstract

In an embodiment, information for use in identifying a plurality of sub-solvers may be acquired. The plurality of sub-solvers may be used in a first attempt to find at least one solution to a problem that may be defined in the acquired information. At least two of the sub-solvers in the plurality of sub-solvers may be of different sub-solver types. The sub-solvers may be identified based on the acquired information. One or more starting points for the identified sub-solvers may be identified and transferred to the identified sub-solvers. One or more outputs, that indicate one or more results associated with the first attempt to find at least one solution to the problem, may be acquired from the identified sub-solvers. One or more sub-solvers may be identified, based on the acquired one or more outputs, for use in a second attempt to find at least one solution to the problem.

Claims

1. A method comprising:

acquiring information for use in identifying a first plurality of sub-solvers, the first plurality of sub-solvers being used in a first attempt to find at least one solution to a problem;

identifying the first plurality of sub-solvers based on the acquired information;

identifying one or more starting points for the identified first plurality of sub-solvers;

transferring one or more of the identified starting points to one or more sub-solvers in the identified first plurality of sub-solvers;

acquiring one or more outputs from the identified first plurality of sub-solvers, the one or more outputs indicating one or more results associated with the first attempt to find at least one solution to the problem by the identified first plurality of sub-solvers; and

identifying a second plurality of sub-solvers for use in a second attempt to find at least one solution to the problem, the second plurality of sub-solvers being identified based on the acquired one or more outputs.

2. The method of claim 1, wherein the second plurality of sub-solvers includes one or more sub-solvers in the first plurality of sub-solvers.

3. The method of claim 1, further comprising:

identifying one or more starting points for one or more of sub-solvers in the second plurality of sub-solvers;

transferring one or more of the starting points, identified for one or more of sub-solvers in the second plurality of sub-solvers, to one or more sub-solvers in the second plurality of sub-solvers; and

acquiring one or more outputs from the identified second plurality of sub-solvers, the one or more outputs indicating one or more results associated with the second attempt to find one or more solutions to the problem by the identified second plurality of sub-solvers.

4. The method of claim 3, further comprising:

identifying a solution to the problem, the solution to the problem being identified based on at least one of;

one or more acquired outputs associated with the first attempt to find a solution to the problem, or

one or more acquired outputs associated with the second attempt to find a solution to the problem.

5. The method of claim 1, wherein one or more of the identified starting points are identified from a domain in a domain space associated with the problem.

6. The method of claim 1, further comprising:

saving one or more of the identified starting points in a cache.

7. The method of claim 6, wherein identifying the one or more starting points further comprises:

identifying one or more of the starting points from the cache.

8. The method of claim 1, wherein identifying the one or more starting points further comprises:

generating at least one of the starting points using a function.

9. The method of claim 1, wherein identifying the one or more starting points further comprises:

acquiring one or more of the starting points.

10. The method of claim 9, wherein one or more of the acquired starting points are acquired from at least one of:

a user interface,

a database,

a simulation,

a file,

a communications network, or

a generator function.

11. The method of claim 1, wherein identifying the one or more starting points further comprises:

generating the one or more starting points based on at least one of;

one or more settings, or

one or more domain definitions of a domain space for the problem.

12. The method of claim 11, wherein the one or more settings include at least one of:

a number of starting points to generate,

a lower bound for the one or more starting points, or

an upper bound for the one or more starting points.

13. The method of claim 1, further comprising:

providing an indication of progress towards attempting to find the solution to the problem.

14. The method of claim 1, further comprising:

adjusting one or more sub-solvers in the identified first plurality of sub-solvers; and

including one or more of the adjusted sub-solvers in the second plurality of sub-solvers.

15. The method of claim 14, wherein one or more of the adjusted sub-solvers are adjusted based on one or more outputs acquired from the first plurality of sub-solvers.

16. The method of claim 1, wherein the information includes an identifier used to identify one or more of the sub-solvers in at least one of:

the first plurality of sub-solvers, or

the second plurality of sub-solvers.

17. The method of claim 1, further comprising:

establishing one or more settings associated with at least one of;

one or more of sub-solvers in the first plurality of sub-solvers, or

one or more of sub-solvers in the second plurality of sub-solvers.

18. The method of claim 17, wherein one or more of the established settings includes an identifier of a function that is called by at least one of:

one or more of sub-solvers in the first plurality of sub-solvers, or

one or more of sub-solvers in the second plurality of sub-solvers.

19. The method of claim 1, wherein the information includes at least one of:

a constraint associated with the problem,

a limit of a solution space for the problem, or

a set of one or more equations used by at least one of;

one or more sub-solvers in the first plurality of sub-solvers, or

one or more sub-solvers in the second plurality of sub-solvers.

20. The method of claim 1, wherein the information includes at least one of:

a specification of a sub-solver/problem pair, or

a constraint function that is used to identify a constraint for at least one of;

one or more sub-solvers in the first plurality of sub-solvers, or

one or more sub-solvers in the second plurality of sub-solvers.

21. The method of claim 1, wherein a result indicated by an output is whether a sub-solver, in the first plurality of sub-solvers, has found a solution to the problem.

22. The method of claim 1, wherein a result indicated by an output is a solution to the problem.

23. The method of claim 1, wherein at least one of:

a first sub-solver in the first plurality of sub-solvers is a numeric solver and a second sub-solver in the first plurality of sub-solvers is a symbolic solver, or

a first sub-solver in the second plurality of sub-solvers is a numeric solver and a second sub-solver in the second plurality of sub-solvers is a symbolic solver.

24. One or more tangible computer-readable storage media for storing computer-executable instructions executable by processing logic, the media storing one or more instructions for:

acquiring information for use in identifying a plurality of sub-solvers, the plurality of sub-solvers being used in a first attempt to find at least one solution to a problem;

identifying the plurality of sub-solvers based on the acquired information;

identifying one or more starting points for the identified plurality of sub-solvers;

transferring one or more of the identified starting points to one or more sub-solvers in the identified plurality of sub-solvers;

acquiring one or more outputs from the identified plurality of sub-solvers, the one or more outputs indicating one or more results associated with the first attempt to find at least one solution to the problem by the identified plurality of sub-solvers; and

identifying one or more sub-solvers for use in a second attempt to find at least one solution to the problem, the one or more sub-solvers for use in the second attempt being identified based on the acquired one or more outputs.

25. The computer-readable storage media of claim 24, wherein the description of the problem contains one or more identifiers that is used to identify one or more sub-solvers in the plurality of sub-solvers.

26. The computer-readable storage media of claim 24, wherein the description includes information that is used to identify one or more of the starting points.

27. The computer-readable storage media of claim 24, wherein one or more of the starting points are identified based on one or more criteria, the one or more criteria including at least one of:

a number of starting points to generate,

a lower bound for the one or more starting points, or

an upper bound for the one or more starting points.

28. The computer-readable storage media of claim 24, further comprising one or more instructions for:

storing one or more of the starting points in a cache.

29. The computer-readable storage media of claim 28, wherein one or more of the starting points are identified from the cache.

30. The computer-readable storage media of claim 28, wherein the cache is used to at least one of:

identify a starting point that has already been used by one or more of sub-solvers, in the plurality of sub-solvers, in an attempt to find a solution to the problem,

identify a starting point that is a predefined distance from the starting point that has already been used by the one or more sub-solvers in the attempt to find a solution to the problem, or

place a limit on a total number of starting points that are identified.

31. The computer-readable storage media of claim 24, wherein at least one of:

a first sub-solver in the first plurality of sub-solvers is a numeric solver and a second sub-solver in the first plurality of sub-solvers is a symbolic solver, or

a first sub-solver in the second plurality of sub-solvers is a numeric solver and a second sub-solver in the second plurality of sub-solvers is a symbolic solver.

32. A system comprising:

a processor for;

acquiring information for use in identifying a plurality of sub-solvers, the plurality of sub-solvers being used in a first attempt to find at least one solution to a problem,

identifying the plurality of sub-solvers based on the acquired information,

identifying one or more starting points for the identified plurality of sub-solvers,

transferring one or more of the identified starting points to one or more sub-solvers in the identified plurality of sub-solvers,

acquiring one or more outputs from the identified plurality of sub-solvers, the one or more outputs indicating one or more results associated with the first attempt to find at least one solution to the problem by the identified plurality of sub-solvers, and

identifying one or more sub-solvers for use in a second attempt to find at least one solution to the problem, the one or more sub-solvers for use in the second attempt being identified based on the acquired one or more outputs.

33. The system of claim 32, wherein the information includes information that describes at least a portion of the problem.

34. The system of claim 32, wherein at least one of:

a first sub-solver in the first plurality of sub-solvers is a numeric solver and a second sub-solver in the first plurality of sub-solvers is a symbolic solver, or

a first sub-solver in the second plurality of sub-solvers is a numeric solver and a second sub-solver in the second plurality of sub-solvers is a symbolic solver.