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.