Solving Large Batches of Linear Programs

Solving a large batch of linear programs (LPs) with varying parameters is needed in stochastic programming and sensitivity analysis, among other modeling frameworks. Solving the LPs for all combinations of given parameter values, called the brute-force approach, can be computationally infeasible when the parameter space is high-dimensional and/or the underlying LP is computationally challenging. This paper introduces a computationally efficient approach for solving a large number of LPs that differ only in the right-hand side of the constraints ( b of A x = b ). The computational approach builds on theoretical properties of the geometry of the space of critical regions, where a critical region is defined as the set of b ’s for which a basis is optimal. To formally support our computational approach we provide proofs of geometric properties of neighboring critical regions. We contribute to the existing theory of parametric programming by establishing additional results, providing deeper geometric understanding of critical regions. On the basis of the geometric properties of critical regions, we develop an algorithm that solves the LPs in batches by finding critical regions that contain multiple b ’s. Moreover, we suggest a data-driven version of our algorithm that uses the distribution (e.g., shape) of a sample of b ’s for which the LPs need to be solved. We empirically compared our approach and three other methods on various instances. The results show the efficiency of our approach in comparison with the other methods but also indicate some limitations of the algorithm.