Unbelievable $O(L^{1.5})$ worst case computational complexity achieved by $spdspds$ algorithm for linear programming problem
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2014
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910224026173440 |
|---|---|
| author | Halemane, Keshava Prasad |
| author_facet | Halemane, Keshava Prasad |
| contents | The Symmetric Primal-Dual Symplex Pivot Decision Strategy (spdspds) is a novel iterative algorithm to solve linear programming problems. A symplex pivoting operation is simply an exchange between a basic variable and a non-basic 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 is the problem-size expressed in terms of the size(length) of the input data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1405_6902 |
| institution | arXiv |
| publishDate | 2014 |
| record_format | arxiv |
| spellingShingle | Unbelievable $O(L^{1.5})$ worst case computational complexity achieved by $spdspds$ algorithm for linear programming problem Halemane, Keshava Prasad Optimization and Control 90C05 F.2.1; G.1.6 The Symmetric Primal-Dual Symplex Pivot Decision Strategy (spdspds) is a novel iterative algorithm to solve linear programming problems. A symplex pivoting operation is simply an exchange between a basic variable and a non-basic 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 is the problem-size expressed in terms of the size(length) of the input data. |
| title | Unbelievable $O(L^{1.5})$ worst case computational complexity achieved by $spdspds$ algorithm for linear programming problem |
| topic | Optimization and Control 90C05 F.2.1; G.1.6 |
| url | https://arxiv.org/abs/1405.6902 |