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.
A logarithmic descent direction algorithm for the quadratic knapsack problem
Karimi H. R.
2020-01-01
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
