Original Research

An experimental investigation of a new multiplex method for linear programming

J. A. Snyman, M. van Rooyen
Suid-Afrikaanse Tydskrif vir Natuurwetenskap en Tegnologie | Vol 6, No 2 | a948 | DOI: https://doi.org/10.4102/satnt.v6i2.948 | © 1987 J. A. Snyman, M. van Rooyen | This work is licensed under CC Attribution 4.0
Submitted: 17 March 1987 | Published: 17 March 1987

About the author(s)

J. A. Snyman,, South Africa
M. van Rooyen,, South Africa

Full Text:

PDF (290KB)

Share this article

Bookmark and Share

Abstract

Karmarkar’s recent internal and iterative method for linear programming problems has resulted in a renewed interest in some older alternatives, other than the simplex method. Here a new multiplex and geometric method, which has some features in common with the older methods, is proposed and implemented. In this method the solution is found by following a gradient path through the interior of the feasible region and through subspaces of reduced dimension corresponding to the bounding hyper-surfaces of the feasible region. The path moves from an initial feasible point through a sequence of linear steps to a vertex of the polytope defined by the constraints. Although similar, the current method differs fundamentally from Rosen’s gradient projection method in that the successive search directions are obtained from the gradients of reduced problems of lesser dimension. These directions, when translated to the original space, do not necessarily correspond to the gradient projection directions. Once a vertex has been reached the new algorithm determines whether or not it is optimal by applying a simple perturbation procedure for which the perturbed points are generated as a by-product of the computed path to the vertex. If not optimal the algorithm proceeds by restarting from a perturbed point (on a suitable edge) with increased function value and the path is continued until the next vertex is reached. It is shown that the results of this experimental investigation of this method is promising since it has successfully been applied to a variety of test problems.

Keywords

No related keywords in the metadata.

Metrics

Total abstract views: 741
Total article views: 1071

Reader Comments

Before posting a comment, read our privacy policy.

Post a comment (login required)

Crossref Citations

No related citations found.