6spdspds9X20201025
KESHAVA PRASAD HALEMANEUNBELIEVABLE O(L1.5) WORST
CASE COMPUTATIONAL COMPLEXITY
ACHIEVED BY spdspds ALGORITHM
FOR
LINEAR PROGRAMMING PROBLEM
Dr.(Prof.) Keshava Prasad Halemane,
Professor - retired from
Department of Mathematical
And Computational Sciences
National Institute of
Technology Karnataka, Surathkal
Srinivasnagar, Mangalore –
575025, India.
[email protected] [+919481022946]
https://www.linkedin.com/in/keshavaprasadahalemane/
https://archive.org/details/@k_prasad_h
ABSTRACT
The
Symmetric Primal-Dual Symplex Pivot Decision Strategy (spdspds)
is a novel iterative algorithm to solve linear programming problems. Here, a symplex pivoting operation is
considered simply as an exchange between a basic (dependent) variable
and a non-basic (independent) variable, in the Tucker’s 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, which
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. At each iteration the
selection of the symplex pivot element is governed by the anticipated decrease
in the infeasibility index - seeking the best possible 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. Significant enhancement in
computational efficiency can also be achieved by the utilization of the
proposed concept of binding constraints.
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. The worst case computational complexity of spdspds
is shown to be O(L1.5).
Keywords:
optimization, linear programming,
algorithm, symmetric primal dual symplex,
spdspds, performance challenge, computational complexity, simplex, symplex
AMS
MSC Mathematics Subject Classification: 90C05
ACM
CCS Computing Classification System: F.2.1, G.1.6