Improving the randomization step in feasibility pump

DOI10.1137/16M1095962MaRDI QIDQ4603044zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

integer programmingfeasibility pumpprimal heuristic

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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

Describes a project that uses

Uses Software

• FEASPUMP
• CPLEX
• MIPLIB

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)