Optimization Online


Boosting the Feasibility Pump

Natashia L. Boland(natashia.boland***at***newcastle.edu.au)
Andrew C. Eberhard(andy.eb***at***rmit.edu.au)
Faramroze G. Engineer(Faramroze.Engineer***at***newcastle.edu.au)
Matteo Fischetti(m.fischetti***at***gmail.com)
Martin W. P. Savelsbergh(martin.savelsbergh***at***newcastle.edu.au)
Angelos Tsoukalas(maurostsouk***at***googlemail.com)

Abstract: 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.

Keywords: integer programming, primal heuristic, feasible solution, projection method, line search

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Report C-OPT 2012-03, The University of Newcastle, Callaghan, NSW, 2308, Australia, 2012

Download: [PDF]

Entry Submitted: 01/22/2012
Entry Accepted: 01/22/2012
Entry Last Modified: 01/22/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society