Feasibility Pump-like heuristics for mixed integer problems

Finding a feasible solution to a MIP problem is a tough task that has received much attention in the last decades. The Feasibility Pump (FP) is a heuristic for finding feasible solutions to MIP problems that has encountered a lot of success as it is very efficient also when dealing with very difficult instances. In this work, we show that the FP heuristic for general MIP problems can be seen as the Frank–Wolfe method applied to a concave nonsmooth problem. Starting from this equivalence, we propose concave non-differentiable penalty functions for measuring solution integrality that can be integrated in the FP approach.