Authors: Keshava Prasad Halemane
The Symmetric Primal-Dual Symplex Pivot Decision Strategy (spdspds) is a novel iterative algorithm to solve linear programming problems. A symplex pivoting operation is considered simply as an exchange between a basic (dependent) variable and a non-basic (independent) variable, in the Goldman-Tucker Compact-Symmetric-Tableau (CST) which is a unique symmetric representation common to both the primal as well as the dual of a linear programming problem in its standard canonical form. From this viewpoint, the classical simplex pivoting operation of Dantzig may be considered as a restricted special case. The infeasibility index associated with a symplex tableau is defined as the sum of the number of primal variables and the number of dual variables that are infeasible. A measure of goodness as a global effectiveness measure of a pivot selection is defined/determined as/by the decrease in the infeasibility index associated with such a pivot selection. The selection of the symplex pivot element is made by seeking the best possible anticipated decrease in the infeasibility index from among a wide range of candidate choices with non-zero values - limited only by considerations of potential numerical instability. After passing through a non-repeating sequence of CST tableaus, the algorithm terminates when further reduction in the infeasibility index is not possible; then the tableau is checked for the terminal tableau type to facilitate the problem classification - a termination with an infeasibility index of zero indicates optimum solution. Even in the absence of an optimum solution, the versatility of the spdspds algorithm allows one to explore/determine the most suitable alternative solutions, including possibly a comprehensive parametric analysis, etc. The worst-case computational complexity of the spdspds algorithm is shown to be O(L^1.5) where L refers to the problem-size expressed in terms of the size(length) of the input data.
Comments: 25 Pages.
Download: PDF
[v1] 2021-02-22 20:57:42
[v2] 2025-05-31 20:56:37
[v3] 2025-07-02 09:07:36
Unique-IP document downloads: 462 times
Vixra.org is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. Vixra.org will not be responsible for any consequences of actions that result from any form of use of any documents on this website.
Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.