×

Feasibility Pump-like heuristics for mixed integer problems. (English) Zbl 1471.90098

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:

90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
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
[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: 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: 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. 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.