A feasibility pump heuristic for general mixed-integer problems

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. Very recently, Fischetti, Glover and Lodi proposed a heuristic scheme for finding a feasible Solution to general MIPs, called a Feasibility, Pump (FP). According to the computational analysis reported by these authors, FP is indeed quite effective in finding feasible solutions of hard 0-1 MIPs. However, MIPs with general-integer variables seem much more difficult to solve by using the FP approach. In this paper we elaborate on the Fischetti-Glover-Lodi approach and extend it in two main directions, namely (i) handling as effectively as possible MIP problems with both binary and general-integer variables, and (ii) exploiting the FP information to drive a Subsequent enumeration phase. Extensive computational results on large sets of test instances from the literature are reported, showing the effectiveness of our improved FP scheme for finding feasible solutions to hard MIPs with general-integer variables. (c) 2006 Elsevier B.V. All rights reserved.