Global optimality conditions and optimization methods for quadratic knapsack problems (Q658556)

The quadratic knapsack problem (QKP) maximizes a quadratic objective function subject to a binary and linear capacity constraint. The classic knapsack problem (CKP) is a special kind of QKP with no cross terms for the objective function, and the supermodular knapsack problem (SKP) is a special kind of QKP with nonnegative cross terms for the objective function. Due to the simple structure and challenging difficulty of QKP, it has been studied intensively during the last two decades. There are only a few methods available to solve QKP with some negative cross terms, namely LP relaxations, semidefinite relaxations, and some dynamic programming algorithms. This paper first presents some global optimality conditions for QKP, which include independent necessary conditions and sufficient conditions. Then a local optimization method for QKP is developed and the algorithm is presented using the necessary global optimality conditions. The number of iterations the algorithm requires to reach a local maximizer of the problem QKP is also derived. Finally, a global optimization method for QKP is proposed based on the sufficient global optimality condition, the local optimization method and an auxiliary function. The exact algorithm with some analysis of its functionality is also given. The paper concludes with several numerical examples to illustrate the efficiency of the presented optimization methods.