PUSH: a primal heuristic based on Feasibility PUmp and SHifting
This work provides an incremental improvement in primal heuristics for mixed-integer programming, benefiting optimization practitioners by enhancing solution feasibility in specific domains.
The authors tackled the problem of finding feasible solutions for mixed-integer programming by introducing PUSH, a primal heuristic that combines Feasibility Pump and Shifting, which directly handles equality constraints without row duplication and outperformed other heuristics like Simple Rounding and Feasibility Pump on benchmark instances.
This work describes PUSH, a primal heuristic combining Feasibility Pump and Shifting. The main idea is to replace the rounding phase of the Feasibility Pump with a suitable adaptation of the Shifting and other rounding heuristics. The algorithm presents different strategies, depending on the nature of the partial rounding obtained. In particular, we distinguish when the partial solution is feasible, infeasible with potential candidates, and infeasible without candidates. We used a threshold to indicate the percentage of variables to round with our algorithm and which other to round to the nearest integer. Most importantly, our algorithm tackles directly equality constraints without duplicating rows. We select the parameters of our algorithm on the 19 instances provided for the Mip Competition 2022. Finally, we compared our approach to other start heuristics, like Simple Rounding, Rounding, Shifting, and Feasibility Pump on the first 800 MIPLIB2017 instances ordered by the number of non-zeros.