Global optimality conditions and optimization methods for quadratic knapsack problems
type: Item
instance of: scholarly article
title: Global optimality conditions and optimization methods for quadratic knapsack problems
zbMATH Open document ID: 1237.90214
author: Juan-Miguel Gracia
published in: Journal of Optimization Theory and Applications
publication date: 2012-01-12T00:00:00Z
review text: 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.
reviewed by: Vladimír Lacko
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C26
Mathematics Subject Classification ID: 90C46
zbMATH DE Number: 5996880
zbMATH Keywords: quadratic knapsack problem
zbMATH Keywords: global optimality conditions
zbMATH Keywords: local optimization method
zbMATH Keywords: global optimization method
describes a project that uses: Knapsack
MaRDI profile type: Publication
full work available at URL: s10957-011-9885-4
OpenAlex ID: W1973286416
Wikidata QID: Q56050296
cites work: Quadratic knapsack problems
cites work: The quadratic knapsack problem -- a survey
cites work: A Selection Problem of Shared Fixed Costs and Network Flows
cites work: Min-cut clustering
cites work: A new upper bound for the 0-1 quadratic knapsack problem
cites work: Q3993418
cites work: Q4247440
cites work: An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
cites work: On the supermodular knapsack problem
cites work: Efficient Methods For Solving Quadratic 0–1 Knapsack Problems
cites work: Lagrangean methods for the 0-1 quadratic knapsack problem
cites work: Exact Solution of the Quadratic Knapsack Problem
cites work: Linear programming for the \(0-1\) quadratic knapsack problem
cites work: The quadratic 0-1 knapsack problem with series-parallel support
cites work: Global optimality conditions for quadratic optimization problems with binary constraints
cites work: Sufficient global optimality conditions for non-convex quadratic minimization problems with box constraints
cites work: Sufficient global optimality conditions for bivalent quadratic optimization
cites work: Handbook of test problems in local and global optimization
DOI: 10.1007/S10957-011-9885-4
description: scientific article; zbMATH DE number 5996880