Product Form of the Inverse Revisited

Authors Péter Tar, István Maros



PDF
Thumbnail PDF

File

OASIcs.SCOR.2012.64.pdf
  • Filesize: 399 kB
  • 11 pages

Document Identifiers

Author Details

Péter Tar
István Maros

Cite AsGet BibTex

Péter Tar and István Maros. Product Form of the Inverse Revisited. In 3rd Student Conference on Operational Research. Open Access Series in Informatics (OASIcs), Volume 22, pp. 64-74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/OASIcs.SCOR.2012.64

Abstract

Using the simplex method (SM) is one of the most effective ways of solving large scale real life linear optimization problems. The efficiency of the solver is crucial. The SM is an iterative procedure, where each iteration is defined by a basis of the constraint set. In order to speed up iterations, proper basis handling procedures must be applied. Two methodologies exist in the state-of-the-art literature, the product form of the inverse (PFI) and lower-upper triangular (LU) factorization. Nowadays the LU method is widely used because 120-150 iterations can be done without the need of refactorization while the PFI can make only about 30-60 iterations without reinversion in order to maintain acceptable numerical accuracy. In this paper we revisit the PFI and present a new version that can make hundreds or sometimes even few thousands of iterations without losing accuracy. The novelty of our approach is in the processing of the non-triangular part of the basis, based on block-triangularization algorithms. The new PFI performs much better than those found in the literature. The results can shed new light on the usefulness of the PFI.
Keywords
  • Linear optimization
  • Simplex method
  • Basis inverse
  • Product form of the inverse

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail