MPC

Mathematical Programming Computation, Volume 6, Issue 3, September 2014

Boosting the feasibility pump

Natashia L. Boland, Andrew C. Eberhard, Faramroze G. Engineer, Matteo Fischetti, Martin W. P. Savelsbergh, Angelos Tsoukalas

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 infeasible solutions. The process attempts to minimize 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.

Full Text: PDF




Imprint and privacy statement

For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2020 by Zuse Institute Berlin (ZIB).