zbMATH — the first resource for mathematics

A logarithmic descent direction algorithm for the quadratic knapsack problem. (English) Zbl 1433.90105
Summary: The quadratic knapsack problem is an NP-hard optimization problem with many diverse applications in industrial and management engineering. However, computational complexities still remain in the quadratic knapsack problem. In this study, a logarithmic descent direction algorithm is proposed to approximate a solution to the quadratic knapsack problem. The proposed algorithm is based on the Karush-Kuhn-Tucker necessary optimality condition and the damped Newton method. The convergence of the algorithm is proven, and the numerical results indicate its effectiveness.
90C20 Quadratic programming
65K10 Numerical optimization and variational techniques
90C51 Interior-point methods
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
Full Text: DOI
[1] Gallo, G.; Hammer, P. L.; Simeone, B., Quadratic knapsack problems, Combinatorial Optimization, 132-149 (1980), Springer · Zbl 0462.90068
[2] Wolfe, P., Algorithm for a least-distance programming problem, Pivoting and Extension, 190-205 (1974), Springer
[3] Motzkin, T. S.; Straus, E. G., Maxima for graphs and a new proof of a theorem of Turán, Can. J. Math., 17, 533-540 (1965) · Zbl 0129.39902
[4] Gary, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of Np-Completeness (1979), W. H. Freeman & Co: W. H. Freeman & Co New York · Zbl 0411.68039
[5] Pardalos, P. M.; Schnitger, G., Checking local optimality in constrained quadratic programming is np-hard, Oper. Res. Lett., 7, 1, 33-35 (1988) · Zbl 0644.90067
[6] Pardalos, P. M.; Rosen, J. B., Constrained Global Optimization: Algorithms and Applications, 268 (1987), Springer · Zbl 0638.90064
[7] Pardalos, P. M.; Ye, Y.; Han, C.-G., Algorithms for the solution of quadratic knapsack problems, Linear Algebra Appl., 152, 69-91 (1991) · Zbl 0729.65047
[8] Chen, Y.; Hao, J.-K., Memetic search for the generalized quadratic multiple knapsack problem, IEEE Trans. Evol. Comput., 20, 6, 908-923 (2016)
[9] Chen, Y.; Hao, J., The bi-objective quadratic multiple knapsack problem: model and heuristics, Knowl. Based Syst., 97, 89-100 (2016)
[10] Zhou, Y.; Chen, X.; Zhou, G., An improved monkey algorithm for a 0-1 knapsack problem, Appl. Soft Comput., 38, 817-830 (2016)
[11] Yassien, E.; Masadeh, R.; Alzaqebah, A.; Shaheen, A., Grey wolf optimization applied to the 0/1 knapsack problem, Int. J. Comput. Appl., 169, 5, 11-15 (2017)
[12] Cao, J.; Yin, B.; Lu, X.; Kang, Y.; Chen, X., A modified artificial bee colony approach for the 0-1 knapsack problem, Appl. Intell., 1-14 (2018)
[13] Song, B.; Li, Y.; Chen, Y.; Yao, F.; Chen, Y., A repair-based approach for stochastic quadratic multiple knapsack problem, Knowl. Based Syst., 145, 145-155 (2018)
[14] Bergman, D., An exact algorithm for the quadratic multiknapsack problem with an application to event seating, INFORMS J. Comput. (2019)
[15] Lai, X.; Hao, J.-K.; Yue, D., Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem, Eur. J. Oper. Rese., 274, 1, 35-48 (2019) · Zbl 1430.90493
[16] Blado, D.; Toriello, A., Relaxation analysis for the dynamic knapsack problem with stochastic item sizes, SIAM J. Optim., 29, 1, 1-30 (2019) · Zbl 1411.90340
[17] Mellor-Crummey, J. M.; Scott, M. L., Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Trans. Comput. Syst. (TOCS), 9, 1, 21-65 (1991)
[18] Bonami, P.; Lodi, A.; Schweiger, J.; Tramontani, A., Solving quadratic programming by cutting planes, SIAM J. Optim., 29, 2, 1076-1105 (2019) · Zbl 1411.90247
[19] Abdel-Basset, M.; El-Shahat, D.; Faris, H.; Mirjalili, S., A binary multi-verse optimizer for 0-1 multidimensional knapsack problems with application in interactive multimedia systems, Comput. Ind. Eng., 132, 187-206 (2019)
[20] Dang, C.; Xu, L., A globally convergent lagrange and barrier function iterative algorithm for the traveling salesman problem, Neural Netw., 14, 2, 217-230 (2001)
[21] Palubeckis, G., Multistart tabu search strategies for the unconstrained binary quadratic optimization problem, Ann. Oper. Res., 131, 1-4, 259-282 (2004) · Zbl 1066.90069
[22] Dang, C.; Ma, W.; Liang, J., A deterministic annealing algorithm for approximating a solution of the min-bisection problem, Neural Netw., 22, 1, 58-66 (2009) · Zbl 1335.90104
[23] Dokeroglu, T., Hybrid teaching-learning-based optimization algorithms for the quadratic assignment problem, Comput. Ind. Eng., 85, 86-101 (2015)
[24] Wu, Z.; Karimi, H. R.; Dang, C., An approximation algorithm for graph partitioning via deterministic annealing neural network, Neural Netw., 117, 191-200 (2019)
[25] Nesterov, Y., Lectures on Convex Optimization, 137 (2018), Springer · Zbl 1427.90003
[26] Han, J.; Yang, C.; Zhou, X.; Gui, W., A two-stage state transition algorithm for constrained engineering optimization problems, Int. J. Control Autom. Syst., 16, 2, 522-534 (2018)
[27] Fiacco, A. V.; McCormick, G. P., Nonlinear Programming: Sequential Unconstrained Minimization Techniques, 4 (1990), SIAM · Zbl 0713.90043
[28] Ye, Y., On homogeneous and self-dual algorithms for LCP, Math. Program., 76, 1, 211-221 (1997) · Zbl 0881.90116
[29] Tseng, P.; Ye, Y., On some interior-point algorithms for nonconvex quadratic optimization, Math. Program., 93, 2, 217-225 (2002) · Zbl 1053.90136
[30] Allgower, E. L.; Georg, K., Computational Solution of Nonlinear Systems of Equations, 26 (1990), American Mathematical Soc.
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.