Feasibility pump 2.0. Finding a feasible solution of a given mixed-integer programming (MIP) model is a very important 𝒩𝒫-complete problem that can be extremely hard in practice. Feasibility Pump (FP) is a heuristic scheme for finding a feasible solution to general MIPs that can be viewed as a clever way to round a sequence of fractional solutions of the LP relaxation, until a feasible one is eventually found. In this paper we study the effect of replacing the original rounding function (which is fast and simple, but somehow blind) with more clever rounding heuristics. In particular, we investigate the use of a diving-like procedure based on rounding and constraint propagation-a basic tool in Constraint Programming. Extensive computational results on binary and general integer MIPs from the literature show that the new approach produces a substantial improvement of the FP success rate, without slowing-down the method and with a significantly better quality of the feasible solutions found.

References in zbMATH (referenced in 107 articles )

Showing results 1 to 20 of 107.
Sorted by year (citations)

1 2 3 4 5 6 next

  1. Carvalho, Iago A.: On the statistical evaluation of algorithmic’s computational experimentation with infeasible solutions (2019)
  2. Berthold, Timo: A computational study of primal heuristics inside an MI(NL)P solver (2018)
  3. Berthold, Timo; Perregaard, Michael; Mészáros, Csaba: Four good reasons to use an interior point solver within a MIP solver (2018)
  4. Borwein, Jonathan M.; Giladi, Ohad: Convex analysis in groups and semigroups: a sampler (2018)
  5. Cafieri, Sonia; D’Ambrosio, Claudia: Feasibility pump for aircraft deconfliction with speed regulation (2018)
  6. Dey, Santanu S.; Iroume, Andres; Molinaro, Marco; Salvagnin, Domenico: Improving the randomization step in feasibility pump (2018)
  7. Hill, Alessandro; Voß, Stefan: Generalized local branching heuristics and the capacitated ring tree problem (2018)
  8. Hiller, Benjamin; Koch, Thorsten; Schewe, Lars; Schwarz, Robert; Schweiger, Jonas: A system to evaluate gas network capacities: concepts and implementation (2018)
  9. Kang, Yongha; Albey, Erinc; Uzsoy, Reha: Rounding heuristics for multiple product dynamic lot-sizing in the presence of queueing behavior (2018)
  10. Kılınç, Mustafa R.; Sahinidis, Nikolaos V.: Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON (2018)
  11. Melo, Wendel; Fampa, Marcia; Raupp, Fernanda: Integrality gap minimization heuristics for binary mixed integer nonlinear programming (2018)
  12. Munguía, Lluís-Miquel; Ahmed, Shabbir; Bader, David A.; Nemhauser, George L.; Shao, Yufen: Alternating criteria search: a parallel large neighborhood search algorithm for mixed integer programs (2018)
  13. Rocha, Ana Maria A. C. (ed.); Costa, M. Fernanda P. (ed.); Fernandes, Edite M. G. P. (ed.): Preface to the special issue “GOW’16” (2018)
  14. Schäfer, Lukas; García, Sergio; Mitschke, Andreas; Srithammavanh, Vassili: Redundancy system design for an aircraft door management system (2018)
  15. Soylu, Banu: The search-and-remove algorithm for biobjective mixed-integer linear programming problems (2018)
  16. Wu, Tao; Xiao, Fan; Zhang, Canrong; He, Yan; Liang, Zhe: The green capacitated multi-item lot sizing problem with parallel machines (2018)
  17. Adamo, Tommaso; Ghiani, Gianpaolo; Grieco, Antonio; Guerriero, Emanuela; Manni, Emanuele: MIP neighborhood synthesis through semantic feature extraction and automatic algorithm configuration (2017)
  18. Andrade, Carlos E.; Ahmed, Shabbir; Nemhauser, George L.; Shao, Yufen: A hybrid primal heuristic for finding feasible solutions to mixed integer programs (2017)
  19. Arts, Joachim: A multi-item approach to repairable stocking and expediting in a fluctuating demand environment (2017)
  20. Belotti, Pietro; Berthold, Timo: Three ideas for a feasibility pump for nonconvex MINLP (2017)

1 2 3 4 5 6 next