9308953 Prabhu The research will investigate a new approach to Linear Programming (LP). The approach exploits fundamental results from Convex Polytope Theory and Polarity Theory that have not been applied to LP computation previously. Preliminary studies suggest that the approach has prospects of yielding an efficient algorithm that could be faster than the current LP algorithms. The work describes two methods for devising an efficient LP algorithm based on the suggested approach: Gale Transform Method and Simplicial Refinement Method. The methods apply classic results on the combinatorial and metric structure of polytopes to make computation efficient. Computational experiments on the methods will be undertaken in parallel with theoretical investigations in order to ensure that the resulting algorithm will be theoretically efficient. Enormous theoretical and computational research effort has been expended in the past on attempts to convert the edge-following Simplex method into a worst-case polynomial-time algorithm . The Generalized Simple scheme can be significant, in that it proffers a fresh approach to the quest for worst-case polynomial-time Simplex algorithms. If these goals are achieved, the results will have significant impact in solving real world problems.

Agency
National Science Foundation (NSF)
Institute
Division of Civil, Mechanical, and Manufacturing Innovation (CMMI)
Application #
9308953
Program Officer
Lawrence M. Seiford
Project Start
Project End
Budget Start
1993-10-01
Budget End
1997-03-31
Support Year
Fiscal Year
1993
Total Cost
$89,995
Indirect Cost
Name
Purdue Research Foundation
Department
Type
DUNS #
City
West Lafayette
State
IN
Country
United States
Zip Code
47907