DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2022.21

Practical Performance of Random Projections in Linear Programming

Authors: Leo Liberti, Benedetto Manca, and Pierre-Louis Poirion

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract

The use of random projections in mathematical programming allows standard solution algorithms to solve instances of much larger sizes, at least approximately. Approximation results have been derived in the relevant literature for many specific problems, as well as for several mathematical programming subclasses. Despite the theoretical developments, it is not always clear that random projections are actually useful in solving mathematical programs in practice. In this paper we provide a computational assessment of the application of random projections to linear programming.

Cite as

Leo Liberti, Benedetto Manca, and Pierre-Louis Poirion. Practical Performance of Random Projections in Linear Programming. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{liberti_et_al:LIPIcs.SEA.2022.21,
  author =	{Liberti, Leo and Manca, Benedetto and Poirion, Pierre-Louis},
  title =	{{Practical Performance of Random Projections in Linear Programming}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.21},
  URN =		{urn:nbn:de:0030-drops-165550},
  doi =		{10.4230/LIPIcs.SEA.2022.21},
  annote =	{Keywords: Linear Programming, Johnson-Lindenstrauss Lemma, Computational testing}
}

Search Results

Documents authored by Manca, Benedetto

Practical Performance of Random Projections in Linear Programming

Abstract

Cite as

Thanks for your feedback!

Could not send message