Feasibility Pump Revised Matteo Fischetti(1) and Domenico Salvagnin(2) (1) DEI, University of Padova, Italy (2) DMPA, University of Padova, Italy e-mail: matteo.fischetti@unipd.it, salvagni@math.unipd.it May 22, 2008 Finding a feasible solution of a given Mixed-Integer Programming (MIP) model is a very important (NP-complete) problem that can be extremely hard in practice. The so-called Feasibility Pump (FP) is heuristic scheme for finding a feasible solution to general MIPs recently proposed by Fischetti, Glover, and Lodi [3] and further improved by Fischetti, Bertacco and Lodi [2] and Achterberg and Berthold [1]. From a geometric point of view, starting from a fractional point which is usually the LP relaxation of the original MIP problem, the FP generates two (hopefully convergent) trajectories of points x* and ~x that satisfy feasibility in a complementary way: points x* satisfy the LP constraints, but may be integer-infeasible, whereas points ~x satisfy the integrality constraint, but may be LP-infeasible. The two sequences are obtained as follows: at each iteration, the new fractional point x* is obtained as a point of the LP relaxation that minimizes (a linearization of) the Hamming distance from the previous integer point ~x, while the new integer point ~x is obtained from the fractional one by simply rounding its components to the nearest integer. Some care must be taken in order to avoid cycling, usually through random perturbations. The FP heuristic turns out to be quite successful in finding feasible solutions even for very hard MIP instances, and is currently implemented in many optimization solvers, both commercial and open source. In this paper we study the effect of substituting the original rounding function (which is fast and simple, but very blind) with more clever rounding heuristics. In particular we investigate the use of a diving-like procedure based on rounding and constraint propagation. Preliminary computational results show that this is a promising direction for improving both the FP convergence rate and the quality of the feasible solutions found.