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 enhancing 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.

hdl.handle.net/1765/131545
Mathematical Programming Computation
Decision and Information Sciences

Boland, N., Eberhard, A, Engineer, F, Fischetti, M., Saverlsberg, M, & Tsoukalas, A.T. (2014). Boosting the feasibility pump. Mathematical Programming Computation, 6, 255–279. Retrieved from http://hdl.handle.net/1765/131545