no. 16 · Tuesday 17 November 2026
Solving Linear and Integer Programs Faster Using Data
Abstract
We study how much a linear program (LP) or an integer program (IP) can be compressed when solved repeatedly over a fixed feasible region with varying objective coefficients. We provide a framework that compresses LP and IP formulations with guarantees on the probability of preserving optimality, using either an uncertainty set for the cost vector or historical samples. Our framework exposes a tunable tradeoff between compression and the probability of recovering an optimal solution. We characterize the minimum dimension of affine reformulations preserving the full optimizer set over a given cost region and provide sample-based learning algorithms with fast-rate guarantees, without requiring a nondegeneracy assumption for LPs. With high confidence over the training data, the learned reformulation preserves the optimizer set for an independent test cost with probability at least $1-ρ-\widetilde{O}(d^\star_ρ/n)$, where $ρ$ bounds the excluded probability mass and $d^\star_ρ$ is the retained region's decision-relevant dimension. Existing data-driven approaches to LP and IP reduction do not, to our knowledge, learn a single low-dimensional affine reformulation with a prescribed probability of preserving the full optimizer set. Experimental results show substantial improvements over the compared baselines in accuracy, sample efficiency, and computational speed.
- comments
- Accepted at NeurIPS 2026. 32 pages, 11 figures
- fields
- Optimization and Control