From an Interior Point to a Corner Point: Smart Crossover

References

• Ahuja RK, Orlin JB, Magnanti TL (1993) Network Flows: Theory, Algorithms, and Applications (Prentice Hall, Upper Saddle River, NJ).Google Scholar
• Altschuler J, Weed J, Rigollet P (2017) Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. Guyon I, Von Luxburg U, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Advances in Neural Information Processing Systems (Curran Associates, Inc., Red Hook, New York), vol. 30, 1961–1971.Google Scholar
• Andersen ED (1999) On exploiting problem structure in a basis identification procedure for linear programming. INFORMS J. Comput. 11(1):95–103.Link, Google Scholar
• Andersen ED (2009) The homogeneous and self-dual model and algorithm for linear optimization. Technical report, MOSEK ApS, Copenhagen.Google Scholar
• Andersen ED, Andersen KD (2000) The MOSEK interior point optimizer for linear programming: An implementation of the homogeneous algorithm. Frenk H, Roos K, Terlaky T, Zhang S, eds. High Performance Optimization, Applied Optimization, vol. 33 (Springer, Boston), 197–232.Google Scholar
• Andersen ED, Ye Y (1996) Combining interior-point and pivoting algorithms for linear programming. Management Sci. 42(12):1719–1731.Link, Google Scholar
• Applegate D, Díaz M, Hinder O, Lu H, Lubin M, O’Donoghue B, Schudy W (2021) Practical large-scale linear programming using primal-dual hybrid gradient. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Vaughan JW, eds. Advances in Neural Information Processing Systems, vol. 34 (Curran Associates, Inc., Red Hook, NY), 20243–20257.Google Scholar
• Bergner M, Lübbecke ME, Witt JT (2014) A branch-price-and-cut algorithm for packing cuts in undirected graphs. Gudmundsson J, Katajainen J, eds. Experimental Algorithms, SEA 2014, Lecture Notes in Computer Science, vol. 8504 (Springer, Cham, Switzerland), 34–45.Google Scholar
• Berkelaar AB, Jansen B, Roos K, Terlaky T (1999) Basis- and partition identification for quadratic programming and linear complementarity problems. Math. Programming 86(2):261–282.Crossref, Google Scholar
• Bertsimas D, Tsitsiklis JN (1997) Introduction to Linear Optimization (Athena Scientific, Belmont, MA).Google Scholar
• Bixby RE (1994) Commentary—Progress in linear programming. ORSA J. Comput. 6(1):15–22.Link, Google Scholar
• Bixby RE, Saltzman MJ (1994) Recovering an optimal LP basis from an interior point solution. Oper. Res. Lett. 15(4):169–178.Crossref, Google Scholar
• Bowman EH (1956) Production scheduling by the transportation method of linear programming. Oper. Res. 4(1):100–103.Link, Google Scholar
• Charnes A (1952) Optimality and degeneracy in linear programming. Econometrica 20(2):160–170.Crossref, Google Scholar
• Charnes A, Cooper WW (1954) The stepping stone method of explaining linear programming calculations in transportation problems. Management Sci. 1(1):49–69.Link, Google Scholar
• Chazelle B (2000) A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM 47(6):1028–1047.Crossref, Google Scholar
• CORE-OR (2024) Clp. Accessed December 7, 2024, https://github.com/coin-or/Clp.Google Scholar
• Cuturi M (2013) Sinkhorn distances: Lightspeed computation of optimal transport. Burges CJ, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Advances in Neural Information Processing Systems, vol. 26 (Curran Associates, Inc., Red Hook, NJ), 2292–2300.Google Scholar
• Deng Q, Feng Q, Gao W, Ge D, Jiang B, Jiang Y, Liu J, et al. (2024) An enhanced alternating direction method of multipliers-based interior point method for linear and conic optimization. INFORMS J. Comput., ePub ahead of print May 31, https://doi.org/10.1287/ijoc.2023.0017.Link, Google Scholar
• Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerical Math. 1(1):269–271.Crossref, Google Scholar
• El-Bakry A, Tapia RA, Zhang Y (1994) A study of indicators for identifying zero variables in interior-point methods. SIAM Rev. 36(1):45–72.Crossref, Google Scholar
• Forrest JJ, Goldfarb D (1992) Steepest-edge simplex algorithms for linear programming. Math. Programming 57(1–3):341–374.Crossref, Google Scholar
• Galabova I, Hall J (2020) The ‘Idiot’ crash quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems. Optim. Methods Software 35(3):488–501.Crossref, Google Scholar
• Galichon A (2018) Optimal Transport Methods in Economics (Princeton University Press, Princeton, NJ).Google Scholar
• Gao W, Ge D, Sun C, Ye Y (2023) Solving linear programs with fast online learning algorithms. Krause A, Brunskill E, Cho K, Engelhardt B, Sabato S, Scarlett J, eds. Proc. 40th Internat. Conf. Machine Learn, Proceedings of Machine Learning Research, vol. 202 (PMLR, New York), 10649–10675.Google Scholar
• Ge D, Wang H, Xiong Z, Ye Y (2019) Interior-point methods strike back: Solving the Wasserstein barycenter problem. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 32 (Curran Associates, Inc., Red Hook, NY), 6894–6905.Google Scholar
• Ge D, Wang C, Xiong Z, Ye Y (2024) From an interior point to a corner point: Smart crossover. http://dx.doi.org/10.1287/ijoc.2022.0291.cd, https://github.com/INFORMSJoC/2022.0291.Google Scholar
• Glavelis T, Ploskas N, Samaras N (2018) Improving a primal–dual simplex-type algorithm using interior point methods. Optimization 67(12):2259–2274.Crossref, Google Scholar
• Gleixner A, Hendel G, Gamrath G, Achterberg T, Bastubbe M, Berthold T, Christophel P, et al. (2021) MIPLIB 2017: Data-driven compilation of the 6th mixed-integer programming library. Math. Programming Comput. 13(3):443–490.Crossref, Google Scholar
• Goldman AJ, Tucker AW (1956) Theory of linear programming. Linear Inequalities Related Systems 38:53–97.Google Scholar
• Gurobi Optimization, LLC (2024) Gurobi optimizer reference manual. Accessed December 7, 2024, https://www.gurobi.com.Google Scholar
• Hanssmann F, Hess SW (1960) A linear programming approach to production and employment scheduling. Management Sci. MT-1(1):46–51.Link, Google Scholar
• Ho N, Huynh V, Phung D, Jordan M (2019) Probabilistic multilevel clustering via composite transportation distance. Proc. Twenty-Second Internat. Conf. Artificial Intelligence Statistics, Proceedings of Machine Learning Research, vol. 89 (PMLR, New York), 3149–3157.Google Scholar
• Li X, Sun D, Toh KC (2020) An asymptotically superlinearly convergent semismooth Newton augmented Lagrangian method for linear programming. SIAM J. Optim. 30(3):2410–2440.Crossref, Google Scholar
• Lin T, Ma S, Ye Y, Zhang S (2020) An ADMM-based interior-point method for large-scale linear programming. Optim. Methods Software 36(2–3):1–36.Google Scholar
• Liu Q, Van Ryzin G (2008) On the choice-based linear programming model for network revenue management. Manufacturing Service Oper. Management 10(2):288–310.Link, Google Scholar
• Lu H, Yang J (2023) cuPDLP.jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia. Preprint, submitted June 7, https://arxiv.org/abs/2311.12180.Google Scholar
• Maes C, Rothberg E, Gu Z, Bixby R (2014) Initial basis selection for LP crossover. Accessed March 24, 2023, https://cerfacs.fr/en/sparse-days-meeting-2014-at-cerfacs-toulouse.Google Scholar
• Megiddo N (1991) On finding primal-and dual-optimal bases. ORSA J. Comput. 3(1):63–65.Link, Google Scholar
• Megiddo N, Chandrasekaran R (1989) On the ε-perturbation method for avoiding degeneracy. Oper. Res. Lett. 8(6):305–308.Crossref, Google Scholar
• Mehrotra S (1991) On finding a vertex solution using interior point methods. Linear Algebra Its Appl. 152:233–253.Crossref, Google Scholar
• Mehrotra S, Ye Y (1993) Finding an interior point in the optimal face of linear programs. Math. Programming 62(1–3):497–515.Crossref, Google Scholar
• Nesterov Y (2018) Lectures on Convex Optimization (Springer, Berlin).Crossref, Google Scholar
• Nesterov Y, Nemirovskii A (1994) Interior-Point Polynomial Algorithms in Convex Programming (SIAM, Philadelphia).Crossref, Google Scholar
• Nguyen X (2013) Convergence of latent mixing measures in finite and infinite mixture models. Ann. Statist. 41(1):370–400.Crossref, Google Scholar
• O’Donoghue B, Chu E, Parikh N, Boyd S (2016) Conic optimization via operator splitting and homogeneous self-dual embedding. J. Optim. Theory Appl. 169(3):1042–1068.Crossref, Google Scholar
• Orlin JB (1997) A polynomial time primal network simplex algorithm for minimum cost flows. Math. Programming 78:109–129.Crossref, Google Scholar
• Prim RC (1957) Shortest connection networks and some generalizations. Bell System Tech. J. 36(6):1389–1401.Crossref, Google Scholar
• Renegar J (2001) A Mathematical View of Interior-Point Methods in Convex Optimization (SIAM, Philadelphia).Crossref, Google Scholar
• Santambrogio F (2015) Optimal Transport for Applied Mathematicians (Springer, Berlin).Crossref, Google Scholar
• Schork L, Gondzio J (2020) Implementation of an interior point method with basis preconditioning. Math. Programming Comput. 12(4):603–635.Crossref, Google Scholar
• Tapia R, Zhang Y (1991) An optimal-basis identification technique for interior-point linear programming algorithms. Linear Algebra Appl. 152:343–363.Crossref, Google Scholar
• Todd MJ, Ye Y (1990) A centered projective algorithm for linear programming. Math. Oper Res. 15(3):508–529.Link, Google Scholar
• Wang H, Ghosal P, Mazumder R (2023) Linear programming using diagonal linear networks. Preprint, submitted October 4, https://arxiv.org/abs/2310.02535.Google Scholar
• Wolfe P (1965) The composite simplex algorithm. SIAM Rev. 7(1):42–54.Crossref, Google Scholar
• Ye Y (1992) On the finite convergence of interior-point algorithms for linear programming. Math. Programming 57(1–3):325–335.Crossref, Google Scholar