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 63 articles )

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

1 2 3 4 next

  1. Fischetti, Matteo; Lodi, Andrea; Monaci, Michele; Salvagnin, Domenico; Tramontani, Andrea: Improving branch-and-cut performance by random sampling (2016)
  2. Sharma, Shaurya; Knudsen, Brage Rugstad; Grimstad, Bjarne: Towards an objective feasibility pump for convex minlps (2016)
  3. Huang, Kuo-Ling; Mehrotra, Sanjay: An empirical evaluation of a walk-relax-round heuristic for mixed integer convex programs (2015)
  4. Humpola, Jesco; FĆ¼genschuh, Armin; Lehmann, Thomas: A primal heuristic for optimizing the topology of gas networks based on dual information (2015)
  5. Kirst, Peter; Stein, Oliver; Steuermann, Paul: Deterministic upper bounds for spatial branch-and-bound methods in global minimization with nonconvex constraints (2015)
  6. Obuchowska, Wiesława T.: Irreducible infeasible sets in convex mixed-integer programs (2015)
  7. Agra, Agostinho; Christiansen, Marielle; Delgado, Alexandrino; Simonetti, Luidi: Hybrid heuristics for a short sea inventory routing problem (2014)
  8. Berthold, Timo: RENS. The optimal rounding (2014)
  9. Berthold, Timo; Gleixner, Ambros M.: Undercover: a primal MINLP heuristic exploring a largest sub-MIP (2014)
  10. Boland, Natashia; Eberhard, Andrew; Engineer, Faramroze; Fischetti, Matteo; Savelsbergh, Martin; Tsoukalas, Angelos: Boosting the feasibility pump (2014)
  11. Camargo, Victor C.B.; Toledo, Franklina M.B.; Almada-Lobo, Bernardo: HOPS -- Hamming-Oriented Partition Search for production planning in the spinning industry (2014)
  12. De Santis, M.; Lucidi, S.; Rinaldi, F.: Feasibility Pump-like heuristics for mixed integer problems (2014)
  13. Hamzeei, Mahdi; Luedtke, James: Linearization-based algorithms for mixed-integer nonlinear programs with convex continuous relaxation (2014)
  14. Berthold, Timo; Salvagnin, Domenico: Cloud branching (2013)
  15. Bosco, Adamo; LaganĆ , Demetrio; Musmanno, Roberto; Vocaturo, Francesca: Modeling and solving the mixed capacitated general routing problem (2013)
  16. Dā€™ambrosio, Claudia; Lodi, Andrea: Mixed integer nonlinear programming tools: an updated practical overview (2013)
  17. Guzelsoy, Menal; Nemhauser, George; Savelsbergh, Martin: Restrict-and-relax search for 0-1 mixed-integer programs (2013)
  18. Huang, Kuo-Ling; Mehrotra, Sanjay: An empirical evaluation of walk-and-round heuristics for mixed integer linear programs (2013)
  19. Li, Min; Vicente, LuĆ­s Nunes: Inexact solution of NLP subproblems in MINLP (2013)
  20. Bonami, Pierre; GonƧalves, JoĆ£o P.M.: Heuristics for convex mixed integer nonlinear programs (2012)

1 2 3 4 next