×

zbMATH — the first resource for mathematics

Adaptive kernel search: a heuristic for solving mixed integer linear programs. (English) Zbl 1380.90290
Summary: We introduce adaptive kernel search (AKS), a heuristic framework for the solution of (general) mixed integer linear programs (MIPs). AKS extends and enhances kernel search, a heuristic framework that has been shown to produce high-quality solutions for a number of specific (combinatorial) optimization problems in a short amount of time. AKS solves a sequence of carefully constructed restricted MIPs (using a commercial MIP solver). The computational effort required to solve the first restricted MIP guides the construction of the subsequent MIPs. The restricted MIPs are constructed around a kernel, which contains the variables that are presumably non-zero in an optimal solution. Computational results, for a set of 137 instances, show that AKS significantly outperforms other state-of-the-art heuristics for solving MIPs. AKS also compares favorably to CPLEX and offers more flexibility to trade-off solution quality and computing time.

MSC:
90C59 Approximation methods and heuristics in mathematical programming
90C11 Mixed integer programming
PDF BibTeX Cite
Full Text: DOI
References:
[1] Achterberg, T.; Berthold, T., Improving the feasibility pump, Discrete Optimization, 4, 1, 77-86, (2007) · Zbl 1170.90443
[2] Angelelli, E.; Mansini, R.; Speranza, M. G., Kernel search: A general heuristic for the multi-dimensional knapsack problem, Computers & Operations Research, 37, 11, 2017-2026, (2010) · Zbl 1188.90207
[3] Angelelli, E.; Mansini, R.; Speranza, M. G., Kernel search: A new heuristic framework for portfolio selection, Computational Optimization and Applications, 51, 1, 345-361, (2012) · Zbl 1246.91119
[4] Baena, D.; Castro, J., Using the analytic center in the feasibility pump, Operations Research Letters, 39, 5, 310-317, (2011) · Zbl 1235.90098
[5] Balas, E.; Ceria, S.; Dawande, M.; Margot, F.; Pataki, G., OCTANE: A new heuristic for pure 0-1 programs, Operations Research, 49, 2, 207-225, (2001) · Zbl 1163.90654
[6] Balas, E.; Schmieta, S.; Wallace, C., Pivot and shift - A mixed integer programming heuristic, Discrete Optimization, 1, 1, 3-12, (2004) · Zbl 1087.90052
[7] Bertacco, L.; Fischetti, M.; Lodi, A., A feasibility pump heuristic for general mixed-integer problems, Discrete Optimization, 4, 1, 63-76, (2007) · Zbl 1169.90415
[8] Boland, N. L.; Eberhard, A. C.; Engineer, F. G.; Fischetti, M.; Savelsbergh, M.; Tsoukalas, A., Boosting the feasibility pump, Mathematical Programming Computation, 6, 3, 255-279, (2014) · Zbl 1323.65065
[9] Danna, E.; Rothberg, E.; Le Pape, C., Exploring relaxation induced neighborhoods to improve MIP solutions, Mathematical Programming, Series A, 102, 1, 71-90, (2005) · Zbl 1131.90036
[10] 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, 23, 3, 1575-1606, (2013) · Zbl 1282.90099
[11] De Santis, M.; Lucidi, S.; Rinaldi, F., Feasibility pump-like heuristics for mixed integer problems, Discrete Applied Mathematics, 165, 152-167, (2014) · Zbl 06292070
[12] Eckstein, J.; Nediak, M., Pivot, cut, and dive: A heuristic for 0-1 mixed integer programming, Journal of Heuristics, 13, 5, 471-503, (2007)
[13] Filippi, C.; Guastaroba, G.; Speranza, M. G., A heuristic framework for the bi-objective enhanced index tracking problem, Omega, 65, 122-137, (2016)
[14] Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Mathematical Programming, Series A, 104, 1, 91-104, (2005) · Zbl 1077.90039
[15] Fischetti, M.; Lodi, A., Local branching, Mathematical Programming, Series B, 98, 1, 23-47, (2003) · Zbl 1060.90056
[16] Fischetti, M.; Lodi, A., Repairing MIP infeasibility through local branching, Computers & Operations Research, 35, 5, 1436-1445, (2008) · Zbl 1278.90273
[17] Fischetti, M.; Lodi, A., Heuristics in mixed integer programming, (Cochran, J., Wiley encyclopedia of operations research and management science, 3, (2011), John Wiley & Sons), 2199-2204
[18] Fischetti, M.; Monaci, M., Proximity search for 0-1 mixed-integer convex programming, Journal of Heuristics, 20, 6, 709-731, (2014) · Zbl 1360.90173
[19] Fischetti, M.; Salvagnin, D., Feasibility pump 2.0, Mathematical Programming Computation, 1, 2, 201-222, (2009) · Zbl 1180.90208
[20] Glover, F., Parametric tabu-search for mixed integer programs, Computers & Operations Research, 33, 9, 2449-2494, (2006) · Zbl 1086.90061
[21] Glover, F.; Laguna, M., General purpose heuristics for integer programming - part I, Journal of Heuristics, 2, 4, 343-358, (1997) · Zbl 0887.90123
[22] Glover, F.; Laguna, M., General purpose heuristics for integer programming - part II, Journal of Heuristics, 3, 2, 161-179, (1997) · Zbl 0898.90094
[23] Guastaroba, G.; Speranza, M. G., Kernel search: an application to the index tracking problem, European Journal of Operational Research, 217, 1, 54-68, (2012) · Zbl 1244.91109
[24] Guastaroba, G.; Speranza, M. G., Kernel search for the capacitated facility location problem, Journal of Heuristics, 18, 6, 877-917, (2012)
[25] Guastaroba, G.; Speranza, M. G., A heuristic for BILP problems: the single source capacitated facility location problem, European Journal of Operational Research, 238, 2, 438-450, (2014) · Zbl 1338.90215
[26] Guzelsoy, M.; Nemhauser, G.; Savelsbergh, M., Restrict-and-relax search for 0-1 mixed-integer programs, EURO Journal on Computational Optimization, 1, 1, 201-218, (2013) · Zbl 1296.90081
[27] Hanafi, S.; Lazić, J.; Mladenović, N.; Wilbaut, C.; Crévits, I., New variable neighbourhood search based 0-1 MIP heuristics, Yugoslav Journal of Operations Research, 25, 3, 343-360, (2015) · Zbl 06749279
[28] Hansen, P.; Mladenović, N.; Urošević, D., Variable neighborhood search and local branching, Computers & Operations Research, 33, 10, 3034-3045, (2006) · Zbl 1086.90042
[29] Koch, T.; Achterberg, T.; Andersen, E.; Bastert, O.; Berthold, T.; Bixby, R. E.; Danna, E.; Gamrath, G.; Gleixner, A. M.; Heinz, S.; Lodi, A.; Mittelmann, H.; Ralphs, T.; Salvagnin, D.; Stey, D. E.; Wolter, K., Miplib 2010, Mathematical Programming Computation, 3, 2, 103-163, (2011)
[30] Lazić, J.; Hanafi, S.; Mladenović, N.; Urošević, D., Variable neighbourhood decomposition search for 0-1 mixed integer programs, Computers & Operations Research, 37, 6, 1055-1067, (2010) · Zbl 1178.90253
[31] Løkketangen, A.; Glover, F., Solving zero-one mixed integer programming problems using tabu search, European Journal of Operational Research, 106, 2, 624-658, (1998) · Zbl 0991.90091
[32] Rothberg, E., An evolutionary algorithm for polishing mixed integer programming solutions, INFORMS Journal on Computing, 19, 4, 534-541, (2007) · Zbl 1241.90092
[33] Sacchi, L. H.; Armentano, V. A., A computational study of parametric tabu search for 0-1 mixed integer programs, Computers & Operations Research, 38, 2, 464-473, (2011) · Zbl 1231.90298
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.