Global Optimality Conditions and Optimization Methods for Quadratic Knapsack Problems

Wu Z., Yang Y., Bai F., MƏMMƏDOV M.

Journal of Optimization Theory and Applications, vol.151, no.2, pp.241-259, 2011 (SCI-Expanded, Scopus) identifier

  • Nəşrin Növü: Article / Article
  • Cild: 151 Say: 2
  • Nəşr tarixi: 2011
  • Doi nömrəsi: 10.1007/s10957-011-9885-4
  • jurnalın adı: Journal of Optimization Theory and Applications
  • Jurnalın baxıldığı indekslər: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Səhifə sayı: pp.241-259
  • Açar sözlər: Global optimality conditions, Global optimization method, Local optimization method, Quadratic knapsack problem
  • Açıq Arxiv Kolleksiyası: Məqalə
  • Adres: Bəli

Qısa məlumat

The quadratic knapsack problem (QKP) maximizes a quadratic objective function subject to a binary and linear capacity constraint. Due to its simple structure and challenging difficulty, it has been studied intensively during the last two decades. This paper first presents some global optimality conditions for (QKP), which include necessary conditions and sufficient conditions. Then a local optimization method for (QKP) is developed using the necessary global optimality condition. Finally a global optimization method for (QKP) is proposed based on the sufficient global optimality condition, the local optimization method and an auxiliary function. Several numerical examples are given to illustrate the efficiency of the presented optimization methods. © 2011 Springer Science+Business Media, LLC.