Methods and apparatus for allocating resources in the presence of uncertainty

• US 6,219,649 B1
• Filed: 07/06/1999
• Issued: 04/17/2001
• Est. Priority Date: 01/21/1999
• Status: Expired due to Fees

• Current Assignee: Joel Jameson
• Original Assignee: Joel Jameson
• Inventors: Jameson, Joel
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): Hayes, John W.
• Application Number:
  US09/348,889
• Time in Patent Office: 651 Days
• Field of Search: 705/8, 705/7, 705/1, 705/400, 700/36, 700/95, 700/99
• US Class Current: 705/7.12
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: G06Q 10/0637 Strategic management or analysis, e.g. setting a goal or target of an organisation; Planning actions based on goals; Analysis or evaluation of effectiveness of goals

Abstract

A method of allocating resources in the presence of uncertainty is presented. The method builds upon deterministic methods and initially creates and optimizes scenarios. The invention employs clustering, line-searching, statistical sampling, and unbiased approximation for optimization. Clustering is used to divide the allocation problem into simpler sub-problems, for which determining optimal allocations is simpler and faster. Optimal allocations for sub-problems are used to define spaces for line-searches; line-searches are used for optimizing allocations over ever larger sub-problems. Sampling is used to develop Guiding Beacon Scenarios that are used for generating and evaluating allocations. Optimization is made considering both constraints, and positive and negative ramifications of constraint violations. Applications for capacity planning, organizational resource allocation, and financial optimization are presented.

Claims

1. A computer system for optimally allocating resources comprising:

a first memory portion storing a plurality of scenarios;

a second memory portion storing an executable program means for loading said first memory portion;

a third memory portion for storing a plurality of XAlloc objects, each XAlloc object capable of containing resource allocations;

a fourth memory portion storing an executable program means for allocating resources within each said scenario stored in said first memory portion;

a fifth memory portion storing an executable program means for generating an additional XAlloc object based upon at least two existing XAlloc objects; and

evaluating the allocation contained in said generated additional xAlloc object;

a sixth memory portion for storing an executable program means for calling executable program means of said second, fourth, and fifth memory portions and for performing executable program means on said first and third memory portions to optimally allocate said resources.

2. The system for optimally allocating resources according to claim 1, wherein said sixth memory portion further comprises an executable program means for clustering said scenarios of said first memory portion;

said first memory portion further comprises a means for storing said clusters;

said sixth memory portion further comprises an executable program means for utilizing said clusters to optimally allocate said resources.

3. The system for optimally allocating resources according to claim 1, wherein said fifth memory portion further comprises at least one of the following executable program means:

SimpleParabolaSearch, InnerCompressSearch, OuterCompressSearch, and GeneticSearch for generating said additional XAlloc object.

4. The system for optimally allocating resources according claim 1, wherein said fifth memory portion further comprises at least one of the following executable program means:

StandardSearch, and MiscSearch for generating said additional XAlloc object.

5. The system for optimally allocating resources according to claim 1, wherein said sixth memory portion further comprises an executable program means for generating Guiding Beacon Scenarios.

6. The system for optimally allocating resources according to claim 5, wherein the Guiding Beacon Scenarios include at least one of the following types:

Contingent, Merged, and Multiple.

7. The system for optimally allocating resources according to claim 6, wherein, at least one of the following:

A) said sixth memory portion further stores an executable program means for clustering said scenarios of said first memory portion;

said first memory portion further stores said clusters;

said, sixth memory portion further stores an executable program means for utilizing said clusters to optimally allocate said resources;

B) said fifth memory portion further stores at least one of the following executable program means;

SimpleParabolaSearch, InnerCompressSearch, OuterCompressSearch, and GeneticSearch for combining XAlloc objects to form additional XAlloc objects; and

C) said fifth memory portion further stores at least one of the following executable program means;

StandardSearch, and MiscSearch for generating additional XAlloc objects based upon at least one existing XAlloc object.

8. The system for optimally allocating resources according to claim 1, wherein said system further comprises at least two of the following:

A) said sixth memory portion further stores an executable program means for clustering said scenarios of said first memory portion;

said first memory portion further stores said clusters;

said sixth memory portion further stores an executable program means for utilizing said clusters to optimally allocate said resources;

B) said fifth memory portion further stores at least one of the following executable program means;

SimpleParabolaSearch, InnerCompressSearch, OuterCompressSearch, and GeneticSearch for combining XAlloc objects to form additional XAlloc objects;

C) said fifth memory portion further stores at least one of the following executable program means;

StandardSearch, and MiscSearch for generating additional XAlloc objects based upon at least one existing XAlloc object; and

D) said sixth memory portion further stores an executable program means for generating Guiding Beacon Scenarios.

9. A computer implemented method for optimally allocating resources comprising:

obtaining a plurality of scenarios;

allocating resources within each said scenario;

generating an additional allocation based upon at least two existing allocations and evaluating said generated additional allocation; and

determining an Optimal Final Allocation.

10. The method for optimally allocating resources according to claim 9, further comprising clustering said scenarios of said plurality of scenarios to form clusters and utilizing said clusters to determine said Optimal Final Allocation.

11. The method for optimally allocating resources according to claim 9, further comprising performing at least one of the following:

SimpleParabolaSearch, InnerCompressSearch, OuterCompressSearch, and GeneticSearch for generating said additional allocation.

12. The method for optimally allocating resources according to claim 9, further comprising at least one of the following:

StandardSearch, and MiscSearch for generating said additional allocation.

13. The method for optimally allocating resources according to claim 9, further comprising generating Guiding Beacon Scenarios.

14. The method for optimally allocating resources according to claim 13, wherein said Guiding Beacon Scenarios include at least one of the following types:

Contingent, Merged, and Multiple.

15. The method for optimally allocating resources according to claim 14 further comprising at least one of the following:

A) clustering said scenarios of said plurality of scenarios forming clusters and utilizing said clusters to optimally allocate said resources;

B) performing at least one of the following;

SimpleParabolaSearch, InnerCompressSearch, OuterCompressSearch, and GeneticSearch to form additional allocations; and

C) performing at least one of the following;

StandardSearch, and MiscSearch to form additional allocations.

16. The method for optimally allocating resources according to claim 9 further comprising at least two of the following:

A) clustering said scenarios of said plurality of scenarios forming clusters and utilizing said clusters to optimally allocate said resources;

B) performing at least one of the following;

SimpleParabolaSearch, InnerCompressSearch, OuterCompressSearch, and GeneticSearch to form additional allocations;

C) performing at least one of the following;

StandardSearch, and MiscSearch to form additional allocations; and

D) generating Guiding Beacon Scenarios.

17. A computer system comprising:

means for obtaining at least two scenarios;

means for obtaining at least first-stage scenario allocations for said at least two scenarios; and

means for determining an Optimal Final Allocation, said means including at least one of the following;

means for both generating additional allocations based upon at least two existing allocations and evaluating said generated allocations;

means for resolving infeasibilities when evaluating an allocation against a scenario of said at least two scenarios;

means for evaluating first-stage allocations using Guiding Beacon Scenarios;

means for using clusters of scenarios as sub-problems to develop said Optimal Final Allocation;

means for converting the results of an evaluation of an allocation against a scenario of said at least two scenarios to a value, said value used by said means for determining said Optimal Final Allocation;

means for determining a utility value of the fit between a genuine portfolio and an imitation portfolio; and

means for performing both NativeOptimization and DeterministicOptimization, in which said NativeOptimization and DeterministicOptimization have different optimization objectives.

18. The computer system according to claim 17, wherein said means for resolving infeasibilities include means for performing DeterministicOptimization.

19. The computer system according to claim 17, wherein said means for converting the results of an evaluation include means for performing ValueAllocation.

20. The computer system according to claim 17, wherein said means for both generating additional allocations based upon at least two existing allocations and evaluating said generated allocations further comprises a means for performing at least one of the following:

SimpleParabolaSearch, InnerCompressSearch, OuterCompressSearch, GeneticSearch, StandardSearch, and MiscSearch.

21. The computer system according to claim 17, wherein said means for evaluating said first-stage allocations using Guiding Beacon Scenarios further comprises at least one of the following:

means for selecting the Guiding Beacon Scenarios from amongst said at least two scenarios;

means for generating Contingent-GBSs;

means for generating Merged-GBSs; and

means for generating Multiple-GBSs.

22. The computer system according to claim 17, wherein said clusters includes at least one of the following:

clusters based upon scenario allocations, clusters based upon scenario specifications, and Modal clusters.

23. The computer system according to claim 19, wherein said means for performing ValueAllocation yields a von Neumann-Morgenstern utility value.

24. The computer system according to claim 19, wherein said means for performing ValueAllocation utilizes a von Neumann-Morgenstern utility function defined by at least two points.

25. A computer system for optimizing financial portfolios comprising:

means for obtaining at least two scenarios;

means for obtaining at least first-stage scenario allocations for said at least two scenarios; and

means for determining an Optimal Final Allocation comprising means for evaluating first-stage allocations.

26. The computer system according to claim 25, wherein said means for determining said Optimal Final Allocation further comprises at least one of the following:

means for generating additional allocations based upon at least two existing allocations; and

means for resolving infeasibilities when evaluating an allocation against a scenario.

27. The computer system according to claim 26, wherein said means for determining said Optimal Final Allocation further comprises at least one of the following:

means for evaluating first-stage allocations using Guiding Beacon Scenarios;

means for using clusters of scenarios as sub-problems to develop said Optimal Final Allocation;

means for converting the results of an evaluation of an allocation against a scenario to a von Neumann-Morgenstern utility value; and

means for determining a utility value of the fit between a genuine portfolio and an imitation portfolio.

28. A computer system for optimally allocating organizational resources comprising:

means for obtaining at least two scenarios;

means for optimizing and re-optimizing allocations within each scenario of said at least two scenarios, separately; and

means for determining an Optimal Final Allocation.

29. A method comprising:

obtaining at least two scenarios;

obtaining at least the first-stage scenario allocations for said at least two scenarios; and

determining an Optimal Final Allocation including at least one of the following;

generating additional allocations based upon at least two existing allocations and evaluating said generated allocations;

resolving infeasibilities when evaluating an allocation against a scenario of said at least two scenarios;

evaluating first-stage allocations using Guiding Beacon Scenarios;

using clusters of scenarios as sub-problems to develop said Optimal Final Allocation;

converting the results of an evaluation of an allocation against a scenario of said at least two scenarios to a value, said value further used by said step of determining said Optimal Final Allocation;

determining a utility value of the fit between a genuine portfolio and an imitation portfolio; and

performing both NativeOptimization and DeterministicOptimization, in which said NativeOptimization and DeterministicOptimization have different optimization objectives.

30. The method according to claim 29, wherein said step of resolving infeasibilities includes performing DeterministicOptimization.

31. The method according to claim 29, wherein said step of converting the results includes performing ValueAllocation.

32. The method according to claim 29, wherein said step of generating additional allocations based upon at least two existing allocations and evaluating said generated allocations further includes a step of performing at least one of the following:

SimpleParabolaSearch, InnerCompressSearch, OuterCompressSearch, GeneticSearch, StandardSearch, and MiscSearch.

33. The method according to claim 29, wherein said step of evaluating first-stage allocations using Guiding Beacon Scenarios further comprises at least one of the following steps:

selecting Guiding Beacon Scenarios from amongst said at least two scenarios;

generating Contingent-GBSs;

generating Merged-GBSs; and

generating Multiple-GBSs.

34. The method according to claim 29, wherein said step of using clusters of includes at least one of the following steps:

forming clusters based upon scenario allocations;

forming clusters based upon scenario specifications; and

forming Modal clusters.

35. The method according to claim 31, wherein said step of performing ValueAllocation yields a von Neumann-Morgenstern utility value.

36. The method according to claim 31, wherein said step of performing ValueAllocation utilizes a von Neumann-Morgenstern utility function defined by at least two points.

37. A computer implemented method for optimizing financial portfolios comprising:

obtaining at least two scenarios;

obtaining at least first-stage scenario allocations for said at least two scenarios; and

determining an Optimal Final Allocation comprising evaluating first-stage allocations.

38. The method according claim 37, further comprising at least one of the following steps:

generating additional allocations based upon at least two existing allocations; and

resolving infeasibilities when evaluating an allocation against a scenario.

39. The method according claim 38, further comprising at least one of the following steps:

evaluating first-stage allocations using Guiding Beacon Scenarios;

using clusters of scenarios as sub-problems to develop said Optimal Final Allocation;

converting the results of an evaluation of an allocation against a scenario to a von Neumann-Morgenstern utility value; and

determining a utility value of the fit between a genuine portfolio and an imitation portfolio.

40. A computer implemented method for optimally allocating organizational resources comprising:

obtaining at least two scenarios;

optimizing and re-optimizing allocations within each scenario of said at least two scenarios, separately; and

determining an Optimal Final Allocation.