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.

Description

[0001] The present application is a continuation of provisional patent application No. 60 / 116,785 filed on Jan. 21, 1999.BACKGROUND TECHNICAL FIELD[0002] This invention relates to methods and systems for allocating resources in an uncertain environment.[0003] This application is a continuation of Provisional Patent Application No. 60 / 116,785 submitted Jan. 21, 1999. By reference the following documents, submitted to the Sunnyvale Center for Innovation, Invention and Ideas (SCI.sup.3) under the US Patent and Trademark Office's Document Disclosure Program, are hereby included:1 Title Number Date Method of Allocating Resources in a Stochastic S00463 Jul. 9, 1997 Environment Method of Allocating Resources in a Stochastic S00730 Mar. 16, 1998 Environment - Further Considerations Method of Allocating Resources in a Stochastic S00743 Apr. 10, 1998 Environment -Further Considerations II Method of Allocating Resources in a Stochastic S00764 May. 11, 1998 Environment - Further Considerations ...

AI Technical Summary

Benefits of technology

[0089] A major advantage of the present invention is that stochastic resource-allocation optimization can be done using a deterministic perspective in the DeterministicOptimizer function. Deterministic resource-allocation optimization is better understood, more advanced, and simpler than prior-art stochastic optimization. (Though DeterministicOptimizer function allows a deterministic perspective, such a perspective is not required. Hence, when a human expert defines DeterministicOptimizer functionality, it is acceptable to implicitly consider uncertainty.)

[0090] The ValueAllocation function, shown in FIG. 11, jointly assesses a scenario and an allocation to determine a voa value. This value represents the desirability to have the scenario-allocation pair occur, as opposed to having any other scenario-allocation pair occur. This could entail, for example, setting voa equal to:

[0091] the objective function value realized by the DeterministicOptimizer or the NativeOptimizer functions

[0092] the cash balance at the end of the last stage

[0094] a VNM utility value based upon the monetary value at the end of the last stage

[0095] an aggregation of VNM utility values based upon monetary values at different stages

Problems solved by technology

The problem with DeLeeuw's method, and this is a frequent problem with all Detailed-calculation, is its requirement to enumerate and evaluate a list of possible resource allocations.

Frequently, because of the enormous number of possibilities, such enumeration and valuation is practically impossible.

Though there are methods to optimize the function, such methods often require significant amounts of computer time and hence are frequently impractical.

A further problem with Detailed-calculation is the difficulty of handling multiple-stage allocations.

Because dynamic programming builds upon Detailed-calculation, the problems of Detailed-calculation are exacerbated.

Further, dynamic programming is frequently difficult to apply.

Unless the resulting optimization model is a linear programming model, the usual problem with such an approach is that the resulting optimization problem is too big to be solved; and aside from size considerations, is frequently unsolvable by known solution means.

Creating a linear programming model, on the other hand, frequently requires accepting serious distortions and simplifications.

Usually, using more than two stages in a stochastic programming problem is impractical, because the above-mentioned computational problems are seriously aggravated.

Assumptions, simplifications, and multi-processor-computer techniques used in special stochastic programming situations fail to serve as a general stochastic-programming solution method.

The fundamental problem with this method is that it does not consider how the resulting allocation performs against the scenarios, nor does it make any genuine attempt to develop an allocation that, overall, performs best against all individual scenarios.

Also related to the fundamental problem of scenario analysis is its inability to accommodate utility functions in general, and von Neumann-Morgenstern (VNM) utility functions in particular.

Further still, the convergent mechanism tends to overly weigh scenarios that are highly sensitive to small allocation changes, even though it could be desirable to ignore such scenarios.

Incorporating penalties for deviating from the average allocation can be cumbersome, if not impossible, and can result in significantly complicating and protracting the solution procedure.

Though this method mitigates some of the problems with Simple-scenario analysis, the problems still remain.

Most importantly, it does not fully consider how the resulting allocation performs against all individual scenarios.

This, coupled with the disparity between objective functions used for optimization and actual objectives, results in allocations that are only fair, rather than nearly or truly optimal.

Because this method sometimes uses a mechanism similar to the convergent mechanism of Convergent-scenario analysis, the previously discussed convergent mechanism problems can also occur here.

First, penalties can introduce distortions.

Second, the process of forming tractable models can introduce other distortions.

Third, existing techniques are frequently unable to handle discrete quantities.

Fourth, constraints are not fully considered, with the result that constraints are violated with unknown ramifications, and, conversely, other constraints are overly respected.

Sixth, existing techniques can require significant computer time to compute gradients and derivatives.

Seventh, and perhaps most important, practitioners frequently do not use stochastic programming techniques, because shifting from deterministic techniques is too complex.

A frequent problem, however, is that once complicating factors are introduced, the solution techniques no longer work, and either computer-simulation Detailed-calculation or stochastic-programming methods, with their associated problems, are required.

A further problem is that such methods, in order to be mathematically tractable, frequently ignore VNM utility functions and work with unrealistically, infinitesimally small quantities and values.

In conclusion, though innumerable methods have been developed to determine how to allocate resources, they frequently are unable to cope with uncertainty.

Attempts to include uncertainty frequently result in models that are too big to be solved, unsolvable using known techniques, or inaccurate.

As a consequence, resource allocations of both organizations and individuals are not as good as they could be.

However, it may happen that fulfilling the contractual obligations becomes impossible.

Whatever course is chosen, there follows an adverse impact on the business' profits.

The more numerous and onerous the contractual obligations, the larger the adverse impact.

However, this adverse impact is always less than infinity.

Lacking better bases, both are usable and valuable.

Such allocations might result in "infeasibility" in subsequent stages, but as discussed previously, constraints can always be violated, though with consequences.

Images