METHODS AND APPARATUS FOR EFFICIENT RESOURCE ALLOCATION

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.