Improving the Feasibility Pump

Please always quote using this URN: urn:nbn:de:0297-zib-8754
  • The Feasibility Pump of Fischetti, Glover, Lodi, and Bertacco has proved to be a very successful heuristic for finding feasible solutions of mixed integer programs. The quality of the solutions in terms of the objective value, however, tends to be poor. This paper proposes a slight modification of the algorithm in order to find better solutions. Extensive computational results show the success of this variant: in 89 out of 121 MIP instances the modified version produces improved solutions in comparison to the original Feasibility Pump.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Tobias Achterberg, Timo Berthold
Document Type:ZIB-Report
Tag:feasibility pump; mixed integer programming; primal heuristics
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-08 Computational methods
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
Date of first Publication:2005/09/16
Series (Serial Number):ZIB-Report (05-42)
Published in:Appeared in: Discrete Optimization 4 (2007) 77-86