Exact solution methods for the k-item quadratic knapsack problem
From MaRDI portal
Publication:2835673
DOI10.1007/978-3-319-45587-7_15zbMATH Open1452.90273arXiv1602.05327OpenAlexW3105658137MaRDI QIDQ2835673FDOQ2835673
Authors: L. Létocart, Angelika Wiegele 
Publication date: 30 November 2016
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1602.05327
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
- CSDP, A C library for semidefinite programming
- The quadratic knapsack problem -- a survey
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- An Interior-Point Method for Semidefinite Programming
- Computational study of a family of mixed-integer quadratic programming problems
- Lagrangian relaxation procedure for cardinality-constrained portfolio optimization
- An Algorithm for Large Zero-One Knapsack Problems
- Algorithm for cardinality-constrained quadratic optimization
- An exact solution approach for portfolio optimization problems under stochastic and integer constraints
- Extending the QCR method to general mixed-integer programs
- The quadratic 0-1 knapsack problem with series-parallel support
- Linear programming for the \(0-1\) quadratic knapsack problem
- Improved semidefinite bounding procedure for solving max-cut problems to optimality
- Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
- Bounds for the quadratic assignment problem using the bundle method
- Solving k-Way Graph Partitioning Problems to Optimality: The Impact of Semidefinite Relaxations and the Bundle Method
Cited In (16)
- Variable fixing method by weighted average for the continuous quadratic knapsack problem
- Computational comparison of exact solution methods for 0-1 quadratic programs: recommendations for practitioners
- On reduction of duality gap in quadratic knapsack problems
- An improved convex 0-1 quadratic program reformulation for quadratic knapsack problems
- Integer quadratic knapsack problems
- Dantzig-Wolfe reformulations for binary quadratic problems
- Title not available (Why is that?)
- 0-1 quadratic knapsack problems: an exact approach based on a \(t\)-linearization
- 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
- Exact solution method to solve large scale integer quadratic multidimensional knapsack problems
- Global optimality conditions and optimization methods for quadratic knapsack problems
- An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
- Combining Constraint Propagation and Discrete Ellipsoid-Based Search to Solve the Exact Quadratic Knapsack Problem
- A semidefinite programming approach to the quadratic knapsack problem
Uses Software
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)
