| Title: | Badr, E., Paparrizos, K., Samaras, N., Sifaleras, A. (2005) . On the basis inverse of the exterior point simplex algorithm. In Proc. of the 17th National Conference of Hellenic Operational Research Society (HELORS), 16-18, Rio, Greece, pp. 677-687, 2005. |
| Authors: | E. M. Badr , K. Paparrizos, N. Samaras and A. Sifaleras |
| Year: | 2005 |
| Keywords: | Not Available |
| Journal: | Not Available |
| Volume: | Not Available |
| Issue: | Not Available |
| Pages: | Not Available |
| Publisher: | Not Available |
| Local/International: | Local |
| Paper Link: | |
| Full paper | Not Available |
| Supplementary materials | Not Available |
| Abstract: |
The main feature of simplex type algorithms is that they can be interpreted as a method following simplex paths that lead to the optimal vertex. Exterior Point Simplex Algorithms (EPSA) differs from classical simplex algorithm in the sense that its basic solution is not feasible. EPSA is sufficiently fast for large-scale sparse linear problems. Recall that the total computational effort of an iteration of simplex type algorithms is dominated by the determination of the basis inverse B-1. This inverse does not have to be computed from scratch at any iteration. In this paper we present an analysis of two well-known updating schemes for basis inverse: (i) The Product Form of the Inverse (PFI) and (ii) A Modification of the Product Form of the Inverse (MPFI) and incorporate it with EPSA. Computational results with a subset of benchmark problems from NETLIB are also presented. |
