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

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

1 2 3 ... 5 6 7 next

  1. Chen, Qi; Johnson, Emma S.; Bernal, David E.; Valentin, Romeo; Kale, Sunjeev; Bates, Johnny; Siirola, John D.; Grossmann, Ignacio E.: Pyomo.GDP: an ecosystem for logic based modeling and optimization development (2022)
  2. Lundell, Andreas; Kronqvist, Jan: Polyhedral approximation strategies for nonconvex mixed-integer nonlinear programming in SHOT (2022)
  3. Todosijević, Raca; Hanafi, SaĆÆd; Glover, Fred: On convergence of scatter search and star paths with directional rounding for 0--1 mixed integer programs (2022)
  4. AssunĆ§Ć£o, Lucas; Mateus, Geraldo Robson: Coupling feasibility pump and large neighborhood search to solve the Steiner team orienteering problem (2021)
  5. Furman, Kevin C.; Grossmann, Ignacio E.: A biographical review of the research and impacts of Marco Duran (2021)
  6. Kronqvist, Jan; Misener, Ruth: A disjunctive cut strengthening technique for convex MINLP (2021)
  7. Neumann, Christoph; Stein, Oliver: Generating feasible points for mixed-integer convex optimization problems by inner parallel cuts (2021)
  8. Wolsey, Laurence A.: Integer programming (2021)
  9. Androutsopoulos, Konstantinos N.; Manousakis, Eleftherios G.; Madas, Michael A.: Modeling and solving a bi-objective airport slot scheduling problem (2020)
  10. Bernal, David E.; Vigerske, Stefan; Trespalacios, Francisco; Grossmann, Ignacio E.: Improving the performance of DICOPT in convex MINLP problems using a feasibility pump (2020)
  11. De Mauri, Massimo; Gillis, Joris; Swevers, Jan; Pipeleers, Goele: A proximal-point outer approximation algorithm (2020)
  12. GrĆ¼bel, Julia; Kleinert, Thomas; Krebs, Vanessa; Orlinskaya, Galina; Schewe, Lars; Schmidt, Martin; ThĆ¼rauf, Johannes: On electricity market equilibria with storage: modeling, uniqueness, and a distributed ADMM (2020)
  13. Neumann, Christoph; Stein, Oliver; Sudermann-Merx, Nathan: Granularity in nonlinear mixed-integer optimization (2020)
  14. Takapoui, Reza; Moehle, Nicholas; Boyd, Stephen; Bemporad, Alberto: A simple effective heuristic for embedded mixed-integer quadratic programming (2020)
  15. Berthold, Timo; Lodi, Andrea; Salvagnin, Domenico: Ten years of feasibility pump, and counting (2019)
  16. Carvalho, Iago A.: On the statistical evaluation of algorithmicā€™s computational experimentation with infeasible solutions (2019)
  17. Gamrath, Gerald; Berthold, Timo; Heinz, Stefan; Winkler, Michael: Structure-driven fix-and-propagate heuristics for mixed integer programming (2019)
  18. Gƶttlich, S.; Potschka, A.; Teuber, C.: A partial outer convexification approach to control transmission lines (2019)
  19. Miertoiu, Florin Ilarion; Dumitrescu, Bogdan: Feasibility pump algorithm for sparse representation under Laplacian noise (2019)
  20. Neumann, Christoph; Stein, Oliver; Sudermann-Merx, Nathan: A feasible rounding approach for mixed-integer optimization problems (2019)

1 2 3 ... 5 6 7 next