Robert J Vanderbei

US Patent:

49243861, May 8, 1990

Filed:

Jul 13, 1987

Appl. No.:

7/072943

Inventors:

Barry A. Freedman - Lincroft NJ
Marc S. Meketon - Middletown NJ
Robert J. Vanderbei - Morganville NJ

Assignee:

American Telephone and Telegraph Company - New York NY

International Classification:

G06F 1520

US Classification:

364402

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.

US Patent:

47440260, May 10, 1988

Filed:

Apr 11, 1986

Appl. No.:

6/851120

Inventors:

Robert J. Vanderbei - Red Bank NJ

Assignee:

American Telephone and Telegraph Company, AT&T Bell Laboratories - Murray Hill NJ

International Classification:

G06F 1520
H04Q 366
H04M 700

US Classification:

364402

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.

US Patent:

56591756, Aug 19, 1997

Filed:

Dec 21, 1995

Appl. No.:

8/576607

Inventors:

Lawrence Allan Shepp - Piscataway NJ
Peter C. Fishburn - Madison NJ
Peter Schwander - Zurich, CH
Robert Joseph Vanderbei - Belle Mead NJ

Assignee:

Lucent Technologies Inc. - Murray Hill NJ

International Classification:

H01J 3726
G01N 2304

US Classification:

250311

Abstract:

A type of tomography is described, wherein occupancy of lattice sites in a microscopic sample of crystalline material is predicted. An electron beam is projected through the sample, at a specific angle, causing discernible spots in a detector, such as photographic film. Each spot corresponds to a row of atoms. The intensity of each spot indicates the number of atoms in the row, and the number is called a "line count. " Projecting the electron beam at specific additional angles produces additional line counts. From all the line counts, a set of equations is derived. Each variable in the equations corresponds to a lattice site in the material. A solution to the equations is found by linear programming techniques, thus assigning a value to each variable. Each value indicates the probability of occupancy of a respective lattice site.

US Patent:

48856860, Dec 5, 1989

Filed:

Jan 12, 1987

Appl. No.:

7/002371

Inventors:

Robert J. Vanderbei - Red Bank NJ

Assignee:

American Telephone and Telegraph AT&T Bell Laboratories - Murray Hill NJ

International Classification:

G06F 1520
H04Q 366
H04M 700

US Classification:

364402

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.