The Feasibility Pump (FP) has proved to be an effective method for finding feasible solutions to mixed integer programming problems. FP iterates between a rounding procedure and a projection procedure, which together provide a sequence of points alternating between LP feasible but fractional solutions, and integer but LP relaxed infeasible solutions. The process attempts to minimise the distance between consecutive iterates, producing an integer feasible solution when closing the distance between them. We investigate the benefits of en- hancing the rounding procedure with a clever integer line search that efficiently explores a large set of integer points. An extensive computational study on benchmark instances demonstrates the efficacy of the proposed approach.
Citation
Report C-OPT 2012-03, The University of Newcastle, Callaghan, NSW, 2308, Australia, 2012