1 Search Results for "Maros, István"


Document
Product Form of the Inverse Revisited

Authors: Péter Tar and István Maros

Published in: OASIcs, Volume 22, 3rd Student Conference on Operational Research (2012)


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.

Cite as

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)


Copy BibTex To Clipboard

@InProceedings{tar_et_al:OASIcs.SCOR.2012.64,
  author =	{Tar, P\'{e}ter and Maros, Istv\'{a}n},
  title =	{{Product Form of the Inverse Revisited}},
  booktitle =	{3rd Student Conference on Operational Research},
  pages =	{64--74},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-39-2},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{22},
  editor =	{Ravizza, Stefan and Holborn, Penny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SCOR.2012.64},
  URN =		{urn:nbn:de:0030-drops-35475},
  doi =		{10.4230/OASIcs.SCOR.2012.64},
  annote =	{Keywords: Linear optimization, Simplex method, Basis inverse, Product form of the inverse}
}
  • Refine by Author
  • 1 Maros, István
  • 1 Tar, Péter

  • Refine by Classification

  • Refine by Keyword
  • 1 Basis inverse
  • 1 Linear optimization
  • 1 Product form of the inverse
  • 1 Simplex method

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2012

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