A heuristic method to find a quick feasible solution based on the ratio programming

The feasibility pump is a successful rounding-based heuristic to find a feasible solution to mixed-integer programming (MIP) problems. This paper presents a novel method to find a high-quality feasible solution to 0-1 MIPs in a reasonable time. This method is based on a ratio programming model, which we refer to as a feasible-finder model (FFM). It proves that the optimal solution to FFM is feasible for the original MIP problem. An efficient ratio programming method is adopted to solve FFM by solving a sequence of linear programming problems. Then, to improve the quality of the feasible solution, a quality-controlling cut is generated and added in each iteration. Computational results over instances of CORAL and MIPLIB confirm the effectiveness of our method.

Automated summary

This paper presents a novel method, called the feasible-finder model (FFM), to find a high-quality feasible solution for 0-1 mixed-integer programming problems. By solving a sequence of linear programming problems using an efficient ratio programming method, FFM proves to provide feasible solutions for the original MIP problem. Additionally, a quality-controlling cut is generated and added in each iteration to improve the solution quality. Computational results on CORAL and MIPLIB instances confirm the effectiveness of this method.