eprintid: 10188333
rev_number: 7
eprint_status: archive
userid: 699
dir: disk0/10/18/83/33
datestamp: 2024-03-04 09:41:54
lastmod: 2024-03-04 09:41:54
status_changed: 2024-03-04 09:41:54
type: article
metadata_visibility: show
sword_depositor: 699
creators_name: Akchen, Yi-Chun
creators_name: Mišić, Velibor V
title: Column-Randomized Linear Programs: Performance Guarantees and Applications
ispublished: inpress
divisions: UCL
divisions: B04
divisions: C05
divisions: F49
keywords: linear programming, column generation, constraint sampling, randomized algorithm
note: This version is the author-accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
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.
date: 2024-02-13
date_type: published
publisher: Institute for Operations Research and the Management Sciences (INFORMS)
official_url: https://doi.org/10.1287/opre.2020.0494
oa_status: green
full_text_type: other
language: eng
primo: open
primo_central: open_green
verified: verified_manual
elements_id: 2251792
doi: 10.1287/opre.2020.0494
lyricists_name: Akchen, Yi-Chun
lyricists_id: YCHBD72
actors_name: Akchen, Yi-Chun
actors_id: YCHBD72
actors_role: owner
full_text_status: public
publication: Operations Research
issn: 0030-364X
citation:        Akchen, Yi-Chun;    Mišić, Velibor V;      (2024)    Column-Randomized Linear Programs: Performance Guarantees and Applications.                   Operations Research        10.1287/opre.2020.0494 <https://doi.org/10.1287/opre.2020.0494>.    (In press).    Green open access   
 
document_url: https://discovery.ucl.ac.uk/id/eprint/10188333/1/Akchen_CRLP.pdf