Exact solution methods for the k-item quadratic knapsack problem
From MaRDI portal
Publication:2835673
Abstract: The purpose of this paper is to solve the 0-1 -item quadratic knapsack problem , a problem of maximizing a quadratic function subject to two linear constraints. We propose an exact method based on semidefinite optimization. The semidefinite relaxation used in our approach includes simple rank one constraints, which can be handled efficiently by interior point methods. Furthermore, we strengthen the relaxation by polyhedral constraints and obtain approximate solutions to this semidefinite problem by applying a bundle method. We review other exact solution methods and compare all these approaches by experimenting with instances of various sizes and densities.
Recommendations
- 0-1 quadratic knapsack problems: an exact approach based on a \(t\)-linearization
- Exact Solution of the Quadratic Knapsack Problem
- Integer quadratic knapsack problems
- An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
- A semidefinite programming approach to the quadratic knapsack problem
Cites work
- Algorithm for cardinality-constrained quadratic optimization
- An Algorithm for Large Zero-One Knapsack Problems
- An Interior-Point Method for Semidefinite Programming
- An exact solution approach for portfolio optimization problems under stochastic and integer constraints
- Bounds for the quadratic assignment problem using the bundle method
- CSDP, A C library for semidefinite programming
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- Computational study of a family of mixed-integer quadratic programming problems
- Extending the QCR method to general mixed-integer programs
- Improved semidefinite bounding procedure for solving max-cut problems to optimality
- Lagrangian relaxation procedure for cardinality-constrained portfolio optimization
- Linear programming for the \(0-1\) quadratic knapsack problem
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Solving \(k\)-way graph partitioning problems to optimality: the impact of semidefinite relaxations and the bundle method
- The quadratic 0-1 knapsack problem with series-parallel support
- The quadratic knapsack problem -- a survey
Cited in
(19)- Exact solution method to solve large scale integer quadratic multidimensional knapsack problems
- Dantzig-Wolfe reformulations for binary quadratic problems
- A note on semidefinite relaxation for 0-1 quadratic knapsack problems
- scientific article; zbMATH DE number 1911487 (Why is no real title available?)
- A conic approximation method for the 0-1 quadratic knapsack problem
- Computational comparison of exact solution methods for 0-1 quadratic programs: recommendations for practitioners
- Parametric convex quadratic relaxation of the quadratic knapsack problem
- 0-1 quadratic knapsack problems: an exact approach based on a \(t\)-linearization
- An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
- Exact Solution of the Quadratic Knapsack Problem
- Rank two relaxation to the quadratic knapsack problem
- A two-phase method for solving continuous rank-one quadratic knapsack problems
- Variable fixing method by weighted average for the continuous quadratic knapsack problem
- On reduction of duality gap in quadratic knapsack problems
- An improved convex 0-1 quadratic program reformulation for quadratic knapsack problems
- Global optimality conditions and optimization methods for quadratic knapsack problems
- Combining Constraint Propagation and Discrete Ellipsoid-Based Search to Solve the Exact Quadratic Knapsack Problem
- Integer quadratic knapsack problems
- A semidefinite programming approach to the quadratic knapsack problem
This page was built for publication: Exact solution methods for the \(k\)-item quadratic knapsack problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835673)
