Improving the randomization step in feasibility pump

DOI10.1137/16M1095962zbMATH Open1391.90426arXiv1609.08121OpenAlexW2964040514MaRDI QIDQ4603044FDOQ4603044

Authors: Andres Iroume, Marco Molinaro, Domenico Salvagnin, Santanu S. Dey 

Publication date: 14 February 2018

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1609.08121

Recommendations

• Improving the feasibility pump
• A New Approach to the Feasibility Pump in Mixed Integer Programming
• A feasibility pump heuristic for general mixed-integer problems
• An empirical evaluation of walk-and-round heuristics for mixed integer linear programs
• Feasibility pump 2.0

zbMATH Keywords

integer programmingfeasibility pumpprimal heuristic

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Mixed integer programming (90C11)

Cites Work

• Title not available (Why is that?)
• A feasibility pump for mixed integer nonlinear programs
• Feasibility pump 2.0
• A storm of feasibility pumps for nonconvex MINLP
• Conflict analysis in mixed integer programming
• A feasibility pump heuristic for general mixed-integer problems
• Improving the feasibility pump
• The feasibility pump
• A new class of functions for measuring solution integrality in the feasibility pump approach
• A New Approach to the Feasibility Pump in Mixed Integer Programming
• Title not available (Why is that?)
• Probability and Computing
• Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems
• Boosting the feasibility pump
• Penalty alternating direction methods for mixed-integer optimization: a new view on feasibility pumps
• Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs

Cited In (5)

• Ten years of feasibility pump, and counting
• Penalty alternating direction methods for mixed-integer optimization: a new view on feasibility pumps
• Using multiple reference vectors and objective scaling in the feasibility pump
• Structure-driven fix-and-propagate heuristics for mixed integer programming
• Feasibility pump algorithm for sparse representation under Laplacian noise

Uses Software

• MIPLIB
• CPLEX
• FEASPUMP

This page was built for publication: Improving the randomization step in feasibility pump

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603044)