Optimization Online


Improving the Randomization Step in Feasibility Pump

Santanu S. Dey(santanu.dey***at***isye.gatech.edu)
Andres Iroume(airoume3***at***gatech.edu)
Marco Molinaro(molinaro.marco***at***gmail.edu)
Domenico Salvagnin(dominiqs***at***gmail.com)

Abstract: Feasibility pump (FP) is a successful primal heuristic for mixed-integer linear programs (MILP). The algorithm consists of three main components: rounding fractional solution to a mixed-integer one, projection of infeasible solutions to the LP relaxation, and a randomization step used when the algorithm stalls. While many generalizations and improvements to the original Feasibility Pump have been proposed, they mainly focus on the rounding and projection steps. We start a more in-depth study of the randomization step in Feasibility Pump. For that, we propose a new randomization step based on the WalkSAT algorithm for solving SAT instances. First, we provide theoretical analyses that show the potential of this randomization step; to the best of our knowledge, this is the first time any theoretical analysis of running-time of Feasibility Pump or its variants has been conducted. Moreover, we also conduct computational experiments incorporating the proposed modification into a state-of-the-art Feasibility Pump code that reinforce the practical value of the new randomization step.

Keywords: Feasibility Pump, Randomization, Integer programming, Two-stage stochastic integer programs

Category 1: Integer Programming (0-1 Programming )

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 09/26/2016
Entry Accepted: 09/26/2016
Entry Last Modified: 09/26/2016

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