Improving the Feasibility Pump
Appeared in: Discrete Optimization 4 (2007) 77-86
| 05-42 | Tobias Achterberg, Timo Berthold
Improving the Feasibility Pump Appeared in: Discrete Optimization 4 (2007) 77-86 | |
Abstract: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.
Keywords: mixed integer programming,
primal heuristics,
feasibility pump
MSC: 90C11, 90-08