×

Ten years of feasibility pump, and counting. (English) Zbl 1430.90429

Summary: The feasibility pump (fp) is probably the best-known primal heuristic for mixed-integer programming. The original work by M. Fischetti et al. [Math. Program. 104, No. 1 (A), 91–104 (2005; Zbl 1077.90039)], which introduced the heuristic for 0-1 mixed-integer linear programs, has been succeeded by more than twenty follow-up publications which improve the performance of the fp and extend it to other problem classes. Year 2015 was the tenth anniversary of the first fp publication. The present paper provides an overview of the diverse feasibility pump literature that has been presented over the last decade.

MSC:

90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming

Citations:

Zbl 1077.90039

Software:

FPBH.jl; FEASPUMP; Bonmin
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achterberg T (2010) LP basis selection and cutting planes. Presentation slides from MIP 2010 workshop in Atlanta. https://www.isye.gatech.edu/news-events/events/past-conferences/2010-mixed-integer-programming-workshop
[2] Achterberg T (2011) LP relaxation modification and cut selection in a MIP solver. US Patent, US20110131167
[3] Achterberg T, Berthold T (2007) Improving the feasibility pump. Discrete Optim Spec Issue 4(1):77-86 · Zbl 1170.90443 · doi:10.1016/j.disopt.2006.10.004
[4] Baena D, Castro J (2011) Using the analytic center in the feasibility pump. Oper Res Lett 39(5):310-317 · Zbl 1235.90098 · doi:10.1016/j.orl.2011.07.005
[5] Belotti P, Berthold T (2016) Three ideas for a feasibility pump for nonconvex MINLP. Optim Lett 11(1):3-15 · Zbl 1373.90080 · doi:10.1007/s11590-016-1046-0
[6] Bertacco L, Fischetti M, Lodi A (2007) A feasibility pump heuristic for general mixed-integer problems. Discrete Optim Spec Issue 4(1):63-76 · Zbl 1169.90415 · doi:10.1016/j.disopt.2006.10.001
[7] Berthold, T.; Salvagnin, D.; Gomes, C. (ed.); Sellmann, M. (ed.), Cloud branching, No. 7874, 28-43 (2013), Berlin · Zbl 1382.90059 · doi:10.1007/978-3-642-38171-3_3
[8] Boland NL, Eberhard AC, Engineer FG, Fischetti M, Savelsbergh MWP, Tsoukalas A (2014) Boosting the feasibility pump. Math Program Comput 6(3):255-279 · Zbl 1323.65065 · doi:10.1007/s12532-014-0068-9
[9] Boland NL, Eberhard AC, Engineer FG, Tsoukalas A (2012) A new approach to the feasibility pump in mixed integer programming. SIAM J Optim 22(3):831-861 · Zbl 1277.90077 · doi:10.1137/110823596
[10] Bonami P, Biegler LT, Conn AR, Cornuéjols G, Grossmann IE, Laird CD, Lee J, Lodi A, Margot F, Sawaya N, Wächter A (2008) An algorithmic framework for convex mixed integer nonlinear programs. Discrete Optim 5:186-204 · Zbl 1151.90028 · doi:10.1016/j.disopt.2006.10.011
[11] Bonami P, Cornuéjols G, Lodi A, Margot F (2009) A feasibility pump for mixed integer nonlinear programs. Math Program 119(2):331-352 · Zbl 1163.90013 · doi:10.1007/s10107-008-0212-2
[12] Bonami P, Gonçalves J (2012) Heuristics for convex mixed integer nonlinear programs. Comput Optim Appl 51:729-747 · Zbl 1241.90189 · doi:10.1007/s10589-010-9350-6
[13] Bosco A, Laganà D, Musmanno R, Vocaturo F (2013) Modeling and solving the mixed capacitated general routing problem. Optim Lett 7(7):1451-1469 · Zbl 1280.90008 · doi:10.1007/s11590-012-0552-y
[14] Brearley A, Mitra G, Williams H (1975) Analysis of mathematical programming problems prior to applying the simplex algorithm. Math Program 8:54-83 · Zbl 0317.90037 · doi:10.1007/BF01580428
[15] Cafieri S, D’Ambrosio C (2017) Feasibility pump for aircraft deconfliction with speed regulation. J Glob Optim 71(3):501-515 · Zbl 1402.90093 · doi:10.1007/s10898-017-0560-7
[16] D’Ambrosio C (2009) Application-oriented mixed integer non-linear programming. Ph.D. Thesis, University of Bologna
[17] D’Ambrosio, C.; Frangioni, A.; Liberti, L.; Lodi, A.; Festa, P. (ed.), Experiments with a feasibility pump approach for nonconvex MINLPs, No. 6049, 350-360 (2010), Berlin Heidelberg
[18] D’Ambrosio C, Frangioni A, Liberti L, Lodi A (2012) A storm of feasibility pumps for nonconvex MINLP. Math Program 136:375-402 · Zbl 1257.90056 · doi:10.1007/s10107-012-0608-x
[19] De Santis M, Lucidi S, Rinaldi F (2013) A new class of functions for measuring solution integrality in the feasibility pump approach. SIAM J Optim 23(3):1575-1606 · Zbl 1282.90099 · doi:10.1137/110855351
[20] De Santis M, Lucidi S, Rinaldi F (2014) Feasibility pump-like heuristics for mixed integer problems. Discrete Appl Math 165:152-167 · Zbl 1471.90098 · doi:10.1016/j.dam.2013.06.018
[21] Dey S (2017) Personal communication
[22] Dey S, Iroume A, Molinaro M, Salvagnin D. Exploiting sparsity of MILPs by improving the randomization step in feasibility pump. SIAM J Optim (to appear) · Zbl 1391.90426
[23] Duran MA, Grossmann IE (1986) An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math Program 36(3):307-339 · Zbl 0619.90052 · doi:10.1007/BF02592064
[24] Eckstein J, Nediak M (2007) Pivot, cut, and dive: a heuristic for 0-1 mixed integer programming. J Heuristics 13(5):471-503 · doi:10.1007/s10732-007-9021-7
[25] Fischetti M, Glover F, Lodi A (2005) The feasibility pump. Math Program 104(1):91-104 · Zbl 1077.90039 · doi:10.1007/s10107-004-0570-3
[26] Fischetti M, Lodi A (2003) Local branching. Math Program 98(1-3):23-47 · Zbl 1060.90056 · doi:10.1007/s10107-003-0395-5
[27] Fischetti M, Lodi A (2008) Repairing MIP infeasibility through local branching. Comput Oper Res 35(5):1436-1445 · Zbl 1278.90273 · doi:10.1016/j.cor.2006.08.004
[28] Fischetti M, Monaci M (2014) Proximity search for 0-1 mixed-integer convex programming. J Heuristics 20(6):709-731 · Zbl 1360.90173 · doi:10.1007/s10732-014-9266-x
[29] Fischetti M, Salvagnin D (2009) Feasibility pump 2.0. Math Program Comput 1:201-222 · Zbl 1180.90208 · doi:10.1007/s12532-009-0007-3
[30] Frank M, Wolfe P (1956) An algorithm for quadratic programming. Naval Res Logist Q 3(1-2):95-110 · doi:10.1002/nav.3800030109
[31] Geißler B, Morsi A, Schewe L, Schmidt M (2017) Penalty alternating direction methods for mixed-integer optimization: a new view on feasibility pumps. SIAM J Optim 27:1611-1636 · Zbl 1371.65051 · doi:10.1137/16M1069687
[32] Guyon O, Lemaire P, Pinson E, Rivreau D (2009) Near optimal and optimal solutions for an integrated employee timetabling and production scheduling problem. IFAC Proc Vol 42(4):1523-1528 · doi:10.3182/20090603-3-RU-2001.0190
[33] Hanafi S, Lazić J, Mladenović N (2010) Variable neighbourhood pump heuristic for 0-1 mixed integer programming feasibility. Electron Notes Discrete Math 36:759-766 · Zbl 1237.90161 · doi:10.1016/j.endm.2010.05.096
[34] Li M, Liu Q (2017) Inexact feasibility pump for mixed integer nonlinear programming. Inf Process Lett 118:110-116 · Zbl 1402.90099 · doi:10.1016/j.ipl.2016.10.009
[35] Misener R, Floudas CA (2012) Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations. Math Program 136(1):155-182 · Zbl 1257.90079 · doi:10.1007/s10107-012-0555-6
[36] Naoum-Sawaya J (2013) Recursive central rounding for mixed integer programs. Comput Oper Res 43:191-200 · Zbl 1348.90493 · doi:10.1016/j.cor.2013.09.008
[37] Pal A, Charkhgard H (2017) A feasibility pump and local search based heuristic for bi-objective pure integer linear programming. Technical Report 5902, Optimization Online · Zbl 1528.90251
[38] Perregaard M (2017) How MILP solvers can benefit from Interior Point solutions. Presentation slides from MIP 2017 workshop in Montréal. https://sites.google.com/site/mipworkshop2017/home
[39] Pesneau P, Sadykov R, Vanderbeck F (2012) Feasibility pump heuristics for column generation approaches. In: 11th International symposium on experimental algorithms (SEA 2012), pp 332-343
[40] Requejo C, Santos E (2017) A feasibility pump and a local branching heuristics for the weight-constrained minimum spanning tree problem. In: Gervasi O, Murgante B, Misra S, Borruso G, Torre CM, Rocha AMA, Taniar D, Apduhan BO, Stankova E, Cuzzocrea A (eds) Computational science and its applications—ICCSA 2017: 17th international conference, Trieste, Italy, July 3-6, 2017, Proceedings, Part II, pp 669-683. Springer International Publishing, Cham
[41] Schöning U (1999) A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: FOCS: IEEE symposium on foundations of computer science (FOCS)
[42] Sharma S (2013) Mixed-integer nonlinear programming heuristics applied to a shale gas production optimization problem. Master’s Thesis. Norwegian University of Science and Technology
[43] Sharma S, Knudsen BR, Grimstad B (2014) Towards an objective feasibility pump for convex MINLPs. Comput Optim Appl 63(3):737-753 · Zbl 1343.90053 · doi:10.1007/s10589-015-9792-y
[44] Sonnevend, G.; Prékopa, A. (ed.); Szelezsáan, J. (ed.); Strazicky, B. (ed.), An “analytical centre” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, No. 84, 866-875 (1986), Berlin · Zbl 0602.90106
[45] Vigerske S (2013) Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear programming. Ph.D. Thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.