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: UNBELIEVABLE  O(L^1.5)  WORST  CASE  COMPUTATIONAL  COMPLEXITY

ACHIEVED  BY  spdspds  ALGORITHM  FOR

LINEAR  PROGRAMMING  PROBLEM 

 

PIPR:©: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.

k.prasad.h@gmail.com  [+919481022946]  spdspds@gmail.com 

https://arxiv.org/abs/1405.6902 

https://archive.org/details/s-p-d-s-p-d-s 

https://doi.org/10.5281/zenodo.14028226 

https://hal.archives-ouvertes.fr/hal-03087745 

https://www.linkedin.com/in/keshavaprasadahalemane/ 

 

ABSTRACT

 

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. 
description: AMS MSC Mathematics Subject Classification: 90C05 
ACM CCS Computing Classification System: F.2.1, G.1.6