Practical Performance of Random Projections in Linear Programming

Leo Liberti; Benedetto Manca; Pierre Louis Poirion

doi:10.4230/LIPIcs.SEA.2022.21

Practical Performance of Random Projections in Linear Programming

Leo Liberti
, Benedetto Manca
, Pierre Louis Poirion

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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.

Original language	English
Title of host publication	20th International Symposium on Experimental Algorithms, SEA 2022
Editors	Christian Schulz, Bora Ucar
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)	9783959772518
DOIs	https://doi.org/10.4230/LIPIcs.SEA.2022.21
Publication status	Published - 1 Jul 2022
Event	20th International Symposium on Experimental Algorithms, SEA 2022 - Heidelberg, Germany Duration: 25 Jul 2022 → 27 Jul 2022

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	233
ISSN (Print)	1868-8969

Conference

Conference	20th International Symposium on Experimental Algorithms, SEA 2022
Country/Territory	Germany
City	Heidelberg
Period	25/07/22 → 27/07/22

Keywords

Computational testing
Johnson-Lindenstrauss Lemma
Linear Programming

Access to Document

10.4230/LIPIcs.SEA.2022.21

Cite this

Liberti, L., Manca, B., & Poirion, P. L. (2022). Practical Performance of Random Projections in Linear Programming. In C. Schulz, & B. Ucar (Eds.), 20th International Symposium on Experimental Algorithms, SEA 2022 Article 21 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 233). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SEA.2022.21

Liberti, Leo ; Manca, Benedetto ; Poirion, Pierre Louis. / Practical Performance of Random Projections in Linear Programming. 20th International Symposium on Experimental Algorithms, SEA 2022. editor / Christian Schulz ; Bora Ucar. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{950e686344ef49a7a591af23ec7449e1,

title = "Practical Performance of Random Projections in Linear Programming",

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.",

keywords = "Computational testing, Johnson-Lindenstrauss Lemma, Linear Programming",

author = "Leo Liberti and Benedetto Manca and Poirion, \{Pierre Louis\}",

note = "Publisher Copyright: {\textcopyright} Leo Liberti, Benedetto Manca, and Pierre-Louis Poirion; 20th International Symposium on Experimental Algorithms, SEA 2022 ; Conference date: 25-07-2022 Through 27-07-2022",

year = "2022",

month = jul,

day = "1",

doi = "10.4230/LIPIcs.SEA.2022.21",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Christian Schulz and Bora Ucar",

booktitle = "20th International Symposium on Experimental Algorithms, SEA 2022",

}

Liberti, L, Manca, B & Poirion, PL 2022, Practical Performance of Random Projections in Linear Programming. in C Schulz & B Ucar (eds), 20th International Symposium on Experimental Algorithms, SEA 2022., 21, Leibniz International Proceedings in Informatics, LIPIcs, vol. 233, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 20th International Symposium on Experimental Algorithms, SEA 2022, Heidelberg, Germany, 25/07/22. https://doi.org/10.4230/LIPIcs.SEA.2022.21

Practical Performance of Random Projections in Linear Programming. / Liberti, Leo; Manca, Benedetto; Poirion, Pierre Louis.
20th International Symposium on Experimental Algorithms, SEA 2022. ed. / Christian Schulz; Bora Ucar. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. 21 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 233).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Practical Performance of Random Projections in Linear Programming

AU - Liberti, Leo

AU - Manca, Benedetto

AU - Poirion, Pierre Louis

N1 - Publisher Copyright: © Leo Liberti, Benedetto Manca, and Pierre-Louis Poirion

PY - 2022/7/1

Y1 - 2022/7/1

N2 - 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.

AB - 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.

KW - Computational testing

KW - Johnson-Lindenstrauss Lemma

KW - Linear Programming

UR - https://www.scopus.com/pages/publications/85130359874

U2 - 10.4230/LIPIcs.SEA.2022.21

DO - 10.4230/LIPIcs.SEA.2022.21

M3 - Conference contribution

AN - SCOPUS:85130359874

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 20th International Symposium on Experimental Algorithms, SEA 2022

A2 - Schulz, Christian

A2 - Ucar, Bora

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 20th International Symposium on Experimental Algorithms, SEA 2022

Y2 - 25 July 2022 through 27 July 2022

ER -

Liberti L, Manca B, Poirion PL. Practical Performance of Random Projections in Linear Programming. In Schulz C, Ucar B, editors, 20th International Symposium on Experimental Algorithms, SEA 2022. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2022. 21. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.SEA.2022.21

Practical Performance of Random Projections in Linear Programming

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this