Column-Randomized Linear Programs: Performance Guarantees and Applications

Yi-Chun Akchen () and Velibor V. Mišić ()
Additional contact information
Yi-Chun Akchen: School of Management, University College London, London E14 5AB, United Kingdom
Velibor V. Mišić: UCLA Anderson School of Management, University of California, Los Angeles, California 90095

Operations Research, 2025, vol. 73, issue 3, 1366-1383

Abstract: We propose a randomized method for solving linear programs with a large number of columns but a relatively small number of constraints. Because enumerating all the columns is usually unrealistic, such linear programs are commonly solved by column generation, which is often still computationally challenging because of the intractability of the subproblem in many applications. Instead of iteratively introducing one column at a time as in column generation, our proposed method involves sampling a collection of columns according to a user-specified randomization scheme and solving the linear program consisting of the sampled columns. Although similar methods for solving large-scale linear programs by sampling columns (or, equivalently, sampling constraints in the dual) have been proposed in the literature, in this paper we derive an upper bound on the optimality gap that holds with high probability. This bound converges to the optimality gap of a linear program related to the sampling distribution at a rate inversely proportional to the square root of the number of sampled columns. We analyze the gap of this latter linear program, which we dub the distributional counterpart, and derive conditions under which this gap will be small. Finally, we numerically demonstrate the effectiveness of the proposed method in the cutting-stock problem and in nonparametric choice model estimation.

Keywords: Optimization; linear programming; column generation; constraint sampling; randomized algorithm (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.0494 (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:oropre:v:73:y:2025:i:3:p:1366-1383

Access Statistics for this article

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