Methods and apparatus for efficient resource allocation

• US 4,744,026 A
• Filed: 04/11/1986
• Issued: 05/10/1988
• Est. Priority Date: 04/11/1986
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Inventors: Vanderbei, Robert J.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US06/851,120
• Time in Patent Office: 760 Days
• Field of Search: 364/402, 379/113, 379/221, 340/827
• US Class Current: 705/7.22
• 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/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/06312 Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling
• 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. At least one allocation variable is assumed to be unconstrained in value. Each successive approximation of the solution point, and the polytope, are normalized such that the solution 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 the phase of one problem of obtaining a starting point, and to the dual problem, where the free variable assumption produces unexpected computational advantages.

Claims

1. A method for allocating available industrial facilities among the users of said facilities so as to reduce 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 the Karmarkar algorithm so as to reduce said total costs at each said reassignment,

each said reassignment being determined by normalizing the previous assignment with respect to constraints on said allocations,

during each said reassignment, adjusting the direction of changes in said previous assignments under the assumption that at least one of said constraints increases in value without limit,

terminating said iterative reassigning steps when said costs are reduced to a preselected threshold to form a final reduced cost assignment, and

allocating said facilities in accordance with the final reduced cost assignment.

2. The allocation method according to claim 1 wherein said final step of allocating is preceded by the steps of

utilizing said facility assignments identified as final reduced cost assignment in claim 1 as the initial assignment of facilities in a further allocation of said facilities to reduce a different cost criteria, and

repeating the steps of claim 1 using said different cost criteria.

3. The allocation method according to claim 1 wherein said reassigning step further includes the step of

reassigning, at each iteration, both the cost minimizing (primal) allocations and the equivalent maximizing (dual) allocations of said facilities.

4. 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,

said iterative selecting means further comprising means for including the effect on successive selections of assuming that at least one of said resources increases in value without limit, and

means for 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 improved 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 under the assumption of at least one unconstrained variable control signal, and selecting each next tentative control signal set along the steepest gradient of a normalized version of said optimizing criteria.

6. The improvement in linear programming methods for optimally allocating resources among a plurality of users which includes the steps of:

introducing at least one free variable into said linear programming model,

iterating on only strictly feasible allocations, and

normalizing each strictly feasible allocation with respect to the constraints on said allocations.

7. A linear programming controller for use with a general purpose digital computer, said controller comprising:

a computer program storage medium having a computer program stored thereon for execution by said digital computer, said program comprising

means for processing a plurality of linear relationships defining a multidimensional convex polytope representing the set of feasible solutions to said plurality of linear relationships, and

means, including a function to be optimized, for identifying that point on the boundary of said polytope representing the optimum solution to said plurality of linear relationships by the Karmarkar algorithm modified for at least one free variable.

8. A method for allocating industrial or technological resources x_i (i=1, n) among a plurality of physical resource users subject to constraints A_ij x_i ≦

b_j and x_i ≧

0 (i=1, n;

j=1, m) in such a manner as to optimize a cost function c_if1 ·

x_i, said method comprising the steps of;

(a) receiving information identifying said resources, said resource users, and said constraints;

(b) partitioning said resources into constrained and unconstrained subsets x and y, respectively,

(c) selecting an initial allocation x_s and y_s meeting said constraints,

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

space="preserve" listing-type="equation">z.sub.F =(F.sup.T BF).sup.-1 (c.sub.F -F.sup.T BAD.sub.x.sup.2 c.sub.A)

where

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

and

D_x =the diagonal matrix of the current allocations of said constrained resources,

(e) rescaling the space of said constraints with said diagonal matrix D_x in accordance with the formula

space="preserve" listing-type="equation">w=BAD.sub.x.sup.2 c.sub.A +BFz.sub.F

(f) determining the direction z_A of the constrained partition of next iteration of said iterative procedure in accordance with the formulae

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

(g) determining the complementary slackness coefficient of said current iteration from the formula

space="preserve" listing-type="equation">γ

=max[(z.sub.A).sub.i /(x.sub.i -l.sub.i)V-(z.sub.A).sub.i /(u.sub.i -x.sub.i)],

(h) determining the dual feasibility coefficient δ

of said current iteration from the formula

space="preserve" listing-type="equation">δ

=-min[(z.sub.A).sub.i /(x.sub.i -l.sub.i).sup.2 Λ

-(z.sub.A).sub.i /(u.sub.i -x.sub.i).sup.2)],

(i) testing said current iteration from the equality

space="preserve" listing-type="equation">γ

+Mδ

<

(ε

/n)(|c.sub.A ·

x+c.sub.F ·

y|+1),

where

space="preserve" listing-type="equation">M=max(x.sub.i -l.sub.i)Λ

(u.sub.i -x.sub.i),

and

ε

=an arbitrarily small error measure,

(j) if the test of step (i) is not satisfied, returning to step (d) with the new allocations

space="preserve" listing-type="equation">x←

x-α

z.sub.A /γ

,

and

space="preserve" listing-type="equation">y←

y-α

z.sub.F /γ

,

where

space="preserve" listing-type="equation">0≦

α

≦

1,

(k) if the test of step (i) is satisfied, allocating said resources in accordance with said current allocation iteration values.

9. A method for utilizing the Karmarkar algorithm for allocating industrial or technological resources x_i (i=1, n) among a plurality of resource users subject to constraints Σ

A_ij x_j =b_i and x_i ≧

0 (i=1, n;

j=1, m) in such a manner as to optimize a cost function c_i ·

x_i, said method comprising the steps of;

(a) receiving information identifying said resources, said resource users, and said constraints;

(b) formulating the dual model

Maximize;

b·

w

Subject To;

A^T w≦

c, w is free,

(c) partitioning the maximizing portion of step (b) as follows;

##EQU9## where v is a subset of unconstrained variables, and I is the identity matrix,

(d) determining the centralized value of the current iteration, and the direction of the next iteration, of an iterative procedure for approximating said optimal cost in accordance with the formulae

space="preserve" listing-type="equation">z.sub.w =-(AD.sub.v.sup.-2 A.sup.T).sup.-1 b,

space="preserve" listing-type="equation">w=-D.sub.v.sup.-2 A.sup.T z.sub.w, and

space="preserve" listing-type="equation">z.sub.v =+D.sub.v.sup.2 x=-A.sup.T z.sub.w

where

D_x =the diagonal matrix of the current allocations of said constrained resources,

(e) determining the complementary slackness coefficient of said current iteration from the formula

space="preserve" listing-type="equation">γ

=max[(z.sub.v).sub.i /v.sub.i ],

(f) determining the dual feasibility coefficient δ

of said current iteration from the formula

space="preserve" listing-type="equation">δ

=-min[(z.sub.v).sub.i /v.sub.i.sup.2 ],

(g) testing said current iteration with the inequality

space="preserve" listing-type="equation">γ

+Mδ

<

(ε

/n)(|b·

w|+1)

where

space="preserve" listing-type="equation">M=max(v.sub.i),

and

ε

=an arbitrarily small error measure,

(h) if the test of step (g) is not satisfied, set

space="preserve" listing-type="equation">w←

w-α

z.sub.w /γ

and

space="preserve" listing-type="equation">v←

v-α

z.sub.v /γ

,

and returning to step (c),

(i) if the test of step (g) is satisfied, allocating said resources in accordance with said current allocation iteration values.

10. A method of allocating resources in accordance with the Karmarkar algorithm where physical resources, users of said resources and the constraints on the allocation of said resources to said users are represented by a polytope, where feasible allocations are points within said polytope, and where a preferred allocation of said resources to said users is carried out

iteratively by stepping from the interior of a rescaled constraint polytope toward the optimum-valued vertex of said rescaled polytope, comprising the steps of:

terminating said iterative stepping when

space="preserve" listing-type="equation">γ

+Mδ

<

ε

/n

where

γ

=max(z_i /x_i);

δ

=-min(z_i /x_i²);

M=max(x_i);

ε

=an arbitrary error metric;

n=the number of allocation variables;

x_i =the ith component of the current allocation of resources;

z_i =the ith component of the direction of the next step; and

allocating said resources in accordance with the values of said current allocation when said terminating step is taken.

11. A method of stopping iterations of the Karmarkar algorithm at substantially the optimum allocation values comprising the steps of

determining the complementary slackness coefficient γ

in accordance with the formula

space="preserve" listing-type="equation">γ

=max(z.sub.i /x.sub.i);

where

x_i =the ith component of the current allocation value, and

z_i =the ith component of the inverse gradient of the objective function at allocation value x;

determining the dual feasibility coefficient δ

in accordance with the formula

space="preserve" listing-type="equation">δ

=-min(z.sub.i /x.sub.i.sup.2);

and stopping said iterations when

space="preserve" listing-type="equation">γ

+Mδ

<

ε

/n

where M is the value of the maximum component of x, ε

is an arbitrarily small error measure, and n is the number of components of x.

12. Apparatus for allocating resources in an optimal manner among users of said resources comprising

means for receiving information concerning said users, concerning the availability of said resources and concerning constraints on the allocation of said resources,

means, utilizing the Karmarkar algorithm, for iteratively approximating an optimum allocation of said resources among said users,

means for stopping said iteratively approximating means when a function of the complementary slackness coefficient and the dual feasibility coefficient is less than a preselected error value, and

means for allocating said resources in accordance with the last option allocating of said resources approximated by said iterative approximating means.

13. The apparatus according to claim 12 wherein

said complementary slackness coefficient is the value of the maximum ratio of the value of the direction component of the next iteration of said iterative approximating means and the corresponding allocation component.

14. The apparatus according to claim 12 wherein

said dual feasibility coefficient is the negative of the value of the maximum ratio of the direction component of the next iteration of said iterative approximating means and the square of the corresponding allocation component.

15. The improvement in linear programming methods for optimally allocating resources among a plurality of users which includes the steps of:

introducing at least one free variable into the said linear programming model employed in said linear programming methods,

iterating on only strictly feasible allocations, and

normalizing each strictly feasible allocation with respect to the constraints on said allocations.