Column-Randomized Linear Programs: Performance Guarantees and Applications

References

• Agrawal S, Wang Z, Ye Y (2014) A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4):876–890.Link, Google Scholar
• Bertsimas D, Tsitsiklis JN (1997) Introduction to Linear Optimization, Athena Scientific Series in Optimization and Neural Computation, vol. 6 (Athena Scientific, Nashua, NH).Google Scholar
• Bertsimas D, Vempala S (2004) Solving convex programs by random walks. J. ACM 51(4):540–556.Crossref, Google Scholar
• Bertsimas D, Chang A, Mišić VV, Mundru N (2019) The airlift planning problem. Transportation Sci. 53(3):773–795.Link, Google Scholar
• Birge JR, Louveaux F (2011) Introduction to Stochastic Programming (Springer Science & Business Media, New York).Crossref, Google Scholar
• Block HD, Marschak J (1959) Random orderings and stochastic theories of response. Technical report, Cowles Foundation for Research in Economics, Yale University, New Haven, CT.Google Scholar
• Bront JJM, Méndez-Díaz I, Vulcano G (2009) A column generation algorithm for choice-based network revenue management. Oper. Res. 57(3):769–784.Link, Google Scholar
• Calafiore G, Campi MC (2005) Uncertain convex programs: Randomized solutions and confidence levels. Math. Programming 102(1):25–46.Crossref, Google Scholar
• Calafiore GC, Campi MC (2006) The scenario approach to robust control design. IEEE Trans. Automat. Control 51(5):742–753.Crossref, Google Scholar
• Campi MC, Garatti S (2008) The exact feasibility of randomized solutions of uncertain convex programs. SIAM J. Optim. 19(3):1211–1230.Crossref, Google Scholar
• Campi MC, Garatti S (2018) Wait-and-judge scenario optimization. Math. Programming 167(1):155–189.Crossref, Google Scholar
• Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper. Res. 8(1):101–111.Link, Google Scholar
• De Farias DP, Van Roy B (2004) On constraint sampling in the linear programming approach to approximate dynamic programming. Math. Oper. Res. 29(3):462–478.Link, Google Scholar
• Desrosiers J, Lübbecke ME (2005) A primer in column generation. Desaulniers G, Desrosiers J, Solomon MM, eds. Column Generation (Springer, New York), 1–32.Crossref, Google Scholar
• du Merle O, Villeneuve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Discrete Math. 194(1–3):229–237.Crossref, Google Scholar
• Dumas Y, Desrosiers J, Soumis F (1991) The pickup and delivery problem with time windows. Eur. J. Oper. Res. 54(1):7–22.Crossref, Google Scholar
• Eghbali R, Saunderson J, Fazel M (2018) Competitive online algorithms for resource allocation over the positive semidefinite cone. Math. Programming 170(1):267–292.Crossref, Google Scholar
• Elmachtoub AN, Grigas P (2017) Smart “predict, then optimize.” Preprint, submitted October 22, https://arxiv.org/abs/1710.08005.Google Scholar
• Farias VF, Jagabathula S, Shah D (2013) A nonparametric approach to modeling choice with limited data. Management Sci. 59(2):305–322.Link, Google Scholar
• Feillet D (2010) A tutorial on column generation and branch-and-price for vehicle routing problems. 4-OR-Q J. Oper. Res. 8(4):407–424.Crossref, Google Scholar
• Ford LR Jr, Fulkerson DR (1958) A suggested computation for maximal multi-commodity network flows. Management Sci. 5(1):97–101.Link, Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, Series of Books in the Mathematical Sciences, vol. 174 (W. H. Freeman, San Francisco).Google Scholar
• Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Oper. Res. 9(6):849–859.Link, Google Scholar
• Klose A, Drexl A (2005) Lower bounds for the capacitated facility location problem based on column generation. Management Sci. 51(11):1689–1705.Link, Google Scholar
• Li X, Ye Y (2019) Online linear programming: Dual convergence, new algorithms, and regret bounds. Preprint, submitted September 12, https://arxiv.org/abs/1909.05499.Google Scholar
• Mišić VV (2016) Data, models and decisions for large-scale stochastic optimization problems. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• Mohajerin Esfahani P, Sutter T, Lygeros J (2014) Performance bounds for the scenario approach and an extension to a class of non-convex programs. IEEE Trans. Automat. Control 60(1):46–58.Crossref, Google Scholar
• Moosmann F, Triggs B, Jurie F (2007) Fast discriminative visual codebooks using randomized clustering forests. Schölkopf B, Platt J, Hoffman T, eds. Adv. Neural Inform. Processing Systems 19 (NIPS 2006) (Neural Information Processing Systems Foundation, Inc., La Jolla, CA), 985–992.Google Scholar
• Pilanci M, Wainwright MJ (2015) Randomized sketches of convex programs with sharp guarantees. IEEE Trans. Inform. Theory 61(9):5096–5115.Crossref, Google Scholar
• Rahimi A, Recht B (2008) Random features for large-scale kernel machines. Platt J, Koller D, Singer Y, Roweis S, eds. Adv. Neural Inform. Processing Systems 20 (NIPS 2007) (Neural Information Processing Systems Foundation, Inc., La Jolla, CA), 1177–1184.Google Scholar
• Rahimi A, Recht B (2009) Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. Koller D, Schuurmans D, Bengio Y, Bottou L, eds. Adv. Neural Inform. Processing Systems 21 (NIPS 2008) (Neural Information Processing Systems Foundation, Inc., La Jolla, CA), 1313–1320.Google Scholar
• Shalev-Shwartz S (2012) Online learning and online convex optimization. Foundations Trends Machine Learn. 4(2):107–194.Crossref, Google Scholar
• Shalev-Shwartz S, Ben-David S (2014) Understanding Machine Learning: From Theory to Algorithms (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Shapiro A, Dentcheva D, Ruszczyński A (2021) Lectures on Stochastic Programming: Modeling and Theory (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Sturt B (2021) The value of robust assortment optimization under ranking-based choice models. Preprint, submitted December 9, https://arxiv.org/abs/2112.05010.Google Scholar
• van Ryzin G, Vulcano G (2015) A market discovery algorithm to estimate a general class of nonparametric choice models. Management Sci. 61(2):281–300.Link, Google Scholar
• Vu K, Poirion P-L, Liberti L (2018) Random projections for linear programming. Math. Oper. Res. 43(4):1051–1071.Link, Google Scholar