FEASPUMP 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: CPLEX; MIPLIB; MIPLIB2003; SCIP; Bonmin; Ipopt; MINLPLib; Octane; Gurobi; AMPL; LINDO; Benchmarks for Optimization Software; GAMS; COIN-OR; FilMINT; DICOPT; BARON; AlphaECP; XPRESS; SoPlex Cited in: 132 Publications all top 5 Cited by 244 Authors 11 Berthold, Timo 9 Lodi, Andrea 8 Fischetti, Matteo 6 Salvagnin, Domenico 5 Kronqvist, Jan 4 Chinneck, John W. 4 D’Ambrosio, Claudia 4 Hanafi, Saïd 4 Nemhauser, George L. 4 Savelsbergh, Martin W. P. 4 Schewe, Lars 4 Stein, Oliver 3 Bernal, David E. 3 Bonami, Pierre 3 De Santis, Marianna 3 Grossmann, Ignacio E. 3 Liberti, Leo 3 Mehrotra, Sanjay 3 Mladenović, Nenad 3 Nannicini, Giacomo 3 Neumann, Christoph 3 Rinaldi, Francesco 3 Schmidt, Martin 3 Todosijević, Raca 2 Achterberg, Tobias 2 Ahmed, Shabbir 2 Baena, Daniel 2 Belotti, Pietro 2 Boland, Natashia L. 2 Castro, Jordi 2 Charkhgard, Hadi 2 Dash, Sanjeeb 2 Dey, Santanu Subhas 2 Eberhard, Andrew C. 2 Engineer, Faramroze G. 2 Glover, Fred W. 2 Günlük, Oktay 2 Hendel, Gregor 2 Huang, Kuo-Ling 2 Joncour, Cédric 2 Kılınç, Mustafa R. 2 Linderoth, Jeff T. 2 Lucidi, Stefano 2 Lundell, Andreas 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 Adamo, Tommaso 1 Agra, Agostinho 1 Akartunalı, Kerem 1 Albey, Erinc 1 Almada-Lobo, Bernardo 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 Cataldo, Alejandro 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 Dumitrescu, Bogdan Alexandru 1 Dupin, Nicolas 1 Elhedhli, Samir 1 Ergun, Ozlem 1 Eronen, Ville-Pekka 1 Fampa, Marcia Helena C. 1 Fernandes, Edite M. G. P. 1 Floudas, Christodoulos Achilleus 1 Frangioni, Antonio 1 Fügenschuh, Armin R. ...and 144 more Authors all top 5 Cited in 27 Serials 20 Computers & Operations Research 14 European Journal of Operational Research 12 Mathematical Programming Computation 10 Journal of Global Optimization 8 Computational Optimization and Applications 7 Mathematical Programming. Series A. Series B 5 SIAM Journal on Optimization 5 INFORMS Journal on Computing 5 EURO Journal on Computational Optimization 4 Journal of Heuristics 3 Discrete Applied Mathematics 3 Journal of Optimization Theory and Applications 3 Operations Research Letters 3 Discrete Optimization 3 Optimization Letters 2 Information Processing Letters 2 Annals of Operations Research 2 Optimization Methods & Software 2 Optimization and Engineering 2 4OR 1 International Journal of Control 1 Bulletin of Mathematical Biology 1 Applied Mathematics and Computation 1 Top 1 Mathematical Problems in Engineering 1 Mathematical Methods of Operations Research 1 International Series in Operations Research & Management Science all top 5 Cited in 13 Fields 130 Operations research, mathematical programming (90-XX) 7 Numerical analysis (65-XX) 5 Computer science (68-XX) 3 Calculus of variations and optimal control; optimization (49-XX) 3 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 2 Statistics (62-XX) 1 General and overarching topics; collections (00-XX) 1 Combinatorics (05-XX) 1 Partial differential equations (35-XX) 1 Functional analysis (46-XX) 1 Convex and discrete geometry (52-XX) 1 Biology and other natural sciences (92-XX) 1 Information and communication theory, circuits (94-XX) Citations by Year