A logarithmic descent direction algorithm for the quadratic knapsack problem

Zhengtian Wu, Baoping Jiang and Hamid Reza Karimi

Applied Mathematics and Computation, 2020, vol. 369, issue C

Abstract: 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.

Keywords: Quadratic knapsack problem; NP-hard optimization problem; Damped newton method; Karush–Kuhn–Tucker condition (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S009630031930846X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:369:y:2020:i:c:s009630031930846x

DOI: 10.1016/j.amc.2019.124854

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().