×

zbMATH — the first resource for mathematics

An iterated “hyperplane exploration” approach for the quadratic knapsack problem. (English) Zbl 1391.90507
Summary: The quadratic knapsack problem (QKP) is a well-known combinatorial optimization problem with numerous applications. Given its NP-hard nature, finding optimal solutions or even high quality suboptimal solutions to QKP in the general case is a highly challenging task. In this paper, we propose an iterated “hyperplane exploration” approach (IHEA) to solve QKP approximately. Instead of considering the whole solution space, the proposed approach adopts the idea of searching over a set of hyperplanes defined by a cardinality constraint to delimit the search to promising areas of the solution space. To explore these hyperplanes efficiently, IHEA employs a variable fixing strategy to reduce each hyperplane-constrained sub-problem and then applies a dedicated tabu search procedure to locate high quality solutions within the reduced solution space. Extensive experimental studies over three sets of 220 QKP instances indicate that IHEA competes very favorably with the state-of-the-art algorithms both in terms of solution quality and computing efficiency. We provide additional information to gain insight into the key components of the proposed approach.

MSC:
90C27 Combinatorial optimization
90C09 Boolean programming
90C10 Integer programming
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Billionnet, A.; Calmels, F., Linear programming for the 0-1 quadratic knapsack problem, Eur J Oper Res, 92, 310-325, (1996) · Zbl 0912.90221
[2] Billionnet, A.; Soutif, E., An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem, Eur J Oper Res, 157, 565-575, (2004) · Zbl 1067.90126
[3] Birattari, M.; Yuan, Z.; Balaprakash, P.; Sttzle, T., F-race and iterated f-race: an overview experimental methods for the analysis of optimization algorithms, 311-336, (2010), Springer Berlin, Germany · Zbl 1204.68280
[4] Boussier, S.; Vasquez, M.; Vimont, Y.; Hanafi, S.; Michelon, P., A multi-level search strategy for the 0-1 multidimensional knapsack problem, Discrete Appl Math, 158, 2, 97-109, (2010) · Zbl 1185.90170
[5] Chaillou, P.; Hansen, P.; Mahieu, Y., Best network flow bound for the quadratic knapsack problem, Lect Notes Math, 1403, 226-235, (1983)
[6] Caprara, A.; Pisinger, D.; Toth, P., Exact solution of the quadratic knapsack problem, INFORMS J Comput, 11, 125-137, (1999) · Zbl 1034.90521
[7] Chen, Y.; Hao, J. K., A reduce and solve approach for the multiple-choice multidimensional knapsack problem, Eur J Oper Res, 239, 2, 313-322, (2014) · Zbl 1339.90237
[8] Dammeyer F., Voß S. Dynamic tabu list management using the reverse elimination method. Ann Oper Res 1993;41:31-46. · Zbl 0775.90290
[9] Dijkhuizen, G.; Faigle, U., A cutting-plane approach to the edge-weighted maximal clique problem, Eur J Oper Res, 69, 121-130, (1993) · Zbl 0787.90059
[10] Feo, T.; Resende, M. G.C., Greedy randomized adaptive search procedures, J Glob Optim, 2, 1-27, (1995) · Zbl 0822.90110
[11] Fleszar, K.; Fast, Hindi K. S., Effective heuristics for the 0-1 multi-dimensional knapsack problem, Comput Oper Res, 36, 5, 1602-1607, (2009) · Zbl 1179.90282
[12] Fomeni, F. D.; Letchford, A. N., A dynamic programming heuristic for the quadratic knapsack problem, INFORMS J Comput, 26, 1, 173-182, (2014) · Zbl 1356.90165
[13] Foster, B. A.; Ryan, D. M., An integer programming approach to scheduling, (Wren, A., Computer scheduling of public transport, (1981), North-Holland Publishing Company Amsterdam), 269-280
[14] Gallo, G.; Hammer, P.; Simeone, B., Quadratic knapsack problems, Math Progr Stud, 12, 132-149, (1980) · Zbl 0462.90068
[15] Glover, F., Heuristics for integer programming using surrogate constraints, Decis Sci, 8, 1, 156-166, (1977)
[16] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Academic Publishers Boston · Zbl 0930.90083
[17] Glover, F.; Hao, J. K., The case for strategic oscillation, Ann Oper Res, 183, 1, 163-173, (2011) · Zbl 1214.90097
[18] Glover, F.; Kochenberger, G.; Alidaee, B.; Amini, M., Series on applied mathematics, Solving quadratic knapsack problems by reformulation and tabu search. Single constraint case, 14, 111-122, (2002), World Scientific Publishing Company Singapore
[19] Glover, F.; Lü, Z. P.; Hao, J. K., Diversification-driven tabu search for unconstrained binary quadratic problems, 4OR—Q J Oper Res, 8, 3, 239-253, (2010) · Zbl 1201.90169
[20] Hammer, P. L.; Rader, D. J., Efficient methods for solving quadratic 0-1 knapsack problem, INFOR, 35, 170-182, (1997) · Zbl 0888.90121
[21] Helmberg, C.; Rendl, F.; Weismantel, R., A semidefinite programming approach to the quadratic knapsack problem, J Comb Optim, 4, 197-215, (2000) · Zbl 0970.90075
[22] Johnson, E.; Mehrotra, A.; Nemhauser, G., MIN-cut clustering, Math Progr, 62, 133-151, (1993) · Zbl 0807.90117
[23] Julstorm BA, Greedy, genetic, and greedy genetic algorithms for the quadratic knapsack problem. In: Genetic and Evolutionary Computation Conference, Washington DC, USA; 2005. p. 607-14.
[24] Kellerer, H.; Strusevich, V. A., Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications, Algorithmica, 57, 4, 769-795, (2010) · Zbl 1208.90149
[25] López-Ibáñez M, Dubois-Lacoste J, Stützle T, Birattari M. The irace package, iterated race for automatic algorithm configuration. Technical Report TR/IRIDIA/2011-004, IRIDIA, Universit Libre de Bruxelles, Belgium; 2011.
[26] Martinelli, R.; Poggi, M.; Subramanian, A., Improved bounds for large scale capacitated arc routing problem, Comput Oper Res, 40, 8, 2145-2160, (2013) · Zbl 1348.90476
[27] Park, K.; Lee, K.; Park, S., An extended formulation approach to the edge-weighted maximal clique problem, Eur J Oper Res, 95, 671-682, (1996) · Zbl 0926.90086
[28] Pisinger, D., The quadratic knapsack problem—a survey, Discrete Appl Math, 155, 623-648, (2007) · Zbl 1143.90028
[29] Pisinger, D.; Rasmussen, A. B.; Sandvik, R., Solution of large-sized quadratic knapsack problems through aggressive reduction, INFORMS J Comput, 19, 2, 280-290, (2007) · Zbl 1241.90119
[30] Sil M. Column generation techniques for pickup and delivery problems [Ph.D. thesis]. Technische Universiteit Eindhoven; 1994.
[31] Usberti, F. L.; Frana, P. M.; Frana, A. L.M., GRASP with evolutionary path-relinking for the capacitated arc routing problem, Comput Oper Res, 40, 12, 3206-3217, (2013) · Zbl 1348.90158
[32] Vasquez M, Hao JK. An hybrid approach for the 0-1 multidimensional knapsack problem. In: Proceedings of the 17th international joint conference of artificial intelligence (IJCAI-2001). San Francisco: Morgan Kaufmann; p. 328-33.
[33] Wang, Y.; Lü, Z. P.; Glover, F.; Hao, J. K., Backbone guided tabu search for solving the UBQP problem, J Heuristics, 19, 4, 679-695, (2013)
[34] Wilbaut, C.; Hanafi, S., New convergent heuristics for 0-1 mixed integer programming, Eur J Oper Res, 195, 1, 62-74, (2009) · Zbl 1161.90448
[35] Xie X, Liu J. A Mini-Swarm for the quadratic knapsack problem. In: IEEE Swarm Intelligence Symposium, Honolulu, HI, USA; 2007. p. 190-7.
[36] Xu, Z., A strongly polynomial FPTAS for the symmetric quadratic knapsack problem, Eur J Oper Res, 218, 2, 377-381, (2012) · Zbl 1244.90202
[37] Yang, Z.; Wang, G.; Chu, F., An effective GRASP and tabu search for the 0-1 quadratic knapsack problem, Comput Oper Res, 40, 1176-1185, (2013) · Zbl 1352.90064
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.