US4924386A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for efficient resource allocation
Assignee: AT&T Inc
•
Filing: 1987-07-13
•
Granted: 1990-05-08
•
Expires: 2007-07-13
Abstract
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.
Inventors
- 👤 Barry A. Freedman
- 👤 Marc S. Meketon
- 👤 Robert J. Vanderbei
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 19:52
CPC Classifications
G; G06; G06Q; G06Q10/00; G06Q10/06; G06Q10/063; G06Q10/0637; G06Q10/06375
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
160 words
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.
Claim 2
Independent Claim
160 words
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.
Claim 3
Dependent Claim
17 words
The allocation method according to claim 1 wherein all of said reassignments have the same finite limit.
Claim 4
Dependent Claim
18 words
The allocation method according to claim 1 wherein each of said reassignments has its own respectively different limit.
Claim 5
Dependent Claim
133 words
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.
Claim 6
Dependent Claim
133 words
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.
Claim 7
Independent Claim
140 words
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.
Claim 8
Independent Claim
140 words
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.
Claim 9
Dependent Claim
257 words
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 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 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.
Claim 10
Dependent Claim
257 words
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 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 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.
References Cited (Backward Citations)
US4345116A
Cited
US4744028A
Cited
US4669113A
Cited
US4704724A
Cited
US4744026A
Cited
US4744027A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-05-07 | 1993-11-06 | 1994-05-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-05-07 | 1997-11-06 | 1998-05-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-05-07 | 2001-11-06 | 2002-05-08 | $7700.00 | Window Closed / Lapsed |