  Identifying optimal basic feasible solutions to linear programming problems
is critical 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 some approaches to overcome this
bottleneck by smartly 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, aimed at recovering basic
solutions by identifying nearby spanning tree structures. For general linear
programs, we propose to recover 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.

Optimization and Control