Optimization Online


A New Approach to the Feasibility Pump in Mixed Integer Programming

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)
Angelos Tsoukalas (maurostsouk***at***googlemail.com)

Abstract: The feasibility pump is a recent, highly successful heuristic for general mixed integer linear programming problems. We show that the feasibility pump heuristic can be interpreted as a discrete version of the proximal point algorithm. In doing so, we extend and generalize some of the fundamental results in this area to provide new supporting theory. We show that feasibility pump algorithms implicitly minimizes a weighted combination of the objective and a term which penalizes lack of integrality. This function has many local minima, some of which correspond to feasible integral solutions; the feasibility pump´┐Żs use of random restarts can be viewed as seeking to escape these local minima when they are not feasible integral solutions. This interpretation suggests alternative ways of incorporating restarts, one of which is the application of cutting planes. Numerical experiments with cutting planes show encouraging results on standard test libraries.

Keywords: integer programming, primal heuristic, feasible solution, cutting planes

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

Citation: Boland N., Eberhard A., Faram E. and Tsoukalas A. (2012), A New Approach to the Feasibility Pump in Mixed Integer Programming, SIAM J. Optim., Vol. 22 no. 3, pp 831-861

Download: [PDF]

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

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