Subclass 6	Subclass 7	Subclass 8
Operations research

Methods and apparatus for allocating, costing, and pricing organizational resources

6965867

Abstract

This invention is a means both to allocate all types of resources for commercial, governmental, or non-profit organizations and to price such resources. A linear programming process makes fulfillment allocations used to produce product units. A Resource-conduit process governs the linear programming process, uses two-sided shadow prices, and makes aperture allocations to allow Potential-demand to become Realized-demand. A strict opportunity cost perspective is employed, and the cost of buyable resources is deemed to be the opportunity cost of tying up cash. Resource available quantities, product resource requirements, and Potential-demand as a statistical distribution are specified in a database. The invention reads the database, performs optimization, and then writes allocation directives to the database. Also determined and written to the database are resource marginal (incremental) values and product marginal costs. The database can be viewed and edited through the invention's Graphical User Interface. Monte Carlo simulation, along with generation of supply and demand schedules, is included to facilitate analysis, explore "what if," and interact with the user to develop product offering, product pricing, and resource allocation strategies and tactics.

Claims

1. A computer system having a memory for storing data for access by an application program being executed on said computer system for allocating organizational resources, comprising:

(a) a rcMat matrix data structure stored in said memory, said rcMat matrix data structure used by said application program and including: organization resource-utilizing groups; said organization resource-utilizing groups utilizing at least some of the resources available to an organization; said rcMat matrix of organization resource-utilizing groups comprising m rows and nRes columns; said number m is at least two; said number nRes is at least one; said nRes columns of said rcMat matrix containing a plurality of organization resource-utilizing groups; said rows of said rcMat matrix containing a plurality of said organization resource-utilizing groups; at least some of said organization resource-utilizing groups containing resource allocations; and

(b) said application program including code segments for accessing said rcMat matrix to retrieve said resource allocations of said organization resource-utilizing groups to allocate at least some organizational resources.

2. The computer system according to claim 1, wherein said application program further comprises at least one of the following, a result therefrom being used for allocating organizational resources:

(a) a code segment for calculating effectiveness for said organization resource-utilizing groups;

(b) a code segment for calculating rowEffectiveness for at least some of said rows of said rcMat matrix;

(c) a code segment for calculating Realized-demand for at least some of said rows of said rcMat matrix;

(d) a code segment for valuing allocations contained in said organization resource-utilizing groups;

(e) a code segment for determining group-marginal-cost-subtract for said organization resource-utilizing groups;

(f) a code segment for determining group-marginal-value-add for said organization resource-utilizing groups;

(g) a code segment for performing a linear programming process.

3. A computer system comprising

(a) means for storing a rcMat matrix of organization resource-utilizing groups; said organization resource-utilizing groups utilizing at least some of the resources available to an organization; said rcMat matrix of or ation resource-utilizing groups comprising m rows and nRes columns; said number m is at least two; said number nRes is at least one; said nRes columns of said rcMat matrix containing a plurality of organization resource-utilizing groups; said rows of said rcMat matrix containing a plurality of said organization resource-utilizing groups; and

(b) means for performing a Resource-conduit process, said Resource-conduit process accessing said rcMat matrix, for allocating at least some of said resources available to said organization to said organization resource-utilizing groups.

4. A computer system comprising:

(a) means for storing a rcMat matrix of organization resource-utilizing groups; said organization resource-utilizing groups utilizing at least some of the resources available to an organization; said rcMat matrix of organization resource-utilizing groups comprising m rows and nRes columns; said number m is at least two; said number nRes is at least one; said nRes columns of said rcMat matrix containing a plurality of organization resource-utilizing groups; said rows of said rcMat matrix containing a plurality of said organization resource-utilizing groups; and

(b) means for performing a Resource-conduit process, said Resource-conduit process accessing said rcMat matrix, for allocating at least some of said resources available to said organization to said organization resource-utilizing groups; said Resource-conduit process comprising at least one of the following:

(i) means for initializing said rcMat matrix and said organization resource-utilizing groups of said rcMat matrix;

(ii) means for valuing allocations contained in said organization resource-utilizing groups of said rcMat matrix;

(iii) means for generating a bOrg vector;

(iv) means for performing a linear programming process.

5. The computer system according to claim 4, wherein said means for storing said rcMat matrix further stores at least one of the following:

(a) a potential demand vector;

(b) a sumWICash vector,

(c) a resQuant vector,

(d) a twpGroupSub and a twpGroupAdd vector;

(e) a rwpDest, rwpSour, rwOldAlloc, and a rwOldMC vector,

(f) a dpTie matrix and a dpTieSubBlk vector.

6. The computer system according to claim 4, wherein said means for performing a Resource-conduit process for allocating at least some of said resources available to said organization to said organization resource-utilizing groups comprises at least one of the following:

(a) means for performing an Axis-walk process;

(b) means for performing a Top-walk process;

(c) means for performing a Lateral-walk process;

(d) means for performing a Ridge-walk process;

(e) means for performing an Explode-walk process;

(f) means for performing a Rand-mode process;

(g) means for performing a Genetic-mode process;

(h) means for performing a Finalitzation process;

(i) means for determining updated values for said bOrg vector.

7. A computer system for optimally making Fulfillment-allocations, comprising:

(a) means for storing a rcMat matrix of organization resource-utilizing groups; said organization resource-utilizing groups utilizing at least some of the resources available to an organization; said rcMat matrix of organization resource-utilizing groups comprising m rows and nRes columns; said number m is at least two; said number nRes is at least one; said nRes columns of said rcMat matrix containing a plurality of organization resource-utilizing groups; said rows of said rcMat matrix containing a plurality of said organization resource-utilizing groups;

(b) means for performing a linear programming process for making at least some of said Fulfillment-allocations; and

(c) means for performing a Resource-conduit process, said Resource-conduit process accessing both said rcMat matrix and calculations of said linear programmed process, for making at least some of said Fulfillment-allocations.

8. A computer system having thereon an application program for determining the marginal value of a resource, wherein said resource is potentially used in each of a plurality of scenarios, and said marginal value is used in allocating said resource, said application program comprising:

(a) a code segment for accessing said plurality of scenarios;

(b) a code segment for performing a linear programming process to optimize resource allocations in each said scenario;

(c) a code segment for determining the marginal value of said resource;

(d) a code segment to pass said determined marginal value of said resource to a subsequent computer program routine for allocating said resource available to said organization.

9. A computer system for indirectly allocating organizational resources, comprising:

(a) means for accessing a plurality of scenarios;

(b) means for performing a linear programming process to optimize resource allocations of each said scenario;

(c) means for determining at least one marginal value of at least one resource in each optimized scenario;

(d) means for calculating a mathematical-mean of said at least one marginal value of said at least one resource in each said optimized scenario;

(e) means for calculating a mathematical-product of a quantity corresponding to said at least one resource by said mathematical-mean; and

(f) means for comparing said mathematical-product to a value to be received and, based upon a result of said comparing means, indirectly allocating organizational resources.

10. A computer-implemented method for allocating organizational resources comprising code segments for:

(a) creating and storing a rcMat matrix data structure that includes organization resource-utilizing groups; said organization resource-utilizing groups utilizing at least some of the resources available to an organization; said rcMat matrix of organization resource-utilizing groups comprising m rows and nRes columns; said number m is at least two; said number nRes is at least one; said nRes columns of said rcMat matrix containing a plurality of organization resource-utilizing groups; said rows of said rcMat matrix containing a plurality of said organization resource-utilizing groups; at least some of said organization resource-utilizing groups containing resource allocations; and

(b) retrieving said resource allocations of said organization resource-utilizing groups to allocate at least some organizational resources.

11. The computer-implemented method for allocating organizational resources according to claim 10, further comprising code segments for performing at least one of the following, and for using a result therefrom to allocate at least some organizational resources:

(a) calculating effectiveness for said organization resource-utilizing groups;

(b) calculating rowEffectiveness for at least some of said rows of said rcMat matrix;

(c) calculating Realized-demand for at least some of said rows of said rcMat matrix;

(d) valuing allocations contained in said organization resource-utilizing groups;

(e) determining group-marginal-cost-subtract for said organization resource-utilizing groups;

(f) determining group-marginal-value-add for said organization resource-utilizing groups;

(g) performing a linear programming process.

12. A method comprising:

(a) storing a rcMat matrix of organization resource-utilizing groups; said organization resource-utilizing groups utilizing at least some of the resources available to an organization; said rcMat matrix of organization resource-utilizing groups comprising m rows and nRes columns; said number m is at least two; said number nRes is at least one; said nRes columns of said rcMat matrix containing a plurality of organization resource-utilizing groups; said rows of said rcMat matrix containing a plurality of said organization resource-utilizing groups; and

(b) performing a Resource-conduit process, said Resource-conduit process accessing said rcMat matrix, for allocating at least some of said resources available to said organization to said organization resource-utilizing groups.

13. A method comprising:

(a) storing a rcMat matrix of organization resource-utilizing groups; said organization resource-utilizing groups utilizing at least some of the resources available to an organization; said rcMat matrix of organization resource-utilizing groups comprising m rows and nRes columns; said number m is at least two; said number nRes is at least one; said nRes columns of said rcMat matrix containing a plurality of organization resource-utilizing groups; said rows of said rcMat matrix containing a plurality of said organization resource-utilizing groups; and

(b) performing a Resource-conduit process, said Resource-conduit process accessing said rcMat matrix, for allocating at least some of said resources available to said organization to said organization resource utilizing groups; said Resource-conduit process comprising at least one of the following:

(i) initializing said rcMat matrix and said organization resource-utilizing groups of said rcMat matrix;

(ii) valuing allocations contained in said organization resource-utilizing groups of said rcMat matrix;

(iii) generating a bOrg vector;

(iv) performing a linear programming process.

14. The method according to claim 13, wherein said act of storing said rcMat matrix fisher includes storing at least one of the following:

(a) a potentialDemand vector;

(b) a sumWICash vector;

(c) a resQuant vector;

(d) a twpGroupSub and a twpGroupAdd vector;

(e) a rwpDest, rwpSour, rwOldAlloc, and a rwOldMC vector;

(f) a dpTie matrix and a dpTieSubBlk vector.

15. The method according to claim 13, wherein said step for performing a Resource-conduit process for allocating at least some of said resources available to said organization to said organization resource-utilizing groups comprises at least one of the following:

(a) performing an Axis-walk process;

(b) performing a Top-walk process;

(c) performing a Lateral-walk process;

(d) performing a Ridge-walk process;

(e) performing an Explode-walk process;

(f) performing a Rand-mode process;

(g) performing a Genetic-mode process;

(h) performing a Finalization process;

(i) determining updated values for said bOrg vector.

16. A method for optimally making Fulfillment-allocations, comprising:

(a) storing a rcMat matrix of organization resource-utilizing groups; said organization resource-utilizing groups utilizing at least some of the resources available to an organization; said rcMat matrix of organization resource-utilizing groups comprising m rows and nRes columns; said number m is at least two; said number nRes is at least one; said nRes columns of said rcMat matrix containing a plurality of organization resource-utilizing groups; said rows of said rcMat matrix containing a plurality of said organization resource-utilizing groups;

(b) performing a linear programming process for making at least some of said Fulfillment-allocations; and

(c) performing a Resource-conduit process, said Resource-conduit process accessing both said rcMat matrix and calculations of said linear programming process, for making at least some of said Fulfillment-allocations.

17. A computer-implemented method for determining the marginal value of a resource, wherein said resource is potentially used in each of a plurality of scenarios, and said marginal value is used in allocating said resource, said computer-implemented embodied on a computer system and comprising code segments for:

(a) accessing said plurality of scenarios;

(b) performing a linear programming process to optimize resource allocations in each said scenario;

(c) determining the marginal value of said resource;

(d) passing said determined marginal value of said resource to a subsequent computer program routine for allocating said resource available to said organization.

18. A computer-implemented method for indirectly allocating organizational resources, said computer-implemented method comprising code segments for:

(a) accessing a plurality of scenarios;

(b) performing a linear programming process to optimize resource allocations of each said scenario;

(c) determining at least one marginal value of at least one resource in each optimized scenario;

(d) calculating a mathematical-mean of said at least one marginal value of said at least one resource in each said optimized scenario;

(e) calculating a mathematical-product of a quantity corresponding to said at least one resource by said mathematical-mean; and

(f) comparing said mathematical-product to a value to be received and, based upon a result of said comparison, indirectly allocating organizational resources.

19. A computer-readable medium having stored thereon a rcMat matrix data structure comprising:

m rows and nRes columns of data, wherein said m is a number having a value of at least two and said nRes is a number having a value of at least one;

the nRes columns of said rcMat matrix data structure including data representing a plurality of organization resource-utilizing groups;

the m rows of said rcMat matrix data structure including data representing a plurality of organization resource-utilizing groups;

wherein at least some of said organization resource-utilizing groups contain resource allocations, and wherein said organization resource-utilizing groups utilizing at least some of the resources available to an organization; and

a computer-readable executable program stored on said computer-readable medium to utilize said rcMat matrix to allocate organizational resources available to said organization stored within said rcMat matrix to said organization resource-utilizing groups.

Description

BACKGROUND TECHNICAL FIELD

This invention relates to methods and systems for allocating resources, specifically to allocating resources in an optimized or near-optimized manner to best serve an organization's goals.

A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to facsimile reproduction by anyone of the patent documentation or the patent disclosure, as it appears in the Patent & Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

BACKGROUND DESCRIPTION OF PRIOR ART

As economic theory teaches, every organization—commercial, non-profit, or governmental—has limited resources, i.e., money, raw materials, personnel, real estate, equipment, etc. These limited resources need to be used to best serve an organization's goals. To do otherwise constitutes waste. The business that wastes its resources forgoes profits and risks eventually closing; the non-profit and governmental organizations that waste their resources fail in their missions, fail as institutions, and/or cost their society more than is necessary. As the increasingly competitive world-market develops, and as citizens increasingly question the actions of non-profits and governments, the importance of resource allocation intensifies.

Known methods for allocating organizational resources can be classified as either subjective, accounting, operations research/management science, or miscellany. All of these methods address the same fundamental issue faced by all organizations: which products to make, which services to perform, which projects to undertake, which resources to acquire, and which resources to divest—i.e. all-in-all, which resources to allocate for which purposes. As organizations implement these decisions, physical transformations are made in the physical world. Prices and costs are clearly key factors driving such decisions. As economic theory teaches, given the desires of the populous and the availability of resources, prices and costs are measurements of relative scarcity and serve as a means to direct resources to where they are best used; this is named "the pricing mechanism" in economics and is a keystone of the free market philosophy.

Under the subjective method, one or more people decide upon allocations in the ways that individuals and groups subjectively decide any matter. This is not objective, nor scientific, and carries with it additional well-known risks and limitations of subjective decision making.

Under accounting methods, so called "costs" are determined and used for deciding issues at hand. As has been well-known for decades, these costs are not economic costs, i.e., the costs that should be used in decision making and that are recognized by economists. By using such invalid costs, undesirable allocations can be made.

The problem with the accountant's cost, as is best known by economists and people with MBAs, is that it:

1. inappropriately includes the price paid for resources, even though such prices are frequently irrelevant to the decision at hand, which is how best to use resources.
2. does not include opportunity cost, which is the loss or waste resulting from not using a resource in its best use.

There is also the famous dilemma of whether cost, as determined by an accountant, should include fixed, sunken, and/or overhead costs. There are strong practical arguments pro and con. Resolution of this issue would significantly affect how organizations calculate costs, and in turn allocate resources. This issue has never been resolved, other than through the dictates of current fashion.

Part of the dilemma of including fixed, sunken, and/or overhead costs is how best to allocate such costs, assuming that such an allocation is going to be made. As is well known, such allocations are largely arbitrary and necessarily distort resulting "costs."

Further, the accounting approach to allocating organizational resources is unable to fine-tune allocation quantities. A priori, it is known that the more of a resource an organization has, the less the resource's marginal (or incremental) value. Accounting offers no means to determine such a marginal value, which is necessary to optimally trade-off resource cost for resource value.

In the 1980s, Activity Based Costing (ABC) was developed to handle some problems resulting from overhead becoming an ever larger component of costs. It is essentially traditional accounting, but with a refined method of allocating overhead costs. It fails to address the above-mentioned problems. ABC is contingent upon all overhead costs being allocated, even though the academic community has for decades argued against such an allocation.

The most important operations research/management science method for allocating organizational resources is linear programming. It was originally formulated by economists in the 1940s and 50s. Part of its promise was both to displace accounting as a method for allocating organizational resources and to resolve the above mentioned accounting problems. For various reasons to be discussed below, linear programming mostly failed to displace accounting as a method for allocating organizational resources. It has largely been confined to use by engineers to solve engineering problems, some of which are organizational allocation problems.

As is well known by practitioners in the field, linear programming is used to allocate some resources for organizations such as oil companies, public utilities, transportation companies, manufacturers, and military units. Though as a method of allocating organizational resources linear programming is very important to some types of organizations for some types of allocations, overall, its use for allocating organizational resources has been limited.

The linearity requirement of linear programming is obviously its most significant deficiency. It cannot handle allocations when economies of scale, economies of scope, or synergistic properties exist; nor can it mix allocating volume and non-volume correlated resources. This means, most importantly, that what are usually known as overhead resources frequently cannot be allocated using linear programming. For example, for a mass market widgets manufacture, linear programming cannot handle the allocation of design resources: a design can be shared by multiple widgets models (economies of scope) and each design used for however many units are sold (economies of scale); further, linear programming cannot: 1) allocate design resources while also considering the effects of design on manufacturing efficiency (synergy), nor 2) simultaneously allocate resources to produce widget units (mix non-volume and volume correlated resources respectively). Practically, this means that linear programming cannot usually be used to allocate some of the most important organizational resources: management time, marketing resources, research and development, product design, product engineering, etc. Linear programming is not well understood by people likely to make organizational resource allocation decisions. Many of the textbooks published in the mid-1980s contained errors in their explanation of a key concept for using linear programming, even though the concept dates back to the 1950s. See

Harper, Robert M. Jr. "Linear Programming in Managerial Accounting: A 'Misinterpretation of Shadow Prices"'Journal of Accounting Education 4 (1986) p 123-130.

Some work has been done to facilitate the use of linear programming, but such work has focused on making linear programming easier to use, presuming the user has some general understanding of linear programming. See:

Gerald Collaud and Jacques Pasquier-Boltuck "gLPS: A graphical tool for the definition and manipulation of linear problems"European Journal of Operational Research 72 (1994) p. 277-286

Harvey J. Greenberg, "Syntax-directed report writing in linear programming using ANALYZE"European Journal of Operational Research 72 (1994) p. 300-311

Asim Roy, Leon Lasdon, and Donald Plane "End-User optimization with spreadsheet models"European Journal of Operational Research 39 (1989) p. 131-137

The final problem with using linear programming for allocating organizational resources is that it implicitly assumes a static future in terms of allocations. In other words, once an allocation is made, it is presumed fixed—at least until a new formulation is made and the linear programming process is repeated. This final problem is not addressed by attempts to extend linear programming to handle stochastic or chance-constrained considerations, with or without recourse. Such attempts are focused on making fixed allocations that best endure eventualities. For many organizations, opportunities, available resources, and commitments are in constant flux—there is never a moment when all can be definitively optimized; nor is it generally administratively or technically possible to update formulations and repeat the linear programming process continuously.

What is needed by organizations whose environments are in constant flux is a means to somehow use a single linear programming optimization to make multiple ongoing ad-hoc resource allocations without repeating or resuming the linear programming optimization.

Linear programming has been extended in several overlapping directions: generalized linear programming, parametric analysis/programming, and integer programming. These extensions have concentrated mainly on broadening the theoretical mathematical scope. See:

Karen Aardal and Torbjörn Larsson, "A Benders decomposition based heuristic for the hierarchical production planning problem", European Journal of Operational Research 45 (1990) p. 4-14.)

J. F. Benders, "Partitioning procedures for solving mixed-variables programming problems", Numerische Mathematik 4 (1962) p. 238-252

George B. Dantzig, Linear Programming and Extensions—Chapter 22: "Programs With Variable Coefficients", Princeton University Press, Princeton (1963)

George B. Dantzig and Philip Wolfe, "Decomposition principle for linear programs", Operations Research 8 (1960) p. 101-111

Tomas Gal, Post-optimal Analysis, Parametric Programming and Related Topics, 2nd ed., Walter de Gruyter, Berlin (1995) (Particularly chapters 4 and 7)

Tomas Gal, "RIM multiparametric linear programming", Management Science 21 (1975) p. 567-575

Tomas Gal and Josef Nedoma, "Multiparametric Linear Programming", Management Science 18 (1972) p. 406-422

Other than integer programming's capability to handle integer variables within a linear programming construct, these extensions are of limited utility and are only for special cases. A general, practical, and useful formulation that utilizes these extensions for allocating organizational resources has not been developed.

Other operations research/management science techniques that might be used as a general means of allocating organizational resources include quadric programming, convex programming, dynamic programming, nonlinear programming, and nondifferentiable optimization. For purposes of allocating organizational resources, these techniques too are of limited utility, and only for special cases. A general, practical, and useful formulation that utilizes these techniques for allocating organizational resources has not been developed.

(For an excellent survey of the techniques of operations research/management science, see:

G. L. Nemhauser, A. H. G. Rinnooy Kan, and M. J. Todd (ed) Handbooks in Operations Research and Management Science Volume 1: Optimization North-Holland Publishing Co., Amsterdam (1989.))

Sometimes standard operations research techniques are adopted, or special techniques developed, to allocate organizational resources. Such techniques and uses are most common in military, public utility, transportation, and logistic applications. Such methods of allocation are far too specialized to be used outside the areas for which they are specifically developed.

Under the miscellany methods of allocating organizational resources, there is Cobb-Douglas, sequential decision models, the "Theory of Constraints," and internal organizational pricing. The Cobb-Douglas method, used by economists since the 1930s, entails using statistical regression to estimate the following equation:

where:

q=quantity of product produced
b_i=estimated coefficient
x_i=resource quantity used

This estimated equation is then used for economic analysis, including determining whether aggregate resource quantities (typically on a national level) should be changed. The problem with this approach is that many data points are required and that it entails a gross aggregation. Furthermore, the formulation, because it completely lacks any linearity, is frequently unrealistic.

For marketing, selling, and advertising purposes, a sequential decision model is sometimes used. A potential buyer is presumed to make a purchase decision in stages, and the goal of the seller is to be able to pass each stage. By depicting the purchase decision as a sequence of stages, such a model helps identify where effort should be focused. Such models are usually qualitative, though they may have probabilities of passage assigned to each stage. Because of its perspective and limited quantification however, the applicability of this method of allocating organizational resources has been limited to only focusing efforts within the marketing, selling, and advertising areas.

"The Theory of Constraints" focuses on identifying a single organizational constraint and then managing that constraint. The problem with this method is its presumption of a single constraint, its qualitative nature, and, to the extent to which it is quantified, its not yielding results or insights any different from applying accounting (variable costing mode) or linear programming.

Sometimes, in some organizations for some resources, an internal price is set by using the above allocation techniques and/or open market prices. (Dorfinan, p. 184, mentions using linear programming for such internal pricing.) Such internal prices are then used with the above allocation techniques to determine when and where internally priced resources should be used. When internal prices are set by, and then used in, the above allocation techniques, the techniques' flaws and limitations as previously discussed remain.

All of these methods for allocating organizational resources—subjective, accounting, operations research/management science, and miscellany—are frequently used to allocate resources across several, time periods. i.e. used for scheduling. Again, the techniques' flaws and limitations as previously discussed remain. These techniques themselves are frequently deficient, because they are unable to fully optimize resources allocations, given the various dependencies.

In conclusion, these deficiencies have come about because of various unrelated reasons. Traditional accounting reflects the problems, capabilities, and knowledge of the time it was first developed—the first third of this century—prior to most modern theoretic economic understanding. Activity Based Costing limited itself to addressing only some of the most serious problems of traditional accounting. It ignored modern theoretic economic understanding, because practical attempts to use such knowledge were frequently incorrectly done, and, consequently, undesirable allocations were made. Activity Based Costing also ignored modern economic understanding because the economic profession had not sufficiently bridged the gap between theory and practice. Linear programming never even moderately displaced accounting, because it was not sufficiently theoretically and practically known how to extend and adapt it. Other operations research techniques also never displaced accounting, partly because they were developed to solve special engineering problems and/or as academic exercises.

Hence, today, organizations are without the tools to best allocate resources; and as a consequence, their abilities to reach goals are hindered, the allocation of humanity's resources is sub-optimal, and humanity's living standard is less than what it could be. It is the solution of this problem to which the present invention is directed.

Objects and Advantages

Accordingly, besides the objects and advantages of the present invention described elsewhere herein, several objects and advantages of the invention are to:

1. Optimally, or near optimally, allocate all types of resources belonging to any type of organization to best serve its goals.
2. Provide a means that leads an organization to optimally, or near optimally, allocate all types of resources to best serve its goals.
3. Provide costs, including opportunity costs, that reflect all factors necessary for optimal decisions.
4. Provide resource marginal, or incremental, values that can be used to optimally determine whether additional resources should be acquired or resource levels reduced.
5. Resolve the decades-old dilemma of whether and how to allocate fixed, sunken, and overhead costs.
6. Handle uncertainty when allocating resources and calculating costs and values.
7. Provide an objective means for allocating all types of organizational resources.
8. Adapt and extend linear programming to displace accounting as a means for allocating organizational resources.
9. Unify existing methods of allocating organizational resources.
10. Provide a means to facilitate an analyst in applying economic theory when analyzing organizational resource allocations.
11. Provide a simple means of use that shields the user from complexity.

Still further objects and advantages will become apparent from a consideration of the ensuing description and drawings.

SUMMARY OF THE INVENTION

The foundational procedure for achieving these objects and advantages, which will be rigorously defined hereinafter, can be pictured by considering FIGS. 1 and 2.

FIG. 1 illustrates a typical computer configuration: a database 101, a bus 103, one or more user IO devices 105, one or more processors 107, linear programming memory 109, a linear programming process 111 (hereafter, LPP), Resource-conduit memory 113, and a Resource-conduit process 115 (hereafter, RCP). (FIG. 1 is explanatory and should not be construed to limit the type of computer system on which the present invention operates.)

FIG. 2 shows the Resource-conduit memory 113 in some detail. In this figure, a vector or one-dimensional array resQuant contains the available quantities of each resource. A matrix, structure, or two-dimensional array rcMat contains what are here called (resource-utilizing) groups, such as group 201. Each resource in each element of vector resQuant is allocated to the groups in the corresponding column of rcMat. The allocation to each group determines what is here called an effectiveness, which is typically both between 0.0 and 1.0 and represents a probability. For each row of rcMat, the effectivenesses of each group are multiplied together to determine the elements of vector rowEffectiveness. Vector potentialDemand contains the maximum conceivable Potential-demand for each of an organization's products; this is what could be sold if the organization had unlimited resources. Each element of vector rowEffectiveness times the corresponding element in vector potentialDemand determines constraint values (commonly known as original b values) fed into linear programming memory 109. Conceptually, these constraint values are termed here Realized-demand.

Once initial linear programming constraint values are determined, the LPP is executed and the following is iterated:

1. the results of the LPP are used to shift or adjust group allocations.
2. new linear programming constraint values are determined.
3. the linear programming memory 109 is updated.

The RCP mainly performs "aperture" allocations, while the LPP mainly performs "fulfillment" allocations. These two types of allocations are defined below. The LPP is a slave of the RCP.

Numerous other advantages and features of the invention will become readily apparent from the following detailed description of the invention and the embodiments thereof, from the claims, and from the accompanying drawings.

Theory of the Invention

Part of the underlying theory of the present invention is that all organizational allocations can be divided into either fulfillment or aperture allocations. Fulfillment allocations use resources to directly make individual product units. Using resources in this way is commonly deemed to generate so-called direct or variable costs that vary with production volume. Aperture allocations are made to keep an organization viable and able to offer its products. These types of allocations are commonly deemed to generate so called indirect, overhead, or fixed costs that do not vary by production volume. Conceivably, a resource can be used for both fulfillment and aperture purposes.

The term "aperture" reflects how the present invention deems certain allocations: as allowing Potential-demand to manifest and become Realized-demand. The fundamental purpose of a group is to transform an allocation into an effectiveness. The higher the allocation to a group, the higher the effectiveness, which results in a higher percentage of Potential-demand becoming Realized-demand. For instance, the allocation to:

Group 201 might be research and development people months; effectiveness is the percentage of Potential-demand that finds the resulting product functionality desirable.
Group 203 might be product-design months; effectiveness is the percentage of Potential-demand that finds the resulting product design desirable.
Group 205 might be advertising dollars; effectiveness is awareness bought by such dollars.

For a unit of Potential-demand to become Realized-demand, it must find the functionality desirable, it must find the design desirable, and it must be aware of the product—it must survive a series of probabilities. This sequential process is modeled here by multiplying the effectivenesses of the groups to obtain rowEffectiveness, which is in turn multiplied by potentialDemand to obtain the constraint value (Realized-demand) used in the LPP.

A group can span several rows of rcMat, and thus the group's effectiveness used for determining the values of several elements of rowEffectiveness. This row spanning means that a single aperture allocation can apply to several products simultaneously. For instance, the application of design resources might apply to, and benefit, several products simultaneously.

The rows spanned by groups in one column of rcMat can be independent of the rows spanned by groups in another column. This independence of row spanning means that products can share and not share resources in arbitrary patterns. For instance, product groupings to share and not share design resources can be independent of the product groupings to share and not share advertising resources.

The relationship between group allocation and effectiveness can be empirically determined by experience, judgment, statistical analysis, or using a coefficient of a Cobb-Douglas function. Because of the independence of the groups, the relationship between group allocation and effectiveness can be determined independently for each group. The relationship can be determined by answering the following question: "Presuming that a group's allocation is the only factor determining whether a product will be purchased, and made available for purchase, how does the probability of purchase vary as the allocation varies?" Presenting this question and being able to work the answer is a major advantage of the present invention. Heretofore, it has usually been very difficult, if not impossible, to individually and collectively analytically consider and evaluate what are here termed "aperture allocations."

(Management time is one of the most important resources an organization has. Groups can also handle such a resource: the allocation of such a resource to a group yields, as before, an effectiveness, which is the percentage of Potential-demand that survives to become Realized-demand, given that management time has been used to make the product available and desirable.)

Each resource is considered either fixed or buyable. A fixed resource is one that is available on-hand and the on-hand quantity cannot be changed. A buyable resource is one that is purchased prior to use; its availability is infinite, given a willingness and ability to pay a purchase price. A fixed resource named Working Inventory Cash (WI-cash) (loosely, working capital) is used to finance the purchase of such buyable resources. It is the lost opportunity of tying up of that cash that is the real cost of buyable resources—and not the purchase price per se.

For example, owned office space is typically a fixed resource: an organization is not apt to continuously buy and sell office space as "needs" vary. Public utility services are buyable resources, since they are frequently, if not continuously, purchased. Employees can be considered either fixed or buyable resources. If an organization generally wants to retain its employees through ups and downs, then employees are fixed resources. If an organization wants employees strictly on a day-to-day as-needed basis, then they are buyable resources. Note that for all fixed resources, including employees, periodic payments, such as salaries, are not directly considered by the present invention: the invention optimally allocates fixed resources presuming their availability is fixed; current payments for such resources is irrelevant to the decision of optimal allocation. Whether the quantities of fixed resources are increased or decreased is decided exogenously of the invention by the user. To help the user, the invention generates marginal values and demand curves that help anticipate the effects of changing fixed resource quantities.

Though this description is written using a terminology suitable for a commercial manufacturing concern, the present invention is just as applicable for commercial service, non-profit, and government entities. From the invention's perspective, a commercial service is tantamount to a commercial product—both require resources to fulfill a sale. Products and services provided by non-profits and governments also require resources, but are handled slightly differently: because such an organization doesn't usually receive a full price (value) for its products and services, the "price" used in the allocation process needs to include an estimated value to society of providing a unit of the service or product.

As will be explained, the present invention can make allocations to either maximize internal producer's surplus (IPS) or maximize cash. The first term derives from the economist's term "producer's surplus." It's called internal here because the economist's "producer's surplus" is technically a societal surplus. A strict opportunity cost perspective is employed here—IPS is profit as compared with a zero profit of doing nothing. For non-profits and government entities, IPS is a measurement of fulfilling their missions. IPS both includes non-monetary benefits received by the organization when its products are purchased and includes wear-and-tear market depreciation on equipment. When an organization's survival is at stake, non-monetary benefits and wear-and-tear market depreciation on equipment becomes irrelevant: the only thing that is relevant is increasing cash. For such situations, maximizing cash is the appropriate allocation objective.

As will be explained, the present invention can make allocations either directly or indirectly. In the direct method, the invention explicitly allocates resources. In the indirect method, the invention uses Monte Carlo simulation to estimate the opportunity cost, or value, of each resource. This opportunity cost is then used to price each resource, which determines when and where it should be used.

The major advantage of the present invention is to, for the first time, optimally allocate all types of organizational resources for all types of organizations.

DRAWING FIGURES

In the drawings, closely related Figures have the same number but different alphabetic suffixes:

FIG. 1 illustrates an explanatory computer configuration.

FIG. 2 shows a conceptual memory layout.

FIG. 3 shows a basic database schema.

FIG. 4 shows prior-art linear-programming memory.

FIG. 5 shows Resource-conduit memory.

FIG. 6 shows group head and group element data fields.

FIG. 7 shows the basic allocation process.

FIG. 8A shows a graphical depiction of allocation movements; FIG. 8B shows corresponding allocation shifts in matrix rcMat.

FIG. 9 shows the basic initialization process.

FIG. 10 shows the Axis-walk process.

FIG. 11 is a combination of FIGS. 11A and 11B, which shows the Axis-walk allocation shift in detail.

FIG. 12 shows the Top-walk process.

FIG. 13 is a combination of FIGS. 13A, 13B, and 13C, which shows the Top-Walk allocation shift in detail.

FIG. 14 shows the Lateral-walk process.

FIG. 15 is a combination of FIGS. 15A and 15B, which shows the Ridge-walk process.

FIG. 16 is a combination of FIGS. 16A and 16B, which shows the Ridge-walk allocation shift in detail.

FIG. 17 shows the basic finalization process.

FIG. 18 shows the top portion of the Graphical User Interface (GUI) distribution window.

FIG. 19 is a combination of FIGS. 19A and 19B, which shows the top portion of the GUI resources window.

FIG. 20 is a combination of FIGS. 20A and 20B, which shows the top portion of the GUI products window.

FIG. 21 shows the GUI results window.

FIG. 22 shows the preferred allocation process.

FIG. 23 shows the supply schedule generation process.

FIG. 24 shows the demand schedule generation process.

DETAILED DESCRIPTION-BASIC EMBODIMENT

While the invention is susceptible to embodiments in many different forms, there are shown in the drawings and will be described herein, in detail, the preferred embodiments of the present invention. It should be understood, however, that the present disclosure is to be considered an exemplification of the principles of the invention and is not intended to limit the spirit or scope of the invention and/or claims of the embodiments illustrated.

The basic embodiment of the present invention will be discussed first. Afterwards, the preferred embodiment, with its extensions of the basic embodiment, will be presented.

With one exception, all costs mentioned in the present invention refer to opportunity costs, which are derived from the in-progress or finalized allocations. The one exception is expenditures for buyable resources that are written to the database and shown in the GUI windows. Here, the words "cost" and "value" are almost synonymous: cost will tend to be used when a subtraction orientation is appropriate and value will tend to be used when an addition orientation is appropriate. The economist's word "marginal" means incremental or first functional derivative. Pseudo-code syntax is loosely based on 'C', C++, SQL and includes expository text. Vectors and arrays start at element 0. Indentation is used to indicate a body of code or a line continuation. Pseudo-code text overrules what is shown in the figures. Floating-point comparisons are presumed done with a tolerance that is not explicit in the figures or pseudo-code. The expression "organizational resources" refers to resources that are directly or indirectly controlled, or are obtainable, by an organization and that can be used to serve its goals.

Database

The basic embodiment of Database 101 is shown in FIG. 3. A simple quasi-relational schema is used here to facilitate understanding. It should be understood that the present invention can easily work with other schemata and database technologies, whether relational or not. There are five tables: Resource, Group, Group Association, Product, and UnitReq. The Resource Table has nRes rows and describes available resources: name (resourceName), available quantity (availQuant), used quantity (meanUse) and marginal, or incremental, value (marginalValue). The Group Table describes groups: name (groupName), resource (resourceName), the allocation-to-effectiveness function (structure atoeFnPt), allocation (meanAlloc), and marginal value. The allocation-to-effectiveness function is described using nir+1 points, which determine nir continuous line segments. These points have only non-negative coordinates and are ordered such that atoeFnPt[i].allocation<atoeFnPt[i+1].allocation, where 0<=i and i<nir-1. (To facilitate exposition, the allocation-to-effectiveness function is presumed to pass through the origin, where atoeFnPt[0] is the origin point. Also to facilitate exposition, each group is presumed to have the same number (nir) of line segments. Relaxation of these two presumptions requires several small obvious changes throughout the exposition.) The Product Table has mProd rows and describes products: name (productName), price, Potential-demand, quantity-to-produce as the result of the optimized allocation process (meanSupply), and marginal cost. The UnitReq Table describes the fulfillment quantities of resources needed to produce each product unit. The Group Association Table maps a many-to-many association relationship between the Group and the Product Tables.

Memory

FIG. 4 shows prior-art linear programming memory 109 in some detail, using standard notation: initially the m by mn matrix a contains constraint coefficients; vector b contains constraint bounds; vector c contains object coefficients; and scalar d contains the value of optimization. (The absolute value of d, i.e., |d|, is utilized here to avoid awkward wording.) Within matrix a is the standard rectangular matrix B, which, initially is an identity matrix. In the right-hand portion of matrix a are n (mProd) columns, each initially containing product resource-requirement coefficients.

Resource-conduit memory 113 is shown in further detail in FIG. 5. Matrix rcMat has m rows and nRes columns. The number of products (mProd) plus the number of resources (nRes) equals m. The vectors bHold, bOrg, rowEffectiveness, and potentialDemand each have m elements. Vector bHold holds temporary copies of vector b. The vector bOrg contains the current linear programming problem's original b vector values—the product of each element in vectors rowEffectiveness and potentialDemand. The vectors resQuant, rwpDest, rwpSour, rwOldAlloc, rwOldMC and dpTieSubBlk each have nRes elements, and each element of these vectors applies only to the corresponding column in matrix rcMat. As explained previously, vector resQuant contains the available resource quantities. The Ridge-walk process, to be described later, entails simultaneously shifting allocations from several groups to several groups. Conceptually, the source and destination groups are in separate rows of rcMat. The vector rwpDest contains pointers to the destination groups; rwpSour contains pointers to source groups; and vectors rwOldAlloc and rwOldMC contain pre-allocation-shifting destination allocations and source marginal costs respectively. For each of the mProd products, matrix dpTie has a row containing indexes of Direct-put groups, which are defined below. Vector dpTieSubBlk contains boolean values indicating whether the Direct-put groups referenced in matrix dpTie should not be used in vector rwpSour.

The Top-walk process, also to be described later, entails simultaneously transferring resources from several groups to several groups. These groups constitute a chain. The vectors twpGroupSub and twpGroupAdd identify this chain by containing pointers to groups for which the allocation is decreasing and increasing respectively. The variable twnLink contains the number of links in the chain.

The Ridge-walk process uses rwiRow as an iterator. Both Axis-walk and Top-walk avoid allocation shifts that result in rowEffectiveness[rwiRow] changing. The vector sumWICash, with mProd elements, contains the required expenditures for buyable resources to produce one unit of each of the mProd products.

A group consists of one or more of what are here termed group elements. For each group, one element is a group head, that, besides containing element data, contains data applicable to the entire group. Each row-column position of matrix rcMat is empty or contains either a group head or a group element. For any group, all elements, including the head, are in the same column of rcMat. There is at least one group head in each column of rcMat. Rows mProd through m-1 each contain a single group head; these groups have only a single element and they are termed Direct-put groups. Here, groups will be named and referenced by their locations in rcMat.

FIG. 6 shows the data contained in group heads and elements. A group head contains all the data fields of a group element; references to elements of a group implicitly include the group's head. A group head contains an allocation and a variable to hold working-temporary allocation values (allocationHold). As in the Group Table in Database 101, a group head contains an atoeFnPt structure that defines the allocation-to-effectiveness function with nir+1 points that determine nir continuous line segments. These points have only non-negative coordinates and are ordered such that atoeFnPt[i].allocation<atoeFnPt[i+1].allocation, where 0<=i and i<nir-1. Variables dedaSub and dedaAdd contain directional derivatives of the allocation-to-effectiveness function. Structure atoeFnPt is indexed by ir. Variables maxSub and maxAdd, respectively, contain the maximum decrement and increment to the allocation that can be made, such that the directional derivative of the allocation-to-effectiveness function remains the same. Variable gmcSub (group marginal cost subtract) contains the marginal cost of decreasing the group's allocation; gmvAdd (group marginal value add) contains the marginal value of increasing the group's allocation. Variable twmcSub (Top-walk marginal-cost subtract) contains the marginal cost of decreasing the group's allocation, while simultaneously: 1) making a compensatory allocation increase to the group with a head at row twcRow and column twcCol in rcMat, and 2) making a compensatory allocation decrease to the group with a head at row twcsRow in column twcCol. The variable effectiveness is the result of applying the allocation-to-effectiveness function using the current allocation; its value is copied to each group element. The variable effectivenessHold holds working-temporary effectiveness values. The variable emcSub, which is found in both group heads and elements, is the single-row marginal cost of decreasing the group's allocation; the sum of emcSub for each element in a group equals the group's gmcSub. Similarly, emvAdd is the single-row marginal value of increasing the group's allocation. The variable subBlk, found in both group heads and elements, is a boolean value indicating whether a reduction in the group's allocation should be blocked (i.e. prevented) by setting emcSub to a very large value. A group head is also a group element.

Basic Embodiment Processing Steps

The basic embodiment processing steps are shown in FIG. 7. The initialization process 701 entails loading Database 101 data into both linear programming memory 109 and Resource-conduit memory and doing initial allocations. Process 703 entails executing the LPP. Axis-walk process 705 entails iteratively shifting part of an allocation from one group to another within each column of rcMat. Top-walk process 707 entails shifting part of an allocation from one group to another, while simultaneously making a chain of compensatory allocation shifts. Lateral-walk process 709 entails performing modified Top-walk, and in turn possibly Axis-walk, iterations. Ridge-walk process 711 entails attempting to move from a local to a better, if not global, optimum. The finalization process 713 posts the results to Database 101.

Graphical Depiction

Graphical depictions of the Axis-walk, Top-walk, Lateral-walk, and Ridge-walk processes are shown in FIG. 8A. This figure shows the optimization surface holding everything constant, except: 1) the allocations to two single-element groups in the same row k of rcMat (where 0<=k and k<mProd) and 2) c[k], which is either, depending on the surface point, 0 or a constant negative value. (Note that this constancy is being pretended. In actual operation, the surface represented in FIG. 8A frequently changes as movements take place.) The horizontal axis is the allocation of one resource to one group; the backward axis is the allocation of the other resource to the other group; the vertical axis is |d|, the value being optimized. The value of |d| increases as long as either or both allocations increase, up to a saturation level, which once reached, results in no further increase in |d|. Such a saturation level is depicted by a contour curve 801, which passes through a point 835. FIG. 8B shows the upper left-hand portion of an example rcMat matrix, where each matrix element contains a group head. (FIGS. 8A and 8B and associated descriptions are used here to facilitate understanding, and should not be construed to define or bound the present invention.)

Axis-walk process 705 entails increasing the allocation of one group, as shown in the Figure by moving from a point 803 to a point 805, while decreasing the allocation of another group, which would be similar to moving on that row's surface from a point 807 to a point 809. Such a movement is done until a directional derivative changes. In terms of rcMat, such a movement corresponds to shifting an allocation from one group to another group within the same column, e.g., shifting some of the allocation of Group 821 to Group 817.

In addition to moving parallel to an axis as in Axis-walk, Top-walk process 707 also entails moving along a contour curve such as contour curve 801. Such a movement has one group's allocation increasing, while another group's allocation decreases, such that the mathematical product of the two group's effectivenesses remains constant. With the mathematical product being constant, from the perspective shown in FIG. 8A, |d| also remains constant. In terms of rcMat, this might entail, for example, shifting the allocation from Groups 821 to 817, 819 to 823, and 825 to 815. The allocation increase in Group 817 and the decrease in Group 819 leaves the product of the two groups' effectivenesses constant and corresponds to movement along contour 801. (The same is also true for the 823 and 825 group pair.) The decrease in |d|, because of the decrease in the allocation of Group 821, is more than offset by the increase in |d|, resulting from the increase allocation in Group 815.

Each Axis-walk and Top-walk shift (movement) is done until a directional derivative changes. Such a change occurs when the end-point of an allocation-to-effectiveness line segment, or the edge of a linear programming facet, is reached. The size of each shift is determined by whittling-down an entertained shifting quantity. (The word "shift" refers to shifting an allocation from one group to another group in matrix rcMat; the word "movement" refers to moving on the geometric surface. Any shift can be pictured as a movement; any movement pictured as a shift.)

Lateral-walk process 709 determines a surface just below the surface depicted in FIG. 8A, and then applies and evaluates Top-walk, and indirectly Axis-walk, iterations. This stratagem is needed because the directional derivatives used individually by both Top-walk and Axis-walk may be inter-dependent and result in an instantaneous quantum change upon starting a shift or movement.

The Ridge-walk process 711 entails serially considering each of the mProd products, and transferring, at minimum cost, allocations to groups of the considered product (rcMat row) in order to force an increase in the product's rowEffectiveness. This is done to explore the possibility of moving from one local to a higher, if not global, maximum. As FIG. 8A depicts, for the row being increased, this entails moving along a ridge or path such as that indicated by points 827, 829, 831, 833, 835, 837, and 839. (Point 831 shows an orthogonal crossing with contour line 851.) For the row or rows being decreased, this entails either moving along a similar ridge or path but in the opposite direction, or moving parallel to an axis, e.g., from a point such as point 807 to a point such as point 809.

As the Ridge-walk process proceeds, Direct-put allocations are also increased to raise the planar portion of the surface depicted in FIG. 8A.

Initialization

Initialization process 701 is shown in detail in FIG. 9 and consists of the following steps:

1. In Box 901, for each resource/row of the Database 101 Resource Table, load each availQuant into an element of vector resQuant. The first row's availQuant goes into resQuant[0], etc. For each of the mProd products/rows of the Product Table, load potentialDemand into the first mProd elements of the vector potentialDemand.

2. In Box 903, join Database 101 tables Group and Group Association, using groupname for the join. For each row of joined table, place either a group head or group element in the rcMat matrix: productName determines the row; resourceName determines the column. Place a group head in rcMat the first time each groupname is encountered; place a group element in rcMat each subsequent time a groupname is encountered. Load each group head with atoeFnPt structure data.

3. In Box 905, place Direct-put groups: place group heads along the diagonal of rcMat[mProd][0] through rcMat[m-1][nRes-1]. For these heads, set atoeFnPt[0].allocation and atoeFnPt[0]. effectiveness equal to 0; set atoeFnPt[1].allocation and atoeFnPt[1].effectiveness equal to the same very large value. Place ones (1.0) in elements mProd through m-1 of the potentialDemand vector.

4. In Box 907, for each column of rcMat, apportion the resQuant quantity to each of the group heads, i.e.,

for (j = 0; j < nRes; j++)

for (i = each group head in column j)

set rcMat[i][j].allocation = resQuant[j]/(number of group heads in

	column j of rcMat)

5. In Box 909, iterate through each column of rcMat and each element of the enumerated column that contains a group head. In other words, iterate through all group heads of rcMat. For each group head,

if (atoeFnPt[nir].allocation < allocation)

	set dedaSub = 0
	set dedaAdd = 0
	set effectiveness = atoeFnPt[nir].effectiveness
	set maxSub = allocation - atoeFnPt[nir].allocation
	set maxAdd = 0

else

find ir such that:

	atoeFnPt[ir].allocation <= allocation and
	atoeFnPt[ir + 1].allocation > allocation
	(Conceptually, atoeFnPt[nir+1].allocation, if it existed, would be

	infinity and atoeFnPt[nir+1].effectiveness would be
	atoeFnPt[nir].effectiveness.)

if (ir < nir)

set dedaAdd = the slope of line segment ir, i.e., the line

determined by points atoeFnPt[ir] and atoeFnPt[ir+1]

set maxAdd = atoeFnPt[ir+1].allocation - allocation

else

	set dedaAdd = 0
	set maxAdd = 0

if (atoeFnPt[ir].allocation not = allocation)

	set dedaSub = dedaAdd
	set maxSub = allocation - atoeFnPt[ir].allocation

else

	if (ir not = 0)
	set dedaSub = the slope of line segment ir-1
	set maxSub = allocation - atoeFnPt[ir-1].allocation

else

	set dedaSub = BIG_M
	set maxSub = 0

set effectiveness = atoeFnPt[ir].effectiveness +

dedaAdd * (allocation - atoeFnPt[ir].allocation)

set each group element effectiveness = group head effectiveness

(BIG_M is an extremely large positive number. It should be set greater than any conceivable relevant applicable number generated by this invention.)

6. In Box 911,

for (i = 0; i < m; i++)

if (group heads or elements exist in row i of rcMat)

set rowEffectiveness[i] = mathematical product of the

effectivenesses of each group head or group element in row i

else

set rowEffectiveness[i] = 1

	set bOrg[i] = rowEffectiveness[i] * potentialDemand[i]

7. In Box 913,

clear a, b, c, d

set B as an identity matrix

Place ones along diagonal a[0][m] through a[mProd-1][mn-1] of

matrix a.

For each row of the UnitReq table, set the appropriate element in matrix

	a equal to the value of reqQt: the field resourceName determines the
	appropriate row, with the first resource of the Resource Table
	corresponding to row mProd; productName determines the column, with
	the first product of the Product Table corresponding to column m.

set (vector) b = (vector) bOrg

set c[m] through c[mn-1] = prices of the mProd products as indicated in

	the product Table of Database 101

8. In Box 915,


	set all elements of matrix dpTie = -1
	for (jProd = 0; jProd < mProd; jProd++)

for (i = mProd; i < m; i++)

if (0 < a[i][m+jProd])

set dpTie[jProd][i- mProd] = i

	set rwiRow = -1
	For each group element (including group heads) in rcMat

	set subBlk = FALSE;

Initial Linear Programming Process

Once Initialization process 701 is completed, process 703 calls the LPP to maximize the formulated linear programming problem.

Axis-Walk Process

Axis-walk process 705 is shown in FIG. 10, and entails the following steps:

1. In Box 1001, iterate through each column of rcMat and each element of the enumerated column that contains a group head. For each group under consideration:

for (i = rcMat row of each group element, including the group head)

while found (find ii such that:

	• b[ii] = 0
	• B[ii][i] > 0
	• there exists a jj such that:

c[jj] < 0 and a[ii][jj] < 0)

if (ii found)

Pivot row ii as described below in Box 1117

	endwhile
	set emcSub = - c[i] * (bOrg[i]/effectiveness) * dedaSub
	if ((ir = 0 and allocation = 0) or subBlk)

set emcSub = BIG_M

while found (find ii such that:

	• b[ii] = 0
	• B[ii][i] < 0
	• there exists a jj such that:

c[jj] < 0 and a[ii][jj] < 0)

if (ii found)

Pivot row ii as described below in Box 1117

	endwhile
	set emvAdd = - c[i] * (bOrg[i]/effectiveness) * dedaAdd
	if (ir = nir)

set emvAdd = 0

set gmcSub = sum of the emcSub values for each group element

set gmvAdd = sum of the emvAdd values for each group element

2. In Box 1003, find the two groups that maximize rcMat[ia],[j].gmvAdd minus rcMat[is],[j].gmcSub, where j ranges from 0 to nRes-1, and ia and is reference group heads in column j of rcMat. Exclude from consideration groups that have elements in row rwiRow of rcMat.

3. In Diamond 1005, test whether an allocation shift from group rcMat[is][j] to group rcMat[ia][j] is worthwhile. If the answer is "Yes", proceed to Box 1007; if the answer is "No", return to calling routine.

4. In Box 1007, shift allocation as shown in FIGS. 11A and 11B and explained below.
Axis-Walk Allocation Shift

FIGS. 1A and 11B show an enlargement of Box 1007, which entails the following steps.

Steps 6 through 9 define a Box 1151.

1. In Box 1101,


	set vector bHold = vector b
	set rcMat[is][j].allocationHold = rcMat[is][j].allocation
	set rcMat[ia][j].allocationHold = rcMat[ia][j].allocation

2. In Box 1103,

set awQuant = minimum(rcMat[is][j].maxSub, rcMat[ia][j].maxAdd)

3. In Box 1105,


	set rcMat[is][j].allocation = rcMat[is][j].allocationHold - awQuant
	set rcMat[ia][j].allocation = rcMat[ia][j].allocationHold + awQuant

4. In Box 1107, apply Box 909 to groups rcMat[is][j] and rcMat[ia][j] to generate group effectivenesses.

5. In Box 1109, apply Box 911 to generate bOrg.

6. In Box 1111, set vector b equal to the product of matrix B and vector bOrg.

7. In Box 1113, if possible, find i such that:

b[i] is minimized,
b[i]<0, and
bHold[i]=0.

8. In Diamond 1115, test whether an i was found in Box 1113. If the answer is "Yes", proceed to Box 1117; if the answer is "No", proceed to Diamond 1119.

9. In Box 1117, pivot row i as described immediately below, then go to Box 1111.

set irow = row to be pivoted

Find jcol such that

	• a[irow][jcol] < 0
	• c[jcol] < 0
	• c[jcol]/a[irow][jcol] is minimized

if (jcol found)

apply prior art to pivot the simplex tableau (matrix a, vectors b and

	c, and scalar d) using a[irow][jcol] as the pivot element

10. In Diamond 1119, test whether any element of vector b is less than 0. If the answer is "Yes", proceed to Box 1121; if the answer is "No", return to calling routine.

11. InBox 1121,

Find i, such that

	b[i] < 0 and
	bHold[i]/(bHold[i] -b[i]) is minimized

set awQuant = awQuant * bHold[i]/(bHold[i] -b[i])

Generate vector b by reapplying Boxes 1105, 1107, 1109, and 1111

(Because an infinite loop may occur in Box 1151, a limit to the number of times branching from Diamond 1115 to Box 1117 is required. Once this limit is reached, Box 1151 should be exited. If Box 1151 was entered as a result of an Axis-walk, Top-walk, or Lateral-walk call, then the rcMat[is][j] and rcMat[ia][j] pair that led to the infinite loop should be directionally blocked so as to prevent a re-entrance into Box 1151. (Directional blocking is explained as part of the Top-walk process.))

Top-Walk Process

The Top-walk process considers shifting allocations from every group to every other group in each rcMat column. Because of inherent numerical accuracy limitations on most computers, it is necessary to test whether a Top-walk shift actually increased |d|, and if not, reverse the shift and block the considered group-pair shift possibility from further consideration. Such blocking can be accomplished by use of a three dimensional array of size mProd by mProd by nRes. The first index is the rcMat row of the subtraction group-head; the second index is the rcMat row of the addition group-head; and the third index is the rcMat column of the two group heads. Initially all elements of this array are set to 0; when a group pair is blocked, the appropriate element in the array is set to 1.0. Blocking is directional.

Also, because of numerical accuracy limitations, essentially a single Top-walk shift may be accomplished by many, similar, infinitesimally-small shifts; to avoid such a possibility and the associated "waste" of CPU cycles, a minimum shifting tolerance can be used. This tolerance (twQuantMin) needs to be set to a non-negative value. The smaller the value of twQuantMin, the more accurate the solution, but the more CPU cycles required.

Top-walk works with a chain of group heads, many of which are paired into uv pairs. For each pair, the u-group has its allocation increasing and the v-group has its allocation decreasing. In FIG. 8B, for example, for the 817-819 pair, group 817 is the u-group while group 819 is the v-group. Similarly for the 823-825 pair, group 823 is the u-group and 825 the v-group.

Top-walk process 707 is shown in FIG. 12, and entails the following steps:

1. In Box 1201, clear all group-pair blocking for all rcMat columns.

2. In Box 1203,

apply Box 1001

for each group element in row rwiRow of rcMat

	set emcSub = BIG_M
	set emvAdd = -BIG_M
	in element's group head

	set gmcSub = BIG_M
	set gmvAdd = -BIG_M

for (each group head in rcMat)

	set twmcSub = gmcSub
	set twcCol = -1
	set twcRow = -1
	set twcsRow = -1

set reCycle = TRUE

while (reCycle)

	set reCycle = FALSE
	for (irow = 0; irow < mProd; irow++)

if (b[irow] = 0 or irow = rwiRow)

	for (jcolu = 0; jcolu < nRes; jcolu++)
	if (rcMat[irow][jcolu] is a group head or group element)

set irowuh = group-head row index of the group that has an

element at rcMat[irow][jcolu]

if (rcMat[irowuh][jcolu].ir not = nir)

find the group head in column jcolu that has the minimum

	twmcSub value, that has a positive allocation, and that
	is not rcMat [irowuh][jcolu]; set irowcs = the row index
	of the found group head

for (jcolv = 0; jcolv < nRes; jcolv++)

if (rcMat[irow][jcolv] is a group head or element and

jcolu not = jcolv)

set irowvh = group-head row index of the group

that has an element at rcMat[irow][jcolv]

if (rcMat[irowvh][jcolv].allocation not = 0)

set lkqt = TWufvEpsilon(

	rcMat[irowuh][jcolu],
	rcMat[irowuh][colu].allocation,
	rcMat[irowvh][jcolv],
	rcMat[irowvh][jcolv].allocation)

	set mc = rc[irowcs][jcolu].twmcSub * lkqt
	for (i = each rcMat row of group

rcMat [irowuh][jcolu])

if (rcMat[i][jcolv] is not an element of

group rcMat[irowvh][jcolv])

set mc = mc -

rcMat[i][jcolu].emvAdd * lkqt

for (i = each rcMat row of group

rcMat[irowvh][jcolv])

if (rcMat[i][jcolu] is not an element of

group rcMat [irowuh][jcolu])

set mc = mc +

rcMat[i][jcolv].emcSub

if (mc < rcMat[irowvh][jcolv].twmcSub)

	set rcMat[irowvh][jcolv].twmcSub = mc
	set rcMat[irowvh][jcolv].twcRow = irowuh
	set rcMat[irowvh][jcolv].twcCol = jcolu
	set rcMat[irowvh][jcolv].twcsRow = irowcs
	set reCycle = TRUE

3. In Box 1205,

find the group pair that maximizes:

rcMat[ia][j].gmvAdd - rcMat[is][j].twmcSub,

such that:

	• j ranges from 0 to nRes-1,
	• ia and is reference group heads in column j of rcMat,
	• the group-pair with the subtraction head at rcMat[is][j] and

	addition head at rcMat[ia][j] is not blocked

4. In Diamond 1207, test whether an allocation shift from group rcMat[is][j] to group rcMat[ia][j] is possibly worthwhile. If the answer is "Yes", proceed to Diamond 1209; if the answer is "No", proceed to Diamond 1221.

5. In Diamond 1209, test whether a transfer chain would have more than a single link. Specifically,


	if (rcMat[is][j].twcCol = -1) then
	chain has only one link.

If transfer chain would have more than a single link, proceed to Box 1211; otherwise proceed to Box 1219.

6. In Box 1211, construct a chain for shifting allocations as follows:

set twpGroupSub[0] = address of rcMat[is][j]

set twpGroupAdd[0] = address of rcMat[ia][j]

	set twnLink = 1
	set xj = j
	set xis = is
	set xia = ia
	set crossOver = FALSE
	while (not crossOver and rcMat[xis][xj].twcCol not = -1)

	set xj = rcMat[xis][j].twcCol
	set xia = rcMat[xis][j].twcRow
	set xis = rcMat[xis][j].twcsRow
	set twpGroupSub[twnLink] = address of rcMat[xis][xj]
	set twpGroupAdd[twnLink] = address of rcMat[xia][xj]
	for (i = 0; i < twnLink; i++)

	if (twpGroupSub[i] = twpGroupSub[twnLink] or
	twpGroupSub[i] = twpGroupAdd[twnLink] or
	twpGroupAdd[i] = twpGroupSub[twnLink] or
	twpGroupAdd[i] = twpGroupAdd[twnLink])

set crossOver = TRUE

set twnLink = twnLink + 1

	set iSplitVer = -1
	set iSplitHor = -1
	if (crossOver)

for (i = 0; i < twnLink - 1; i++)

	{
	if (twpGroupAdd[i] = twpGroupAdd[twnLink - 1])

	set twnLink = twnLink - 1
	goto endLoop1

else if (twpGroupSub[i] = twpGroupSub[twnLink - 1])

	set iSplitVer = i
	goto endLoop1

else if (twpGroupAdd[i] = twpGroupSub[twnLink - 1])

	{
	if (twpGroupSub[i] not = twpGroupAdd[twnLink - 1])

	twpGroupSub[twnLink - 1] = twpGroupSub[i]
	set iSplitVer = i
	goto endLoop1

else

	set twnLink = twnLink - 1
	goto endLoop1

}

else if (twpGroupSub[i] = twpGroupAdd[twnLink - 1])

	set twnLink = twnLink - 1
	goto endLoop1

}

endLoop1:

for (i = 0; i < twnLink-1; i++)

if (exactly one of the following is true:

	CrossHAT(twpGroupSub[i])
	CrossHAT(twpGroupAdd[i+1]))

goto Box 1217

if (CrossHAT (twpGroupSub[twnLink-1]) and iSplitVer = -1)

	{
	for (i = 0; i < twnLink; i++)

if (CrossHAT(twpGroupSub[i]))

	{
	if (iSplitHor = -1)

set iSplitHor = i + 1

else

	set twnLink = i + 1
	goto endLoop2

}

	goto Box 1217
	}

endLoop2:

Function definition:

CrossHAT(pointer group head (pGH))

if (the group whose head is pointed to by pGH has an element in row

rwiRow of rcMat)

return TRUE

else

	return FALSE

7. In Box 1213, determine quantities and shift allocations through the chain. This is shown in detail FIG. 13 and explained below.

8. In Diamond 1215, test whether the allocation shifts through the chain proved worthwhile. If the answer is "Yes", proceed to Box 1203; if the answer is "No", proceed to Box 1217.

9. In Box 1217, block the shift group-pair with a subtraction head at rcMat[is][j] and an addition head at rcMat[ia][j] (both group heads were determined in Box 1205) from further consideration.

10. In Box 1219, apply Box 705 (Axis-walk).

11. In Diamond 1221, test whether |d| has increased since any group-pair was blocked in Box 1217. If the answer is "Yes", proceed to Box 1201; if the answer is "No", return to calling routine.
Top-Walk Allocation Shift

FIGS. 13A, 13B, and 13C show Box 1213 in detail:

1. In Box 1301, save the following to a temporary memory location that is specific to this Top-walk process:

matrix a, vectors b and c, and scalar d
matrix rcMat and all contained group head and group elements
vectors bOrg and rowEffectiveness

2. In Box 1302,


	set vector bHold = vector b

for (i = 0; i < twnLink; i++)

apply to group pointed to by twpGroupSub[i]

	set allocationHold = allocation
	set effectivenessHold = effectiveness

apply to group pointed to by twpGroupAdd[i]

	set allocationHold = allocation
	set effectivenessHold = effectiveness

3. In Box 1303, set twQuant, the initial shift quantity:

set twQuant = twpGroupAdd[0]->maxAdd

for (i = 0; i < twnLink-1; i++)

set twQuant = minimum (twQuant, twpGroupSub[i]->maxSub)

set twQuant = TWufv(

twpGroupAdd[i+1],

	twpGroupAdd[i+1]->allocation,
	twpGroupSub[i],
	twpGroupSub[i]->allocation,
	twQuant)

set twQuant = minimum (twQuant, twpGroupAdd[i+1]->maxAdd)

set twQuant = minimum (twQuant, twpGroupSub[twnLink-1]->maxSub)

The following functions are used in Box 1303 and in other Boxes of the Top-walk process. TWufv accepts a quantity being shifted out of a group v and determines the compensating quantity to shift into a group u; TWvfu does the reverse. TWufvEpsilon is the same as TWufv, except the quantity being shifted out of group v, in the mathematical limit sense, is assumed to be an infinitesimally small unit of one, while the compensatory quantity shifted into group u is a multiple of the same infinitesimally small unit.

GenEffectiveness(pointerGroup, newAllocation)

	set net = pointerGroup->effectivenessHold
	set diff = newAllocation - pointerGroup->allocationHold
	if (0 < diff)

set net = net + pointerGroup->dedaAdd * diff

else

set net = net + pointerGroup->dedaSub * diff

return net

TWufv(pointerUGroup, uAllocation, pointerVGroup, vAllocation, shift)

	set ue = GenEffectiveness(pointerUGroup, uAllocation)
	set ud = pointerUGroup->dedaAdd
	set ve = GenEffectiveness(pointerVGroup, vAllocation)
	set vd = pointerVGroup->dedaSub
	set vi = vd * shift
	return (ue * vi/(ud * (ve - vi)))

TWvfu (pointerUGroup, uAllocation, pointerVGroup, vAllocation, shift)

	set ue = GenEffectiveness(pointerUGroup, uAllocation)
	set ud = pointerUGroup->dedaAdd
	set ve = GenEffectiveness(pointerVGroup, vAllocation)
	set vd = pointerVGroup->dedaSub
	set ui = ud * shift
	return (ve * ui/(vd * (ue + ui)))

TWufvEpsilon (pointerUGroup, uAllocation, pointerVGroup, vAllocation)

	set ue = GenEffectiveness(pointerUGroup, uAllocation)
	set ud = pointerUGroup->dedaAdd
	set ve = GenEffectiveness(pointerVGroup, vAllocation)
	set vd = pointerVGroup->dedaSub
	return (uevd/udve)

TWvfuEpsilon (pointerUGroup, uAllocation, pointerVGroup, vAllocation)

	set ue = GenEffectiveness(pointerUGroup, uAllocation)
	set ud = pointerUGroup->dedaAdd
	set ve = GenEffectiveness(pointerVGroup, vAllocation)
	set vd = pointerVGroup->dedaSub
	return (udve/uevd)

4. In Box 1305, shift allocations as follows:


	set shift = twQuant
	for (i = twnLink-1; 0 <= i; i--)

set twpGroupSub[i]->allocation =

twpGroupSub[i]->allocationHold - shift

if (i = iSplitVer)

set shift = shift - twQuant

set twpGroupAdd[i]->allocation =

twpGroupAdd[i]->allocationHold + shift

if (i = iSplitHor)

	set debt = TWufv(	twpGroupAdd[iSplitHor],
		twpGroupAdd[iSplitHor]->allocation,
		twpGroupSub[twnLink-1],
		twpGroupSub[twnLink-1]->allocation,
		twQuant)

set shift = shift - debt

else

set debt = 0

if (0 < i)

	set shift = TWvfu(	twpGroupAdd[i],
		twpGroupAdd [i]- >allocationHold+debt,
		twpGroupSub[i-1],
		twpGroupSub[i-1]->allocationHold,
		shift)

generate group effectivenesses for the groups pointed to by

twpGroupSub[i] and twpGroupAdd[i] by applying Box 909

regenerate vectors rowEffectiveness and bOrg by applying Box 911

5. In Box 1307, apply Box 1001 to generate group marginal values for each group pointed to by vectors twpGroupSub and twpGroupAdd. (Note that the linear programming problem and solution is the same as it was in Box 1301.)

6. In Box 1309, do the following to determine rcMat[is][j].twmcSub, given the shifts done in Box 1305:

set mc = twpGroupSub[twnLink-1)->gmcSub

set shift = 1.0 //(infinitesimal unit)

for (i = twnLink-1; 1 <= i; i--)

	set jj = rcMat column of group pointed to by twpGroupAdd[i]
	for (ii = each rcMat row of group pointed to by twpGroupAdd[i])

if (group pointed to by twpGroupSub[i-1] does not have group

element in row ii of rcMat)

set mc = mc - rcMat[ii][jj].emvAdd * shift

if (i = iSplitVer)

set shift = shift - 1.0

if (i = iSplitHor)

	set debt = TWufvEpsilon(	twpGroupAdd[iSplitHor),
		twpGroupAdd[iSplitHor]->allocation,
		twpGroupSub[twnLink-1],
		twpGroupSub[twnLink-1]->allocation)

set shift = shift - debt

	set shift = shift * TWufvEpsilon(	twpGroupAdd[i],
		twpGroupAdd[i]->allocation,
		twpGroupSub[i-1],
		twpGroupSub[i-1]->allocation)

	set jj = rcMat column of group pointed to by twpGroupSub[i-1]
	for (ii = each rcMat row of group pointed to by twpGroupSub[i-1])

if (group pointed to by twpGroupAdd[i] does not have group

element in row ii of rcMat)

set mc = mc + rcMat[ii][jj].emcSub * shift

set rcMat[is][jj].twmcSub = mc

7. In Diamond 1311, test whether the shifting done in Box 1305 is marginally worthwhile, i.e., whether, rcMat[is][j].twmcSub<=rcMat[ia][j].gmvAdd. If the answer is "Yes", proceed to Box 1321; if the answer is "No", proceed to Box 1315.

8. In Box 1315, use bisection method search to find a new value for twQuant so that:

it is between 0 and the values set in Box 1303 and
after reapplying Boxes 1305, 1307, and 1309 the following condition is met:

9. In Box 1317, apply Box 1305.

10. In Box 1321, apply Box 1151 to generate vector b.

11. In Diamond 1329, test whether any element of vector b is less than an infinitesimal negative value. If the answer is "Yes", proceed to Box 1331; if the answer is "No", proceed to Box 1333.

12. In Box 1331, use bisection method search to find a new value for twQuant, so that:

it is between 0 and the smaller of the values as set in Boxes 1303 and 1315.
after reapplying Box 1317 and setting b=B*bOrg, the smallest element in vector b is 0 or infinitesimally smaller than 0.

14. In Box 1333,

if (twQuant < twQuantMin)

	set twQuant = minimum of twQuantMin and twQuant as set in
	Box 1303

15. In Box 1335, apply Box 1305 using the current twQuant and set b=B*bOrg.

16. In Box 1337, make the current linear programming solution feasible, by, for instance, applying the well known Dual Simplex Method.

17. In Diamond 1339, test whether |d| has increased since it was saved in Box 1301. If the answer is "Yes", return to calling routine; if the answer is "No", proceed to Box 1341.

18. In Box 1341, restore the earlier solution by restoring the data saved in Box 1301.
Lateral-Walk Process

Lateral-walk process 709 uses facReduce as a programmer-set tolerance, which needs to be slightly less than 1.0. The closer facReduce is to 1.0, the more accurate the solution, but the more CPU cycles required. Like the Top-walk process, the Lateral-walk process tracks which group-pair shifts proved undesirable and then avoids repeat consideration of such shifts. Process 709 is shown in detail in FIG. 14 and entails the following steps:

1. In Box 1401, clear all group-pair blockings.

2. In Box 1403, apply Box 1301, but use storage that is specific to this Lateral-walk process.

Also make a copy of vector potentialDemand.

3. In Box 1405,

for (i = 0; i < m; i++)

	set limitLoop = a positive integer limit value
	while (b[i] = 0 and 0 < limitLoop and

(exists j and jj such that

	B[i][j] not = 0
	B[i][jj] not = 0
	j not = jj))

	{
	set potentialDemand[i] = potentialDemand[i] * facReduce
	apply Box 911
	set b = b * bOrg
	apply box 1337
	set limitLoop = limitLoop - 1
	}

4. In Bo x 1407, apply Boxes 1203, 1205, 1207, 1209, 1211, 1213, and 1219. Exit before applying Boxes 1215 and 1221. When doing Box 1205, respect any pair-blocking done in Box 1419. When doing Box 1213, skip Diamond 1339 and Box 1341. Immediately exit Box 1219, after doing Box 1007.

5. In Box 1409, restore vector potentialDemand that was stored in Box 1403. Also


	apply Box 911
	set b = B * bOrg
	apply box 1337

6. In Diamond 1411, test whether a Top-walk allocation shift was done in Box 1407 i.e., if the answer to the condition of Diamond 1207 was "Yes." If the answer is "Yes", proceed to Diamond 1415; if the answer is "No", proceed to Diamond 1421.

7. In Diamond 1415, test whether |d| increased from its value saved in Box 1403. If the answer is "Yes", proceed to Box 1403; if the answer is "No", proceed to Box 1417.

8. In Box 1417, restore the solution saved in Box 1403.

9. In Box 1419, block the group-pair with group heads at rcMat[is ][j] and rcMat[ia][j] (as determined in Boxes 1407 and 1205) from further consideration.

10. In Diamond 1421, test whether |d| has increased since any group-pair was blocked in Box 1419. If the answer is "Yes", proceed to Box 1401; if the answer is "No", return to calling routine.
Ridge-Walk Process

Ridge-walk process 711 uses three programmer-set tolerances: rwATLrefresh, rwShiftMin, and rwShiftMax. These tolerances need to be positive. Once the increase in rowEffectiveness is greater than rwATLrefresh, the Axis-walk, Top-walk, and Lateral-walk processes are called. Tolerances rwShiftMin and rwShiftMax, with rwShiftMin<=rwShiftMax, determine the minimum and maximum allocation shift per iteration. The smaller each of these three tolerances, the more accurate the solution, but the more CPU cycles required.

Ridge-walk process 711 is shown in detail in FIGS. 15A and 15B and entails the following steps:

1. In Box 1501, use rwiRow as an iterator to continually cycle through the first mProd rows of rcMat. Continue until a complete cycle has not resulted in any increase in |d|. Specifically:


	set rwiRow =0

	set count = 0
	do

	{
	set dHold = \|d\|
	apply Box 1551
	if (\|d\| > dHold)

set count = 1

else

set count = count + 1

	set rwiRow = rwiRow + 1
	if (rwiRow = mProd)

set rwiRow = 0

}

	while (count not = mProd)
	set rwiRow = -1

2. In Box 1503,


	set all elements of vector dpTieSubBlk = FALSE
	set baseRowEffectiveness = - BIG_M

3. In Box 1505, apply Box 1301, but use storage that is specific to this Ridge-walk process.

4. In Box 1507, drag along Direct-puts: shift group allocations between the groups of row rwiRow and its Direct-put groups in order to relieve constraints on product rwiRow.

Specifically,

for (j = 0; j < nRes; j++)

if (dpTie[rwiRow][j] not = -1)

if (rcMat[rwiRow][j] is not empty)

set iRW = row of group head of the group that has an element at

rcMat[rwiRow][j]

else

set iRW = -1

	set iDP = dpTie[rwiRow][j]
	set qtRW = bOrg[rwiRow]
	set qtDP = (bOrg[iDP]) /(the value of a[iDP][m + rwiRow] as

originally set in Box 913)

while (qtDP > qtRW)

	apply Box 1001 to all groups in column j of rcMat
	ia = iDP
	is = index of group head in column j of rcMat that has the smallest

gmcSub but is not equal to iDP

if (rcMat[is][j].gmcSub = BIG_M)

break out of while loop

	set awQuant = minimum(	rcMat[ia][j].maxAdd,
		rcMat[is][j].maxSub,
		rwShiftMin)

apply Boxes 1101, 1105, 1107, 1109, 11