×

zbMATH — the first resource for mathematics

Feasibility Pump-like heuristics for mixed integer problems. (English) Zbl 06292070
Summary: Finding a feasible solution to a MIP problem is a tough task that has received much attention in the last decades. The Feasibility Pump (FP) is a heuristic for finding feasible solutions to MIP problems that has encountered a lot of success as it is very efficient also when dealing with very difficult instances. In this work, we show that the FP heuristic for general MIP problems can be seen as the Frank-Wolfe method applied to a concave nonsmooth problem. Starting from this equivalence, we propose concave non-differentiable penalty functions for measuring solution integrality that can be integrated in the FP approach.

MSC:
90C Mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T.; Berthold, T., Improving the feasibility pump, Discrete Optimization, 4, 77-86, (2007) · Zbl 1170.90443
[2] Achterberg, T.; Koch, T.; Martin, A., Miplib 2003, Operations Research Letters, 34, 361-372, (2006), Problems available at http://miplib.zib.de · Zbl 1133.90300
[3] Baena, D.; Castro, J., Using the analytic center in the feasibility pump, Operations Research Letters, 39, 310-317, (2011) · Zbl 1235.90098
[4] Balas, E.; Schmieta, S.; Wallace, C., Pivot and shifta mixed integer programming heuristic, Discrete Optimization, 1, 1, 3-12, (2004) · Zbl 1087.90052
[5] Bertacco, L.; Fischetti, M.; Lodi, A., A feasibility pump heuristic for general mixed-integer problems, Discrete Optimization, 4, 63-76, (2007) · Zbl 1169.90415
[6] N.L. Boland, A.C. Eberhard, F.G. Engineer, M. Fischetti, M.W.P. Savelsbergh, A. Tsoukalas, Boosting the feasibility pump, Report C-OPT 2012-03, The University of Newcastle, Callaghan, NSW, 2308, Australia, 2012. · Zbl 1323.65065
[7] COR@L, COR@L MIP library, http://coral.ie.lehigh.edu/data-sets/mixed-integer-instances/.
[8] ILOG, Cplex, http://www.ilog.com/products/cplex.
[9] C. D’ambrosio, Application-oriented mixed integer nonlinear programming, Ph.D. Thesis, University of Bologna, 2009.
[10] D’ambrosio, C., Application-oriented mixed integer nonlinear programming, 4OR, 8, 3, 319-322, (2010) · Zbl 1205.90203
[11] Danna, E.; Rothberg, E.; Le Pape, C., Exploring relation induced neighborhoods to improve MIP solution, Mathematical Programming, 102, 1, 71-90, (2005) · Zbl 1131.90036
[12] De Santis, M.; Lucidi, S.; Rinaldi, F., A new class of functions for measuring solution integrality in the feasibility pump approach, SIAM Journal on Optimization, (2013), (in press) · Zbl 1282.90099
[13] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profile, Mathematical Programming, 91, 201-213, (2002) · Zbl 1049.90004
[14] Eckstein, J.; Nediak, M., Pivot, cut, and dive: a heuristic for 0-1 mixed integer programming, Journal of Heuristics, 13, 471-503, (2007)
[15] Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Mathematical Programming, 104, 91-104, (2005) · Zbl 1077.90039
[16] Fischetti, M.; Lodi, A., Local branching, Mathematical Programming, 98, 1-3, 23-47, (2003) · Zbl 1060.90056
[17] Fischetti, M.; Salvagnin, D., Feasibility pump 2.0, Mathematical Programming Computation, 1, 201-222, (2009) · Zbl 1180.90208
[18] Glover, F.; Laguna, M., General purpose heuristics for integer programming part I, Journal of Heuristics, 3, (1997) · Zbl 0887.90123
[19] Glover, F.; Laguna, M., General purpose heuristics for integer programming part II, Journal of Heuristics, 3, (1997) · Zbl 0898.90094
[20] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Academic Publisher Boston, Dordrecht, London · Zbl 0930.90083
[21] Glover, F.; Løkketangen, A.; Woodruff, D. L., Scatter search to generate diverse MIP solutions, (Laguna, M.; Gonzàlez-Velarde, J., OR Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, (2000), Kluwer Academic Publishers), 299-317
[22] Hillier, F. S., Efficient heuristic procedures for integer linear programming with an interior, Operations Research, 17, 600-637, (1969) · Zbl 0176.49902
[23] Hillier, F. S.; Saltzman, R. M., A heuristic ceiling point algorithm for general integer linear programming, Management Science, 38, 2, 263-283, (1992) · Zbl 0777.90035
[24] Lucidi, S.; Rinaldi, F., Exact penalty functions for nonlinear integer programming problems, Journal of Optimization Theory and Applications, 145, 479-488, (2010) · Zbl 1206.90100
[25] Mangasarian, O. L., Machine learning via polyhedral concave minimization, (Fischer, H.; Riedmueller, B.; Schaeffler, S., Applied Mathematics and Parallel Computing-Festschrift for Klaus Ritter, (1996), Physica Heidelberg), 175-188 · Zbl 0906.68127
[26] Mangasarian, O. L., Solutions of general linear complementarity problems via nondifferentiable concave minimization, Acta Mathematica Vietnamica, 22, 1, 199-205, (1997) · Zbl 0895.90167
[27] Rinaldi, F., New results on the equivalence between zero-one programming and continuous concave programming, Optimization Letters, 3, 3, 377-386, (2009) · Zbl 1170.90438
[28] Rinaldi, F.; Schoen, F.; Sciandrone, M., Concave programming for minimizing the zero-norm over polyhedral sets, Computational Optimization and Applications, 46, 467-486, (2010) · Zbl 1229.90170
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.