  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 to 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 to
state-of-the-art commercial solvers on classical linear programming problem
benchmarks, network flow problem benchmarks, and optimal transport problems.
