Solving Large Batches of Linear Programs

Ilbin Lee (), Stewart Curry () and Nicoleta Serban ()
Additional contact information
Ilbin Lee: Alberta School of Business, University of Alberta, Edmonton, Alberta T6G 2R6, Canada
Stewart Curry: Georgia Institute of Technology, Atlanta, Georgia 30332
Nicoleta Serban: Georgia Institute of Technology, Atlanta, Georgia 30332

INFORMS Journal on Computing, 2019, vol. 31, issue 2, 302-317

Abstract: 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.

Keywords: linear programming; sensitivity analysis; stochastic programming; simplex method (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0838 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:2:p:302-317

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().