Affordable Access

Publisher Website

Random Projections for Linear Programming: An Improved Retrieval Phase

Authors
  • Liberti, Leo
  • Manca, Benedetto
  • Poirion, Pierre-Louis
Publication Date
Dec 31, 2023
Identifiers
DOI: 10.1145/3617506
OAI: oai:HAL:hal-04264551v1
Source
Hal-Diderot
Keywords
Language
English
License
Unknown
External links

Abstract

One way to solve very large linear programs in standard form is to apply a random projection to the constraints, then solve the projected linear program [ 63 ]. This will yield a guaranteed bound on the optimal value, as well as a solution to the projected linear program. The process of constructing an approximate solution of the original linear program is called solution retrieval. We improve theoretical bounds on the approximation error of the retrieved solution obtained as in Reference [ 42 ] and propose an improved retrieval method based on alternating projections. We show empirical results illustrating the practical benefits of the new approach.

Report this publication

Statistics

Seen <100 times