Methods and apparatus for efficient resource allocation

• US 4,885,686 A
• Filed: 01/12/1987
• Issued: 12/05/1989
• Est. Priority Date: 01/12/1987
• Status: Expired due to Term

• Current Assignee: American Telephone & Telegraph Company (AT&T, Inc.), Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: American Telephone & Telegraph Company (AT&T, Inc.)
• Inventors: Vanderbei, Robert J.
• Primary Examiner(s): MACDONALD, ALLEN R
• Application Number:
  US07/002,371
• Time in Patent Office: 1,058 Days
• Field of Search: 364/402, 379/113, 379/221, 340/825.28
• US Class Current: 700/99
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

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 constraints on the allocation variables (the surfaces of the polytope) are partitioned into sparse and non-sparse partitions to permit applying a perturbation formula permitting rapid inversion of the resulting perturbed matrix products. 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, also partitioned into sparse and non-sparse portions. 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 other wise involve excessive amounts of computation time.

Claims

1. A method for allocating available industrial facilities among users of said facilities, subject to constraints on said allocations, to minimize the total cost of providing said facilities, said method starting with a initial tentative facilities assignment and comprising the steps of:

tentatively assigning said available facilities to said users in accordance with a specified deterministic process to form a tentative facilities assignment characterized by a total cost that is lower than the cost of preceding tentative facilities assignments;

repeating said step of tentatively assigning when said total cost fails to meet a preselected criterion; and

allocating said facilities in accordance with the last of said tentative facilities assignments when said total cost meets said preselected criterion;

wherein

said allocations to said users and said available industrial facilities form linear constraint relationships; and

said preselected deterministic process is a modified Karmarkar algorithm wherein

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

during each said assignment, forming a tentative facilities assignment by (a) separating said constraint relationships into a sum of a first subset of constraint relationships and a second subset of constraint relationships, where said first subset of constraint relationships corresponds to those users that affect a number of said constraints in excess of a preselected proportion of said constraints, and said second subset of constraint relationships corresponds to the remaining users, and (b) separately operating on said subsets of constraint relationships in the course of said assignment.

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

utilizing the last of said tentative facilities assignment in claim 1 as the initial assignment of facilities in a further allocation of said facilities to minimize 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 assigning step further includes the step of

assigning 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

a controller for assigning said resource users to said physical resources so as to minimize the cost of providing said resources, said controller including

first means for iteratively and tentatively selecting feasible ones of said assignments in accordance with a preselected process until preselected stopping criteria are met,

second means for allocating said physical resources in accordance with a final one of said tentative assignment; and

third means for including the effect on successive selections of partitioning the users into a set of users that employ a number of said physical resources in excess of a preselected proportion of said physical resources, and a set of users that corresponds to the remaining ones of said users;

wherein

said first means of said controller constrains each of said feasible assignments to be represented within the interior of a normalized multidimensional convex feasible solution space.

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 variable 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 optimized control signal sets to said process control devices in accordance with the Karmarkar algorithm,

said controller including means for identifying successive tentative strictly feasible control signal sets including means for separating sparsely and non-sparsely constrained ones of said variable control signals, and means for selecting each of said successive tentative control signal set along the steepest gradient of a normalized version of said optimizing criteria.

6. The system according to claim 5 wherein said controlled process is a process of assigning transmission facilities in a telecommunications network.

7. The system according to claim 5 wherein said controlled process is a process of manufacturing a number of products.

8. The system according to claim 5 wherein said controlled process is a process of controlling the the deployment of industrial equipment.

9. The system according to claim 5 wherein said controlled process is an inventory control process.

10. A method for allocating industrial or technological resources, x_j j-l,n, among a plurality of resource users subject to constraints ##EQU4## to optimize a cost function ##EQU5## said method comprising the steps of:

tentaively allocating said available resources to said resource users in accordance with a specified deterministic process to form a tentative resource allocation characterized by a total cost that is lower than the cost of preceding tentative resource allocations;

repeating said step of tentatively allocating when said total cost fails to meet a preselected criterion; and

allocating said resource in accordance with the last of said tentative resource allocations when said total cost meets said preselected criterion;

wherein said step of tentatively allocating includes the steps;

(a) partitioning said constraints into sparse and non-sparse subsets S and N, respectively, of a constraint matrix, A=[a_ij ],

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

(c) determining a dual variable w in accordance with the formula

space="preserve" listing-type="equation">w={(SD.sub.S.sup.2 S.sup.T).sup.-1 -(SD.sub.S.sup.2 S.sup.T).sup.-1 N(D.sub.N.sup.-2

space="preserve" listing-type="equation"> +N.sup.T (SD.sub.S.sup.2 S.sup.T).sup.- N).sup.-1 N.sup.T (SD.sub.S.sup.2 S.sup.T).sup.-1 }AD.sub.x.sup.2 c,

where S is the submatrix of A corresponding to sparse columns of A, where a column j_o is sparse when the number of nonzero elements in column j_o is less than a preselected proportion of the total number of elements a_ij.sbsb.o for i=1, 2, . . . , m, N is the submatrix of A corresponding to the non-sparse columns, D_x is a diagonal matrix containing the elements of the current allocation vector x D_S is a diagonal matrix containing those elements of the current allocation vector x that correspond to the sparse columns, and D_N is a diagonal matrix containing those elements of the current allocation vector x that correspond to the non-sparse columns,

(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),

where D_x is the diagonal matrix of the current allocation values given by ##EQU6## (e) determining a complementary slackness coefficient γ

of said current iteration from the formula

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

=max.sub.j z.sub.j /x.sub.j, and

(f) determining a dual feasibility coefficient δ

of said current iteration from the formula

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

=-min.sub.j z.sub.j /x.sub.j.sup.2,

wherein said step of returning to said step of tentatively allocating allocating includes the steps;

(g) testing said current iteration against the inequality

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

+Mδ

<

(ε

/n)(|c·

x|+1),

where

space="preserve" listing-type="equation">M=max.sub.j x.sub.j

and ε

is an arbitrary small error measure,

(h) if the test of step (g) is not satisfied, returning to step (c) with the new allocations

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

x-α

z/γ

,

where

α

is an arbitrary real number strictly between zero and one, and

wherein said step of allocating allocates said resources in accordance with said current allocation when the test of step (g) is satisfied.

11. A method for allocating available industrial facilities, b, among users of said facilities, where the allocations, x≧

0, to said users and said available industrial facilities form linear constraint relationships, Ax=b, and said allocations are selected so as to minimize the total cost, c·

x, of providing said facilities, said method comprising the step of;

tentatively and iteratively assigning said available facilities to said users in accordance with the Karkmarkar algorithm so as to reduce said total costs at each said assignment,

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

during each said assignment, adjusting the previous assignments by grouping said set of constraint relationships Ax=b into a sum of a first subset of constraint relationships and a second subset of constraint relationships, N+S, where A=[NS], where said first subset of constraint relationships, N, corresponds to those users that affect a number of said constraints in excess of a preselected proportion of said constraints, and said second subset of constraint relationships, S, corresponds to the remaining users, and operating on said subsets of constraint relationships individually in the course of said assignment,

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

allocating said facilities in accordance with the minimum cost assignment after the last one of said steps of tentatively and iteratively assigning.