An implementation of the projective algorithm for linear programming
Loading...
Authors
Bretschneider, Guenter W.
Subjects
Linear Programming
Projection Method
Symmetric Matrices
Least Squares Problem
Cholesky Factorization
Projection Method
Symmetric Matrices
Least Squares Problem
Cholesky Factorization
Advisors
Wood, R. Kevin
Date of Issue
1985-09
Date
Publisher
Language
en_US
Abstract
An algorithm to solve linear programming problems is presented
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 factorization. The iterative method uses the incomplete
Cholesky factor of the normal equation matrix as a preconditioner
for conjugate gradient iterations which are performed implicitly on the
preconditioned matrix. The study concludes with implementation
remarks, and computational results.
Type
Thesis
Description
Series/Report No
Department
Operations Research (OR)
Organization
Naval Postgraduate School
Identifiers
NPS Report Number
Sponsors
Funder
Format
43 p.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.