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

Motivated by large-scale applications, there is a recent trend of research on using first-order methods for solving LP. Among them, PDLP, which is based on a primal-dual hybrid gradient (PDHG) algorithm, may be the most promising one. In this paper, we present a geometric viewpoint on the behavior of PDHG for LP. We demonstrate that PDHG iterates exhibit a spiral pattern with a closed-form solution when the variable basis remains unchanged. This spiral pattern consists of two orthogonal components: rotation and forward movement, where rotation improves primal and dual feasibility, while forward movement advances the duality gap. We also characterize the different situations in which basis change events occur. Inspired by the spiral behavior of PDHG, we design a new crossover algorithm to obtain a vertex solution from any optimal LP solution. This approach differs from traditional simplex-based crossover methods. Our numerical experiments demonstrate the effectiveness of the proposed algorithm, showcasing its potential as an alternative option for crossover.

History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous.

Funding: T. Liu is partially supported by National Natural Science Foundation of China [Grants NSFC-72225009, 72394360, 72394365]. H. Lu is partially supported by Air Force Office of Scientific Research [Grant FA9550-24-1-0051] and Office of Naval Research [Grant N000142412735].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0996) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0996). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.