Improving the Randomization Step in Feasibility Pump
Santanu Subhas Dey, Andres Iroume, Marco Molinaro, Domenico Salvagnin · SIAM Journal on Optimization · 2018
Feasibility pump is a successful primal heuristic for mixed-integer linear programs. The algorithm consists of three main components: rounding fractional solution to a mixed-integer one, projection of infeasible solutions to the linear programming relaxation, and a randomization step used when the algorithm stalls. While many generalizations and improvements to the original Feasibility Pump have been proposed, they mainly focus on the rounding and projection steps. We start a more in-depth study of the randomization step in Feasibility Pump. For that, we propose a new randomization step based on the WalkSAT algorithm for solving instances of the Boolean satisfiability problem. First, we provide theoretical analyses for instances with disjoint equality constraints that show the potential of this randomization step; to the best of our knowledge, this is the first time any theoretical analysis of the running-time of Feasibility Pump or its variants has been conducted, even for a special class of instances. Moreover, we propose a practical version of a new randomization step, and incorporate it into a state-of-the-art Feasibility Pump code. Our experiments suggests that this simple-to-implement modification consistently dominates the standard randomization previously used.