Methods and apparatus for efficient resource allocation

Details Methods and apparatus for efficient resource allocation Methods and apparatus for efficient resource allocation

1985-04-19

1988-05-10

Ruggiero, Joseph

Boots, shoes, and leggings

G06F 1520, H04Q 366, H04M 700

Patent

active

047440287

ABSTRACT:
A method and apparatus for optimizing resource allocations is disclosed which proceeds in the interior of the solution space polytope instead of on the surface (as does the simplex method), and instead of exterior to the polytope (as does the ellipsoid method). 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. 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 optimization method is sufficiently fast to be useful in real time control systems requiring more or less continual allocation optimization in a changing environment, and in allocation systems heretofore too large for practical implementation by linear programming methods.

REFERENCES:
patent: 4364115 (1982-12-01), Asai
patent: 4479176 (1984-10-01), Grimshaw
patent: 4481600 (1984-11-01), Asai
Linear Programming and Extensions, G. B. Dantzig, 1963.
Hacijan, L. G., A Polynomiar Algorithm in Linear Programming, Soviet Math. Dokl, vol. 20, #1, 1979.
Bland, R. G. et al., The Elipsoid Method: A Survey, vol. 29, No. 6, Operations Research 1981.
A New Polynomial-Time Algorithm Ser Linear Programming, N. Karmarkar, ACM 1984.
Design and Optimization of Networks with Dynamic Routing, G. R. Ash et al., The Bell System Tech. Journal, vol. 60, No. 8, 10/1981, p. 1787.
G. R. Ash et al., Servicing and Real-Time Control of Networks with Dynamic Routing, The Bell System Tech. Journal, vol. 60, No. 8, 10/1981, p. 1821.
"The Ellipsoid Method and its Consequences in Combinatorial Optimization," Combinatorica 1(2), Grotschel et al., 1981, pp. 169-197.

Affiliated with

Also associated with

Rating

Methods and apparatus for efficient resource allocation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and apparatus for efficient resource allocation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for efficient resource allocation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1325268