A New Crossover Algorithm for LP Inspired by the Spiral Dynamic of PDHG

References

• Amor HB, Desrosiers J, Soumis F (2006) Recovering an optimal LP basis from an optimal dual solution. Oper. Res. Lett. 34(5):569–576.Crossref, 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, Lu H, Lubin M (2024) Infeasibility detection with primal-dual hybrid gradient for large-scale linear programming. SIAM J. Optim. 34(1):459–484.Crossref, Google Scholar
• Applegate D, Hinder O, Lu H, Lubin M (2023) Faster first-order primal-dual methods for linear programming using restarts and sharpness. Math. Programming 201(1):133–184.Crossref, 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 P, Vaughan JW, eds. Adv. Neural Inform. Processing Systems, vol. 34 (Curran Associates Inc., Red Hook, NY), 20243–20257.Google Scholar
• Baillon JB, Bruck RE, Reich S (1978) On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces. Houston J. Math. 4(1):1–9. 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
• Blin N (2024) Accelerate large linear programming problems with NVIDIA cuOpt. Accessed December 23, 2025, https://developer.nvidia.com/blog/accelerate-large-linear-programming-problems-with-nvidia-cuopt/.Google Scholar
• Chambolle A, Pock T (2011) A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40(1):120–145. Crossref, Google Scholar
• Charnes A, Kortanek K (1963) An opposite sign algorithm for purification to an extreme point solution. Office Naval Res. Memorandum 84.Google Scholar
• Charnes A, Kortanek K, Raike W (1965) Extreme point solutions in mathematical programming: An opposite sign algorithm. Systems Res. Memorandum 129.Google Scholar
• Dantzig GB (1951) Maximization of a linear function of variables subject to linear inequalities. Koopmans TC, ed. Activity Analysis of Production and Allocation (John Wiley, Hoboken, NJ), 339–347.Google Scholar
• Dantzig GB (1963) Linear Programming and Extensions (Princeton University Press, Princeton, NJ).Crossref, 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. 37(2):338–359.Link, Google Scholar
• Esser E, Zhang X, Chan TF (2010) A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4):1015–1046.Crossref, Google Scholar
• FICO Xpress (2024) FICO Xpress Optimization Suite Documentation. Accessed December 23, 2025, https://www.fico.com/fico-xpress-optimization/docs/latest/overview.html.Google Scholar
• Fong DCL, Saunders M (2011) LSMR: An iterative algorithm for sparse least-squares problems. SIAM J. Sci. Comput. 33(5):2950–2971.Crossref, Google Scholar
• Gay DM (1985) Electronic mail distribution of linear programming test problems. Math. Programming Soc. COAL Newsletter 13:10–12.Google Scholar
• Ge D, Wang C, Xiong Z, Ye Y (2025a) From an interior point to a corner point: Smart crossover. INFORMS J. Comput. 37(6):1433–1688.Link, Google Scholar
• Ge D, Huangfu Q, Wang Z, Wu J, Ye Y (2025b) Cardinal Optimizer (COPT) user guide. Accessed December 23, 2025, https://guide.coap.online/copt/en-doc.Google Scholar
• Halpern B (1967) Fixed points of nonexpanding maps. Bull. Amer. Math. Soc. 73:957–961. Crossref, Google Scholar
• Huangfu Q, Hall JJ (2018) Parallelizing the dual revised simplex method. Math. Programming Comput. 10(1):119–142.Crossref, Google Scholar
• Karmarkar N (1984) A new polynomial-time algorithm for linear programming. Proc. Sixteenth Annual ACM Symposium Theory Comput., 302–311.Google Scholar
• Khachiyan LG 1979) A polynomial algorithm in linear programming. Soviet Math. Doklady 20:191–194. Google Scholar
• Kortanek K, Jishan Z (1988) New purification algorithms for linear programming. Naval Res. Logist. (NRL) 35(4):571–583.Crossref, Google Scholar
• Lin T, Ma S, Ye Y, Zhang S (2021) An ADMM-based interior-point method for large-scale linear programming. Optim. Methods Software 36(2–3):389–424.Crossref, Google Scholar
• Liu T, Lu H (2026) A new crossover algorithm for LP inspired by the spiral dynamic of PDHG. https://doi.org/10.1287/ijoc.2024.0996.cd, https://github.com/INFORMSJoC/2024.0996.Google Scholar
• Lu H, Yang J (2022) On the infimal sub-differential size of primal-dual hybrid gradient method and beyond. Preprint, submitted June 24, https://arxiv.org/abs/2206.12061.Google Scholar
• Lu H, Yang J (2023a) cuPDLP.jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia. Preprint, submitted November 20, https://arxiv.org/abs/2311.12180.Google Scholar
• Lu H, Yang J (2023b) On a unified and simplified proof for the ergodic convergence rates of PPM, PDHG and ADMM. Preprint, submitted May 3, https://arxiv.org/abs/2305.02165.Google Scholar
• Lu H, Yang J (2024) Restarted Halpern PDHG for linear programming. Preprint, submitted July 23, https://arxiv.org/abs/2407.16144.Google Scholar
• Lu H, Yang J (2025) On the geometry and refined rate of primal–Dual hybrid gradient for linear programming. Math. Programming 212(1–2):349–387.Google Scholar
• Lu H, Yang J, Hu H, Huangfu Q, Liu J, Liu T, Ye Y, Zhang C, Ge D (2023) cuPDLP-C: A strengthened implementation of cuPDLP for linear programming by C language. Preprint, submitted December 22, https://arxiv.org/abs/2312.14832.Google Scholar
• Megiddo N (1991) On finding primal- and dual-optimal bases. ORSA J. Comput. 3(1):63–65.Link, Google Scholar
• Mehrotra S (1991) On finding a vertex solution using interior point methods. Linear Algebra Appl. 152:233–253.Crossref, Google Scholar
• O’Donoghue B (2021) Operator splitting for a homogeneous embedding of the linear complementarity problem. SIAM J. Optim. 31(3):1999–2023. 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
• Pazy A (1971) Asymptotic behavior of contractions in Hilbert space. Israel J. Math. 9(2):235–240. Crossref, Google Scholar
• Perron L, Furnon V (2024) OR-Tools. Accessed December 23, 2025, https://developers.google.com/optimization/.Google Scholar
• Poon C, Liang J (2019) Trajectory of alternating direction method of multipliers and adaptive acceleration. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform. Processing Systems, vol. 32 (Curran Associates Inc., Red Hook, NY), 7325–7333.Google Scholar
• Poon C, Liang J (2020) Geometry of first-order methods and adaptive acceleration. Preprint, submitted March 9, https://arxiv.org/abs/2003.03910.Google Scholar
• Renegar J (1988) A polynomial-time algorithm, based on Newton’s method, for linear programming. Math. Programming 40(1):59–93.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
• Xiong Z, Freund RM (2024) The role of level-set geometry on the performance of PDHG for conic linear optimization. Preprint, submitted June 4, https://arxiv.org/abs/2406.01942.Google Scholar
• Zhu M, Chan T (2008) An efficient primal-dual hybrid gradient algorithm for total variation image restoration. UCLA CAM Rep. (University of California, Los Angeles), 8–34.Google Scholar