An Implementation of the Projective Algorithm for Linear Programming.
Abstract
An algorithm to solve linear programming problems is presented in this thesis which is based on Karmarkar's projective method. The algorithm includes a practical method to project a general linear programming problem onto a unit simplex and eliminates the a priori need to know the optimal value of the objective function. The implementation conserves sparsity. The key part of the implementation is the solution of a linear least-squares problem to find an improving direction: a direct and an iterative method are implemented to solve this problem. The direct method employs the minimum-degree heuristic to reorder the system of normal equations, and thus conserve sparsity during the following Cholesky factor of the normal equation matrix as a preconditioner for conjugate gradient iterations which are performed implicity on the preconditioned matrix. The study concludes with implementation remarks, and computational results.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1985
- Accession Number
- ADA162048
Entities
People
- Guenter W. Bretschneider
Organizations
- Naval Postgraduate School