swMATH ID: 4802
Software Authors: Fischetti, Matteo; Salvagnin, Domenico
Description: 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.
Homepage: http://www.or.deis.unibo.it/research_pages/ORcodes/FP-gen.html
Keywords: mixed-integer programming; primal heuristics; constraint programming; constraint propagation
Related Software: MIPLIB; CPLEX; MIPLIB2003; SCIP; Bonmin; Ipopt; MINLPLib; Octane; Gurobi; AMPL; LINDO; Benchmarks for Optimization Software; GAMS; COIN-OR; SoPlex; DICOPT; FilMINT; BARON; XPRESS; AlphaECP
Cited in: 141 Documents
all top 5

Cited by 263 Authors

12 Berthold, Timo
9 Lodi, Andrea
8 Fischetti, Matteo
7 Salvagnin, Domenico
5 Kronqvist, Jan
5 Stein, Oliver
4 Chinneck, John W.
4 D’Ambrosio, Claudia
4 Grossmann, Ignacio E.
4 Hanafi, SaĂŻd
4 Nemhauser, George L.
4 Neumann, Christoph
4 Savelsbergh, Martin W. P.
4 Schewe, Lars
3 Baena, Daniel
3 Bernal, David E.
3 Bonami, Pierre
3 Castro, Jordi
3 De Santis, Marianna
3 Liberti, Leo
3 Mehrotra, Sanjay
3 Mladenović, Nenad
3 Nannicini, Giacomo
3 Rinaldi, Francesco
3 Schmidt, Martin
3 Todosijević, Raca
2 Achterberg, Tobias
2 Adamo, Tommaso
2 Ahmed, Shabbir
2 Belotti, Pietro
2 Boland, Natashia L.
2 Charkhgard, Hadi
2 Dash, Sanjeeb
2 Dey, Santanu Subhas
2 Eberhard, Andrew C.
2 Engineer, Faramroze G.
2 Ghiani, Gianpaolo
2 Glover, Fred W.
2 Guerriero, Emanuela
2 GĂĽnlĂĽk, Oktay
2 Hendel, Gregor
2 Huang, Kuo-Ling
2 Joncour, CĂ©dric
2 Kılınç, Mustafa R.
2 Li, Min
2 Linderoth, Jeff T.
2 Lucidi, Stefano
2 Lundell, Andreas
2 Manni, Emanuele
2 Misener, Ruth
2 Monaci, Michele
2 Naoum-Sawaya, Joe
2 Pal, Aritra
2 Perregaard, Michael
2 Sadykov, Ruslan
2 Shao, Yufen
2 Soylu, Banu
2 Sudermann-Merx, Nathan
2 Tsoukalas, Angelos
2 Vanderbeck, François
2 Westerlund, Tapio
2 Wolsey, Laurence Alexander
2 Wu, Tao
2 Zhang, Canrong
1 Abhishek, Kumar
1 Agra, Agostinho
1 Akartunalı, Kerem
1 Albey, Erinc
1 Almada-Lobo, Bernardo
1 An, Duleabom
1 Andrade, Carlos E.
1 Androutsopoulos, Konstantinos N.
1 Armentano, VinĂ­cius Amaral
1 Arts, Joachim
1 Assunção, Lucas
1 AtamtĂĽrk, Alper
1 Bader, David A.
1 Bates, Johnny
1 Beasley, John E.
1 Bemporad, Alberto
1 Bertacco, Livio
1 Borwein, Jonathan Michael
1 Bosco, Adamo
1 Boukouvala, Fani
1 Boyd, Stephen Poythress
1 Burke, Edmund Kieran
1 Cafieri, Sonia
1 Camargo, Victor C. B.
1 Camponogara, Eduardo
1 Carr, Robert D.
1 Carvalho, Iago Augusto
1 Cataldo, Alejandro
1 Chen, Qi
1 Christiansen, Marielle
1 Coelho, Leandro C.
1 Cornuéjols, Gérard P.
1 Costa, M. Fernanda P.
1 De Mauri, Massimo
1 Delgado, Alexandrino
1 Di Cairano, Stefano
...and 163 more Authors

Citations by Year