Methods and apparatus for efficient resource allocation

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

1986-04-11

1988-05-10

Ruggiero, Joseph F.

Boots, shoes, and leggings

379113, 379221, 340827, G06F 1520, H04Q 366, H04M 700

Patent

active

047440260

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.

REFERENCES:
patent: 3591724 (1971-07-01), Yaku et al.
patent: 4284852 (1981-08-01), Szybicki et al.
patent: 4345116 (1982-08-01), Ash et al.
patent: 4669113 (1984-05-01), Ash et al.
patent: 4704724 (1987-11-01), Krishnan et al.
Introduction to Operations Research, F. Hillier and G. Lieberman, 1980, pp. 91-109.
Technical Report No. 648, "An Extension of Karmarkar's Algorithm for Linear Programming Using Dual Variables", M. J. Todd et al., Cornell University, Jan. 1985.
"Efficient Implementation of a Class of Preconditioned Conjugate Gradient Methods", Siam J. Sci Stat Comput., vol. 2, No. 1, S. C. Eisenstat, Mar. 1981.
"Some Computational Experience and a Modification of the Karmarkar Algorithm", ISME Working Paper 85-105, T. M. Cavalier et al., The Pennsylvania State University.
"A Variation on Karmarkar's Algorithm for Solving Linear Programming Problems", Earl R. Barnes, IBM T. J. Watson Research Center.
"On Projected Newton Barrier Methods for Linear Programming and an Equivalence to Karmarkar's Projective Method", Gill et al., Stanford University, Technical Report Sol. 85-11, Jul. 1985.

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-1325258