*Result*: From an Interior Point to a Corner Point: Smart Crossover.
*Further Information*
*Identifying optimal basic feasible solutions to linear programming problems is a critical task for mixed integer programming and other applications. The crossover method, which aims at deriving an optimal extreme point from a suboptimal solution (the output of a starting method such as interior-point methods or first-order methods), is crucial in this process. This method, compared with the starting method, frequently represents the primary computational bottleneck in practical applications. We propose approaches to overcome this bottleneck by exploiting problem characteristics and implementing customized strategies. For problems arising from network applications and exhibiting network structures, we take advantage of the graph structure of the problem and the tree structure of the optimal solutions. Based on these structures, we propose a tree-based crossover method, aiming to recovering basic solutions by identifying nearby spanning tree structures. For general linear programs, we propose recovering an optimal basic solution by identifying the optimal face and employing controlled perturbations based on the suboptimal solution provided by interior-point methods. We prove that an optimal solution for the perturbed problem is an extreme point, and its objective value is at least as good as that of the initial interior-point solution. Computational experiments show significant speed-ups achieved by our methods compared with state-of-the-art commercial solvers on classical linear programming problem benchmarks, network flow problem benchmarks, and optimal transport problems. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: D. Ge was supported by the National Natural Science Foundation of China [Grants 72150001, 72225009, 72394360, and 72394365]. 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.2022.0291) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0291). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]
Copyright of INFORMS Journal on Computing is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)*
*Full text is not displayed to guests* *Login for full access*