License
when quoting this document, please refer to the following
DOI: 10.4230/OASIcs.SCOR.2012.64
URN: urn:nbn:de:0030-drops-35475
URL: http://drops.dagstuhl.de/opus/volltexte/2012/3547/

Tar, Péter ; Maros, István

Product Form of the Inverse Revisited

pdf-format:
Dokument 1.pdf (400 KB)


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.

BibTeX - Entry

@InProceedings{tar_et_al:OASIcs:2012:3547,
  author =	{P{\'e}ter Tar and Istv{\'a}n Maros},
  title =	{{Product Form of the Inverse Revisited}},
  booktitle =	{3rd Student Conference on Operational Research},
  pages =	{64--74},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-39-2},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{22},
  editor =	{Stefan Ravizza and Penny Holborn},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3547},
  URN =		{urn:nbn:de:0030-drops-35475},
  doi =		{http://dx.doi.org/10.4230/OASIcs.SCOR.2012.64},
  annote =	{Keywords: Linear optimization, Simplex method, Basis inverse, Product form of the inverse}
}

Keywords: Linear optimization, Simplex method, Basis inverse, Product form of the inverse
Seminar: 3rd Student Conference on Operational Research
Issue date: 2012
Date of publication: 26.06.2012


DROPS-Home | Fulltext Search | Imprint Published by LZI