Methods and apparatus for efficient resource allocation

A method of allocating available user facilities among a plurality of users so as to reduce the cost of providing said facilities, said method comprising the steps of

• tentatively and iteratively reassigning said facilities among said users so as to reduce said costs at each said reassignment,
• each said iterative reassignment being determined by centralizing the previous assignment with respect to constraints on said allocations,
• terminating said iterative reassignment step when said costs are at a below a preselected limit, and
• allocating said available user facilities among said users in accordance with the final iterative reassignment.

An optimized resource allocation system comprising:

• a first plurality of physical resources available for use,
• a second plurality of resource users using said physical resources, and
• means for assigning said resource users to said physical resources so as to reduce the cost of providing said resources, said assigning means including
• means for iteratively and tentatively selecting feasible ones of said assignments such that, at each iteration, each of said feasible assignments is centered within the interior of a normalized multidimensional convex feasible solution space, and
• means for allocating said physical resources in accordance with the final one of said tentative assignments.

A system for optimizing the performance of a controlled process in accordance with an optimizing criterion, said system comprising:

• process control devices for controlling said process in response to control signal sets,
• a plurality of sensors for sensing variable conditions affecting the operation of said process,
• a plurality of data input devices for prescribing conditions affecting the operation of said process, and
• a linear programming controller responsive to said sensors and said input devices for providing optimum control signal sets to said process control devices,
• said controller including means for iteratively identifying successive tentative strictly feasible control signal sets and selecting each next tentative control signal set in the direction of the steepest gradient of a normalized version of said optimizing criteria.

A controller for optimizing the operation of a controlled system comprising:

• means for determining the physical constraints and constraint limits on the operation of said system,
• means for prescribing performance measurement criteria for the operation of said system,
• means for successively identifying tentative sets of operational control values strictly satisfying said constraints and said constraint limits,
• means for normalizing said tentative sets of control values so as to equidistance said control values from said constraint limits, and
• means for selecting each next successive set of normalized control values in accordance with said prescribed performance measurement criteria.

A method for allocating physical resources using a linear programming model including the steps of:

• prescribing a linear programming model with an objective function and a plurality of constraints which adequately describes feasible allocations of said physical resources,
• identifying a tentative physical resource allocation which is strictly feasible,
• iteratively improving said tentative resource allocation by normalizing said tentative resource allocation with respect to said constraints and altering said tentative resource allocations in the direction specified by said objective function, and
• allocating said resources in accordance with the most improved tentative resource allocation.

A system for allocating technological resources among a plurality of user entities, each said allocation having constraints imposed thereon and quantifiable costs or quantifiable benefits associated therewith, said system including resource allocation elements disposed by a resource allocating mechanism including:

• means for representing said constraints as a multidimensional convex polytope having facets representing said constraints and having a surface representing preferred resource allocations,
• means for tentatively selecting an allocation of said resources corresponding to a point in the interior of said polytope as a beginning point,
• means for stepping from said beginning point to a succession of points in the interior of said polytope, each succeeding point representing a more optimal allocation than the preceding point, and
• means for deploying the elements of said system to accommodate the preferred resource allocation specified by a point on said surface.

A technological resource allocation system for allocating technological resources among a plurality of resource users subject to constraints on said allocations and in such a manner as to reduce the total cost of said allocations, the allocations made in said system being determined in accordance with a method comprising the following steps:

• (1) receiving information concerning availability of said technological resources, said users, said constraints, and said costs,
• (2) representing said constraints as a polytope in multidimensional space,
• (3) representing said allocation costs as a vector in said multidimensional space,
• (4) selecting an initial allocation point located in the interior of said polytope,
• (5) normalizing said polytope such that said initial allocation point is substantially at its center,
• (6) determining the direction of said cost vector projected into the null space of said constraints within said normalized polytope,
• (7) selecting a new allocation point in said normalized polytope in a direction opposite to the direction of said projected cost vector, and
• (8) repeating steps (4) through (7) for said new allocation point,
• (9) allocating said technological resources to said users in accordance with the latest one of said new allocation point.

A system comprising a plurality of resources achieving a plurality of end results and employing a recursive method for allocating said resources to achieve said end results, wherein a present resource allocation arrangement x.sup.i is replaced by an improved resource allocation arrangement x.sup.i+1 which is derived from x.sup.i by the equation x.sup.i+1 =.PHI.{X.sup.i } and which becomes the present resource allocation arrangement of the next iteration, the function .PHI. comprising:

• (1) arranging the components of said present resource allocation arrangement along the diagonal of an otherwise empty matrix D;
• (2) forming a matrix B by developing the matrix product AD and augmenting the developed product with a last row of n 1's;
• (3) developing a vector c.sub.p by obtaining the value of [I-B.sup.T (BB.sup.T)B].sup.-1 Dc where I is the identity matrix;
• (4) dividing c.sub.p by its magnitude to develop a normalized pointer c.sub.p ;
• (5) creating a transformed new estimate x.sup.i+1 of x by subtracting .alpha.c.sub.p from said current transformed estimate x.sup.i of x, where .alpha. is less than unity;
• (6) creating an untransformed new estimate of x by evaluating Dx.sup.i+1 /e.sup.T Dx.sup.i+1 where e={1,1, . . . , 1};
• and
• (7) applying said new estimate x.sup.i+1 of x to said system.

The method of allocating industrial resources among a plurality of resource users, each said allocation having physical constraints on resource use and quantifiable costs or benefits associated with each said allocation, said method comprising the steps of

• (1) receiving information concerning availability of said industrial resources, said users, said constraints, and said costs,
• (2) representing said physical constraints with a system of linear relationships together defining a multidimensional polytope having a facet representing each of said physical constraints,
• (3) selecting a tentative set of allocations of said resources represented by an interior point within said polytope as a beginning allocation point,
• (4) transforming said polytope to place said beginning allocation point substantially at the geometrical center of said transformed polytope and all said facets at substantially equal distances from said center,
• (5) moving from said beginning allocation point to another allocation point interior to said rescaled polytope but closer to the surface of said rescaled polytope,
• (6) transforming said another allocation point back to the original scale of said polytope,
• (7) repeating steps (4) through (6) until a point interior to said polytope is selected which is substantially coincident with said surface,
• (8) identifying the allocation values associated with said point substantially coincident with said surface, and
• (9) allocating said resources in accordance with the resource allocation values so identified.

A system for allocating industrial resources among a plurality of resource consumers, each resource allocation being physically constrained and having quantifiable costs associated with said allocation, said system providing allocations of said resources determined in accordance with a method comprising the steps of:

• (1) representing said physical constraints as a system of linear relationships defining a closed convex multidimensional solid,
• (2) selecting a resource allocation corresponding to a point interior to said multidimensional solid as a beginning point,
• (3) transforming said closed solid so as to place said selected beginning point substantially at the geometric center of said transformed solid and the surfaces of said solid substantially equidistant from said center,
• (4) selecting another allocation of said resources corresponding to another point interior to said rescaled closed solid but closer to said surface than said beginning point,
• (5) repeating steps (3) and (4) with the new allocations until a selected allocation substantially corresponds to a point on the surface of said solid, and
• arranging said system to allocate said resources in accordance with the final industrial resource allocation associated with said point on the surface of said solid.

A method for allocating physical resources among a plurality of resource users subject to constraints on said allocations and in such a manner as to reduce related allocation costs, said method comprising the steps of:

• (1) representing said constraints as a polytope in multidimensional space,
• (2) representing said allocation costs as a vector in said multidimensional space,
• (3) selecting an initial allocation point located in the interior of said polytope,
• (4) transforming said polytope into an equivalent space with said initial allocation point substantially at its center,
• (5) determining the direction of said cost vector in said equivalent space,
• (6) selecting a new allocation point in said equivalent space in a direction opposite to the direction of said cost vector,
• (7) transforming said new allocation point back to the original space of said polytope,
• (8) repeating steps (4) through (7) for said new allocation point,
• (9) terminating the iterative process defined in steps (4) through (8) when evaluated allocation costs fall below a preselected threshold, and
• (10) allocating said physical resources among said plurality of resource users in accordance with the latest one of said new allocation point.

A method for allocating industrial or technological resources x.sub.i (i=1, n) among a plurality of resource users subject to constraints A.sub.ij x.sub.i .ltoreq.b.sub.j and x.sub.i .gtoreq.0 (i=1, n;

• j=1, m) in such a manner as to optimize a cost function c.sub.i.sup.T .multidot.x.sub.i, said method comprising the steps of:
• (1) selecting an initial allocation x.sup.start =(x.sub.1.sup.start, x.sub.2.sup.start, . . . , x.sub.n.sup.start) meeting said constraints,
• (2) using the projective transformation ##EQU10## where
• D=diag.{x.sub.1.sup.start, x.sub.2.sup.start, . . . , x.sub.n.sup.start },
• and
• e=(1, 1, 1, . . . , 1),
• to transform said constraints into an affine space with x.sup.start substantially at its center,
• (3) determining the cost function vector c.sub.p in said affine space by the relationship
• c.sub.p ={I-B.sup.T (BB.sup.T).sup.-1 B}Dc
• where
• I is the identity matrix,
• c is the cost vector,
• D is defined above, and
• B=(AD/e.sup.T),
• (4) normalizing said cost function vector c.sub.p by the relationship ##EQU11## (5) selecting a new initial allocation b' in said affine space given by
• b'=x'.sup.start -.alpha.rc.sub.p,
• where
• r is the radius of the largest inscribed sphere in said affine space and is given by ##EQU12## and .alpha. is less than unity,
• (6) transforming said new new initial allocation point back to the original space with the transformation ##EQU13## and (7) repeating steps (2) through (6) using b instead of a.sub.o as the new initial allocation
• (8) allocating said industrial or technological resources in accordance with said new allocation b'.

A method for improving overall cost in a system having a plurality n of industrial resources operating in concert to achieve a plurality of technological end results b.sub.j, each of said resources providing a contribution to each of said end results with an attendant cost coefficient and subject to constraints characterizing said system, where vector b represents said plurality of end results, vector x represents the set of said contributions required of said plurality of resources, vector c represents the set of said cost coefficients, and matrix A represents said system constraints,

• CHARACTERIZED BY:
• selecting a set of contributions x.sup.curr satisfying said system constraints as a current estimate of x;
• arranging said current estimate x.sup.curr along the diagonal of an otherwise empty matrix D;
• forming a matrix B by developing the matrix product AD and augmenting the developed product with a last row of n 1's;
• developing a pointer vector c.sub.p by evaluating [I-B.sup.T (BB.sup.T).sup.-1 B]Dc where I is the identity matrix;
• dividing c.sub.p by its magnitude to develop a normalized pointer c.sub.p ;
• creating a transformed new estimate x.sup.1 of x by subtracting .alpha.c.sub.p from e/n, where .alpha. is less than unity,
• creating an untransformed new estimate x.sup.next of x by evaluating Dx'/e Dx' where e={1,1, . . . 1};
• and
• applying said new estimate x.sup.next of x to said system.

Method for allocating industrial or technological resources, said method comprising:

• the determination of values for controllable physical variables associated with said resources,
• the set of feasible combinations of said physical variables being a convex set and said determination to be effected so as to enhance the value of an objective function of said physical variables,
• said determination comprising a sequence of steps such that at each step tentative values for said physical variables are replaced
• said replacing based on choosing a direction in a set which is obtained by centralizing said convex set;
• and
• allocating said resources in accordance with the last step in said sequence of steps of replacing tentative values of said physical resources.

A method of optimizing the allocation of resources in a system characterized by a linear objective function, each element of which represents a specific resource allocation attributable to an individual entity of the system, and comprises a variable and a known variable coefficient, and by one or more constraint linear forms expressed in terms of one or more of the variables of the objective function, said method comprising the steps of

• (1) determining an initial value for each of the variables of the objective function such that a vector in n-dimensional space defined by the initial values resides inside a polytope defined by the constraint linear forms,
• (2) transforming the polytope including the initial vector and the constraint linear forms into a simplex S{x.vertline.x>=0, .SIGMA.x.sub.i =1} having the origin of the initial vector located substantially at its center,
• (3) projecting the transformed initial vector orthogonally onto the simplex,
• (4) determining the direction of the projection of the transformed initial vector in said simplex,
• (5) determining a new starting point for a new initial vector by moving from the center e/n of the simplex S in a direction opposite to said determined direction by a distance in said simplex equal to a multiple of the radius of the largest sphere inscribed in said simplex and centered at the origin of the transformed initial vector,
• (6) transforming said new starting point back into the polytope space,
• (7) repeating steps (2) through (6), substituting, for the initial values of the objective function variables, values defined by said transformed new starting point, until a satisfactory minimization of the objective function is obtained, and
• allocating system resources to the individual system entities according to the final values of the elements of the objective function.

A method of optimizing an allocation of resources in a system characterized by an n-dimensional objective function, each element of which represents a specific resource allocation attributable to an individual entity of the system and comprises a variable and a known variable coefficient, and by one or more constraint relationships expressed in terms of one or more of the variables of the objective function, said method comprising the steps of:

• (1) determining an initial value for each of the variables of the objective function such that an initial vector defined by the initial values resides inside a polytope defined by the constraint relationships,
• (2) transforming the polytope, including the initial vector and the constraint relationships, into a simplex S={x.vertline.x.sub.1 .gtoreq.0, .gtoreq.x.sub.i =1} in which the transformed initial vector is located substantially at the center of the simplex,
• (3) projecting the transformed vector of said objective function orthogonally onto the null space of the transformed constraint relationships,
• (4) determining the direction of the projection of the transformed objective function,
• (5) determining a new value for each of the variables of the objective function by moving from the center e/n of said simplex, a distance equal to a predefined multiple of the radius of the largest sphere contained within the simplex and centered at the origin of the transformed initial vector,
• (6) transforming said new values back into the original variables,
• (7) repeating steps (2) through (6), substituting said new values for the initial values of the objective function variables, until a satisfactory minimization of the objective function is obtained, and
• (8) allocating system resources to the individual system entities according to the final values of the elements of the objective function.