FEASPUMP

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

Showing results 101 to 120 of 121.
Sorted by year (citations)
  1. Joncour, C.; Michel, S.; Sadykov, R.; Sverdlov, D.; Vanderbeck, F.: Column generation based primal heuristics (2010)
  2. Nannicini, Giacomo: Point-to-point shortest paths on dynamic time-dependent road networks (2010)
  3. Richard, Jean-Philippe P.; Dey, Santanu S.: The group-theoretic approach in mixed integer programming (2010)
  4. Wallace, Chris: ZI round, a MIP rounding heuristic (2010)
  5. Achterberg, Tobias: SCIP: solving constraint integer programs (2009)
  6. Akartunalı, Kerem; Miller, Andrew J.: A heuristic approach for big bucket multi-level production planning problems (2009)
  7. Bonami, Pierre; CornuƩjols, GƩrard; Lodi, Andrea; Margot, FranƧois: A feasibility pump for mixed integer nonlinear programs (2009)
  8. Fischetti, Matteo; Salvagnin, Domenico: Feasibility pump 2.0 (2009)
  9. Laundy, Richard; Perregaard, Michael; Tavares, Gabriel; Tipi, Horia; Vazacopoulos, Alkis: Solving hard mixed-integer programming problems with Xpress-MP: a MIPLIB 2003 case study (2009)
  10. Poojari, C. A.; Beasley, J. E.: Improving Benders decomposition using a genetic algorithm (2009)
  11. Berthold, Timo: Heuristics of the branch-cut-and-price-framework SCIP (2008)
  12. Chinneck, John W.: Feasibility and infeasibility in optimization. Algorithms and computational methods. (2008)
  13. Dash, Sanjeeb; GĆ¼nlĆ¼k, Oktay: On the strength of Gomory mixed-integer cuts as group cuts (2008)
  14. Fischetti, Matteo; Lodi, Andrea: Repairing MIP infeasibility through local branching (2008)
  15. Raidl, GĆ¼nther R.; Puchinger, Jakob: Combining (integer) linear programming techniques and metaheuristics for combinatorial optimization (2008)
  16. Achterberg, Tobias; Berthold, Timo: Improving the feasibility pump (2007)
  17. Bertacco, Livio; Fischetti, Matteo; Lodi, Andrea: A feasibility pump heuristic for general mixed-integer problems (2007)
  18. Patel, Jagat; Chinneck, John W.: Active-constraint variable ordering for faster feasibility of mixed integer linear programs (2007)
  19. AtamtĆ¼rk, Alper; Savelsbergh, Martin W. P.: Integer-programming software systems (2005)
  20. Fischetti, Matteo; Glover, Fred; Lodi, Andrea: The feasibility pump (2005)