Methods apparatus for allocating resources in the presence of uncertainty

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.

What I claim is:  
     
         1 . A system for optimally allocating resources comprising: 
 a computer having at least one processor, means for data input and output, and memory means for storing data and executable programs;    said memory means 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;    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 evaluating an allocation contained in an XAlloc object against one or more scenarios of said first memory portion;    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 sixth memory portion further comprises at least one of the following executable program means: SimpleParabolaSearch, InnerCompressSearch, OuterCompressSearch, GeneticSearch for combining XAlloc objects to form new XAlloc objects; said sixth memory portion causing only preferable said new XAlloc objects to be stored in said memory portion three.  
     
     
         4 . The system for optimally allocating resources according to  claim 1 , wherein said sixth memory portion further comprises at least one of the following executable program means: StandardSearch, MiscSearch for generating XAlloc objects; said sixth memory portion causing only preferable said generated XAlloc objects to be stored in said memory portion three.  
     
     
         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; said fifth memory portion further comprising means for using said generated Guiding Beacon Scenarios.  
     
     
         6 . The system for optimally allocating resources according to  claim 5 , wherein said executable program means for generating Guiding Beacon Scenarios further includes means for generating at least one of the following types of Guiding Beacon Scenarios: Contingent, Merged, and Multiple; said means for using said generated Guiding Beacon Scenarios further includes means for using the Guiding Beacon Scenarios generated by said means for generating Guiding Beacon Scenarios.  
     
     
         7 . The method 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 sixth memory portion further stores at least one of the following executable program means: SimpleParabolaSearch, InnerCompressSearch, OuterCompressSearch, GeneticSearch for combining XAlloc objects to form new XAlloc objects; said sixth memory portion causing only preferable said new XAlloc objects to be stored in said memory portion three;    C) said sixth memory portion further stores at least one of the following executable program means: StandardSearch, MiscSearch for generating XAlloc objects; said sixth memory portion causing only preferable said generated XAlloc objects to be stored in said memory portion three.    
     
     
         8 . The method for optimally allocating resources according to  claim 1 , wherein said method 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 sixth memory portion further stores at least one of the following executable program means: SimpleParabolaSearch, InnerCompressSearch, OuterCompressSearch, GeneticSearch for combining XAlloc objects to form new XAlloc objects; said sixth memory portion causing only preferable said new XAlloc objects to be stored in said memory portion three;    C) said sixth memory portion further stores at least one of the following executable program means: StandardSearch, MiscSearch for generating XAlloc objects; said sixth memory portion causing only preferable said generated XAlloc objects to be stored in said memory portion three.    D) said sixth memory portion further stores an executable program means for generating Guiding Beacon Scenarios; said fifth memory portion further stores means for using said generated Guiding Beacon Scenarios.    
     
     
         9 . A method for optimally allocating resources, utilizing a computer having at least one processor, means for data input and output, and memory means for storing data and executable programs; said method comprising: 
 storing a plurality of scenarios in a first portion of said memory means;    storing in a second portion of said memory means an executable program means for loading said first memory portion;    storing XAlloc objects in a third portion of said memory means;    storing in a fourth portion of said memory means an executable program means for allocating resources within each said scenario stored in said first memory portion;    storing in a fifth portion of said memory means an executable program means for evaluating an allocation contained in an XAlloc object against one or more scenarios of said first memory portion;    storing in a sixth portion of said memory means 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.    
     
     
         10 . The method for optimally allocating resources according to  claim 9 , wherein 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.  
     
     
         11 . The method for optimally allocating resources according to  claim 9 , wherein said sixth memory portion further stores at least one of the following executable program means: SimpleParabolaSearch, InnerCompressSearch, OuterCompressSearch, GeneticSearch for combining XAlloc objects to form new XAlloc objects; said sixth memory portion causing only preferable said new XAlloc objects to be stored in said memory portion three.  
     
     
         12 . The method for optimally allocating resources according to  claim 9 , wherein said sixth memory portion further stores at least one of the following executable program means: StandardSearch, MiscSearch for generating XAlloc objects; said sixth memory portion causing only preferable said generated XAlloc objects to be stored in said memory portion three.  
     
     
         13 . The method for optimally allocating resources according to  claim 9 , wherein said sixth memory portion further stores an executable program means for generating Guiding Beacon Scenarios; said fifth memory portion further stores means for using said generated Guiding Beacon Scenarios.  
     
     
         14 . The method for optimally allocating resources according to  claim 13 , wherein said executable program means for generating Guiding Beacon Scenarios further includes means for generating at least one of the following types of Guiding Beacon Scenarios: Contingent, Merged, and Multiple; said means for using said generated Guiding Beacon Scenarios further including means for using the Guiding Beacon Scenarios generated by said means for generating Guiding Beacon Scenarios.  
     
     
         15 . The method for optimally allocating resources according to  claim 14 , 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 sixth memory portion further stores at least one of the following executable program means: SimpleParabolaSearch, InnerCompressSearch, OuterCompressSearch, GeneticSearch for combining XAlloc objects to form new XAlloc objects; said sixth memory portion causing only preferable said new XAlloc objects to be stored in said memory portion three.    C) said sixth memory portion further stores at least one of the following executable program means: StandardSearch, MiscSearch for generating XAlloc objects; said sixth memory portion causing only preferable said generated XAlloc objects to be stored in said memory portion three.    
     
     
         16 . The method for optimally allocating resources according to  claim 9 , wherein, 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 sixth memory portion further stores at least one of the following executable program means: SimpleParabolaSearch, InnerCompressSearch, OuterCompressSearch, GeneticSearch for combining XAlloc objects to form new XAlloc objects; said sixth memory portion causing only preferable said new XAlloc objects to be stored in said memory portion three.    C) said sixth memory portion further stores at least one of the following executable program means: StandardSearch, MiscSearch for generating XAlloc objects; said sixth memory portion causing only preferable said generated XAlloc objects to be stored in said memory portion three.    D) said sixth memory portion further stores an executable program means for generating Guiding Beacon Scenarios; said fifth memory portion further stores means for using said generated Guiding Beacon Scenarios.