UNBELIEVABLE O(L^1.5) WORST CASE COMPUTATIONAL COMPLEXITY ACHIEVED BY spdspds ALGORITHM FOR LINEAR PROGRAMMING PROBLEM
Creators: name: HALEMANE, KESHAVA PRASAD
Publisher: name: Zenodo
Year: 1996
Subjects: optimization, linear programming, algorithm, simplex, symplex, symmetric primal dual symplex, spdspds, computational complexity

description: <strong>UNBELIEVABLE <em>O</em>(<em>L</em><sup>1.5</sup>) WORST CASE COMPUTATIONAL COMPLEXITY </strong> <strong>ACHIEVED BY <em>spdspds</em> ALGORITHM FOR </strong> <strong>LINEAR PROGRAMMING PROBLEM </strong> ©Dr.(Prof.) Keshava Prasad Halemane, Professor - retired from Department of Mathematical And Computational Sciences National Institute of Technology Karnataka, Surathkal Srinivasnagar, Mangaluru - 575025, India. Residence: 8-129/12 SASHESHA, Sowjanya Road, Naigara Hills, Bikarnakatte, Kulshekar Post, Mangaluru - 575005. Karnataka State, India. <em>k.prasad.h@gmail.com</em> [+91<em>9481022946</em>] https://arxiv.org/abs/1405.6902 https://archive.org/details/s-p-d-s-p-d-s https://doi.org/10.5281/zenodo.4553754 https://hal.archives-ouvertes.fr/hal-03087745 https://www.linkedin.com/in/keshavaprasadahalemane/ <strong>ABSTRACT </strong> The Symmetric Primal-Dual <em>Sym</em>plex Pivot Decision Strategy (<em>spdspds</em>) is a novel iterative algorithm to solve linear programming problems. Here, a symplex pivoting operation is considered simply as an <em>exchange</em> between a basic (dependent) variable and a non-basic (independent) variable, in the Tucker’s <em>Compact Symmetric Tableau</em> (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 <em>classical simplex pivoting</em> operation of Dantzig may be considered as a restricted special case. The <em>infeasibility index</em> 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 <em>measure of goodness</em> as a <em>global effectiveness measure</em> of a pivot selection is defined/determined as/by the <em>decrease in the infeasibility index</em> associated with such a pivot selection. At each iteration the selection of the symplex pivot element is governed by the anticipated <em>decrease in the infeasibility index</em> - seeking the best possible <em>decrease in the infeasibility index</em> - from among a wide range of candidate choices with non-zero values - limited only by considerations of <em>potential numerical instability</em>. The algorithm terminates when further reduction in the infeasibility index is not possible; then the tableau is checked for the <em>terminal tableau type</em> to facilitate the <em>problem classification</em> - a termination with an <em>infeasibility index</em> of <em>zero</em> indicates optimum solution. Even in the absence of an optimum solution, the versatility of the <em>spdspds</em> algorithm allows one to explore/determine the most suitable alternative solutions in a given context, including a comprehensive parametric analysis, etc. The worst case computational complexity of <em>spdspds</em> is shown to be <em>O</em>(<em>L</em><sup>1.5</sup>).
description: AMS MSC Mathematics Subject Classification: 90C05 ACM CCS Computing Classification System: F.2.1, G.1.6