# From an Interior Point to a Corner Point: Smart Crossover

**Authors:** Dongdong Ge, Chengwenjian Wang, Zikai Xiong, Yinyu Ye  
**arXiv:** [2102.09420](https://arxiv.org/abs/2102.09420)  
**Date:** 2021-02-18  
**Summary page:** https://www.summarizepaper.com/en/paper/2102.09420v1/

## Key points

- The paper discusses the concept of crossover in linear programming optimization
- Crossover aims to find an optimal corner or extreme point from an approximately optimal inner point
- Authors propose a novel approach that uses problem characteristics and customized strategies to address the bottleneck of lengthy crossover procedures
- For problems with a network structure, the method evaluates columns' potential to form the optimal basis and efficiently identifies a nearby basic feasible solution
- For problems with a large optimal face, a perturbation crossover approach is introduced to locate a corner point of the optimal face
- Proposed method shows significant advantages over state-of-the-art commercial LP solvers in various benchmark tests
- Research provides insights into improving efficiency of crossover procedures in linear programming optimization by tailoring strategies to problem characteristics and leveraging network structures

## Summary

The paper "From an Interior Point to a Corner Point: Smart Crossover" by Dongdong Ge, Chengwenjian Wang, Zikai Xiong, and Yinyu Ye delves into the concept of crossover in linear programming optimization. The crossover procedure aims to find an optimal corner or extreme point from an approximately optimal inner point generated by interior-point methods or first-order algorithms. However, this step often takes significantly longer than previous stages. To address this bottleneck, the authors propose a novel approach that utilizes problem characteristics and implements customized strategies. For problems with a network structure, their method can start from an inexact solution obtained through interior-point methods or other first-order algorithms. By fully exploiting the network structure, the method intelligently evaluates columns' potential to form the optimal basis and efficiently identifies a nearby basic feasible solution. Additionally, for problems with a large optimal face, the authors introduce a perturbation crossover approach to locate a corner point of the optimal face. Through comparison experiments with state-of-the-art commercial LP solvers on classical linear programming benchmarks, network flow benchmarks, and MINST datasets, the proposed method demonstrates significant advantages in practice. Overall, this research provides valuable insights into improving crossover procedures' efficiency in linear programming optimization by tailoring strategies to problem characteristics and effectively leveraging network structures.