Methods and apparatus for efficient resource allocation

• US 4,924,386 A
• Filed: 07/13/1987
• Issued: 05/08/1990
• Est. Priority Date: 07/13/1987
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Inventors: Meketon, Marc S., Freedman, Barry A., Vanderbei, Robert J.
• Primary Examiner(s): MacDonald, Allen
• Application Number:
  US07/072,943
• Time in Patent Office: 1,030 Days
• Field of Search: 364/402, 379/113, 379/221, 340/825.28
• US Class Current: 705/7.37
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/06375 Prediction of business process outcome or impact based on a proposed change

Abstract

A method and apparatus for optimizing resource allocations is disclosed which utilizes the Karmarkar algorithm to proceed in the interior of the solution space polytope. The values of the allocation variables are limited by upper and lower bounds, either individually or collectively with the same common bound. Each successive approximation of the solution point, and the polytope, are normalized such that the solution point is at the center of the normalized polytope using a diagonal matrix of the current solution point. The objective function is then projected into the normalized space and the next step is taken in the interior of the polytope, in the direction of steepest-descent of the objective function gradient and of such a magnitude as to remain within the interior of the polytope. The process is repeated until the optimum solution is closely approximated.

The resulting algorithm steps are advantageously applied to linear programming problems which involve allocations which are simultaneously dependent on a large number of constraints, problems which might otherwise involve excessive amounts of computation time.

Claims

1. A method for allocating available industrial facilities among the users of said facilities so as to minimize the total cost of providing said facilities, said method comprising the steps of:

tentatively and iteratively reassigning said available facilities to said users in accordance with a deterministic process so as to reduce said total costs at each said reassignment with each of the reassignments in said tentatively and iteratively reassigning being characterized by a total cost that is lower than the cost of preceding reassignment,

terminating said iterative reassigning steps when said costs are minimized, and

physically allocating said facilities in accordance with the minimum cost assignment

wherein said deterministic process is the Karmarkar algorithm where each reassignment is developed by normalizing the previous reassignment with respect to constraints on said allocations, and

the direction of changes in said previous reassignment to develop said each reassignment is made under the constraint that at least one of said assignments has a finite limit.

2. The allocation method according to claim 1 wherein all of said reassignments have the same finite limit.

3. The allocation method according to claim 1 wherein each of said reassignments has its own respectively different limit.

4. An optimized resource allocation system comprising:

a first plurality of physical resources available for use,

a second plurality of resource users keyblue to said physical resources so as to minimize 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,

said iterative selecting means further comprising means for including the effect on successive selections of limiting the value of at least one of said allocations to a preselected finite value, and

means coupled to said resource users and to said iteratively selecting means for physically allocating said physical resources in accordance with the final one of said tentative assignments.

5. 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 in accordance with the Karmarkar algorithm,

said controller including means for iteratively identifying successive tentative strictly feasible control signal sets including means for limiting at least one of said control signals to a preselected value, and selecting each next tentative control signal set along the steepest gradient of a normalized version of said optimizing criteria.

6. In a system that includes industrial or technological resources to be allocated among a plurality of resource users, and a controller coupled to said users and to said resources, where the controller carries out a method for allocating said resources x_i (i=1,n) among said plurality of resource users subject to constraints ##EQU21## and x_j ≧

0(i=1,m;

j=1,n) in such a manner as to optimize a cost function Σ

c_i ·

X_i, said method comprising the steps of;

(a) partitioning said constraints into limit-dependent and limitindependent subsets, respectively,

(b) selecting an initial allocation x meeting said constraints,

(c) rescaling the space of said constraints in accordance with the formula

space="preserve" listing-type="equation">w=(AD.sub.x.sup.2 A.sup.T).sup.-1 AD.sub.x.sup.2 c

where D_x is the diagonal matrix of the current allocation values of x,

(d) determining the direction of the next iteration of an iterative procedure for approximating said optimal cost in accordance with the formula

space="preserve" listing-type="equation">z=D.sub.x.sup.2 (c-A.sup.T w),

(e) determining the complementary slackness coefficient "γ

" of said current iteration from the formula ##EQU22## wherein "V" indicates the selection of the largest maximum of the two sets,

(f) determining the dual feasibility coefficient "δ

" of said current iteration from the formula ##EQU23## where "Λ

" indicates the selection of the smallest minimum of the two sets,

(g) testing said current iteration with the equality ##EQU24## (h) if the test of step (g) is not satisfied, returning to step (c) with the new allocations ##EQU25## (i) if the test of step (g) is satisfied, physically allocating said resources in accordance with said current allocation iteration values.