Abstract:We study how much a linear program (LP) can be compressed when solved repeatedly, given prior knowledge about its objective function. Existing data-driven projection methods learn low-dimensional surrogate LPs with approximate objective-value guarantees, but cannot provably identify the optimal projection for a prescribed compression budget. We instead ask a sharper question: how far can an LP be compressed into a lower-dimensional equivalent while \emph{exactly} preserving optimality, enabling faster repeated solves with no loss in solution quality? We provide an exact geometric characterization of such compressed LPs, together with a tractable sample-based learning algorithm that comes with fast-rate guarantees: the compressed LP recovers the optimal solution of an unseen instance with probability at least $1-\widetilde O(d^\star/n)$, where $d^\star$ is the dimension of the decision-relevant subspace, and $n$ is the number of available historical LP samples. This $1/n$ dependence is sharper than the $\widetilde O(1/\sqrt n)$ uniform-convergence rates of approximate projection methods. Our framework further exposes a tunable tradeoff between the dimension of the compressed LP and the probability of recovering the optimal solution, allowing the user to trade compression for accuracy.
| Comments: | 27 pages, 11 figures |
| Subjects: | Optimization and Control (math.OC) |
| MSC classes: | 90C05 (Primary), 90C60, 68Q32, 90C31, 52B55 (Secondary) |
| Cite as: | arXiv:2605.25635 [math.OC] |
| (or arXiv:2605.25635v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2605.25635 arXiv-issued DOI via DataCite (pending registration) |
From: Yuhan Ye [view email]
[v1]
Mon, 25 May 2026 09:33:53 UTC (2,223 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。