The quadratic knapsack problem -- a survey

DOI10.1016/j.dam.2006.08.007zbMath1143.90028OpenAlexW2082782506WikidataQ58826435 ScholiaQ58826435MaRDI QIDQ875597

Publication date: 13 April 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.08.007

zbMATH Keywords

upper bounds semidefinite programming valid inequalities approximation algorithms quadratic knapsack problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Approximation algorithms (68W25)

Related Items (83)

Stochastic Quadratic Knapsack with Recourse ⋮ A branch-and-cut technique to solve multiobjective integer quadratic programming problems ⋮ A new family of facet defining inequalities for the maximum edge-weighted clique problem ⋮ BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints ⋮ Dantzig-Wolfe reformulations for binary quadratic problems ⋮ Dual mean field search for large scale linear and quadratic knapsack problems ⋮ On exact solution approaches for bilevel quadratic 0-1 knapsack problem ⋮ Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications ⋮ Knapsack problems with dependencies through non-additive measures and Choquet integral ⋮ A tight upper bound for quadratic knapsack problems in grid-based wind farm layout optimization ⋮ Greedy robust wind farm layout optimization with feasibility guarantee ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Asymptotic behavior of the quadratic knapsack problem ⋮ Approximation of the Quadratic Knapsack Problem ⋮ Generalized quadratic multiple knapsack problem and two solution approaches ⋮ An iterated ``hyperplane exploration approach for the quadratic knapsack problem ⋮ A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem ⋮ On the product knapsack problem ⋮ Lower bounds and exact algorithms for the quadratic minimum spanning tree problem ⋮ A hybrid three-phase approach for the Max-Mean dispersion problem ⋮ A Hybrid Heuristic Approach Based on a Quadratic Knapsack Formulation for the Max-Mean Dispersion Problem ⋮ A mathematical programming approach to overlapping community detection ⋮ On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study ⋮ Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions ⋮ On the rectangular knapsack problem ⋮ Structured linear reformulation of binary quadratically constrained quadratic programs ⋮ Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach ⋮ An exact semidefinite programming approach for the max-mean dispersion problem ⋮ Product allocation to different types of distribution center in retail logistics networks ⋮ Dual mean field annealing scheme for binary optimization under linear constraints ⋮ A cut-and-branch algorithm for the quadratic knapsack problem ⋮ An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem ⋮ SDP-based branch-and-bound for non-convex quadratic integer optimization ⋮ A lifted-space dynamic programming algorithm for the quadratic knapsack problem ⋮ Aggregation with dependencies: capacities and fuzzy integrals ⋮ The symmetric quadratic knapsack problem: approximation and scheduling applications ⋮ A general purpose exact solution method for mixed integer concave minimization problems ⋮ Approximation of the quadratic knapsack problem ⋮ Knapsack problem with probability constraints ⋮ A Dynamic Programming Heuristic for the Quadratic Knapsack Problem ⋮ On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem ⋮ Locating a discrete subtree of minimum variance on trees: new strategies to tackle a very hard problem ⋮ Quadratic Combinatorial Optimization Using Separable Underestimators ⋮ Global optimality conditions and optimization methods for quadratic knapsack problems ⋮ An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating ⋮ Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods ⋮ Completely positive and copositive program modelling for quadratic optimization problems ⋮ An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming ⋮ HEURISTIC AND EXACT SOLUTION METHOD FOR CONVEX NONLINEAR KNAPSACK PROBLEM ⋮ Optimal allocation of buffer times to increase train schedule robustness ⋮ MINIMIZING TOTAL WEIGHTED EARLINESS-TARDINESS ON A SINGLE MACHINE AROUND A SMALL COMMON DUE DATE: AN FPTAS USING QUADRATIC KNAPSACK ⋮ On reduction of duality gap in quadratic knapsack problems ⋮ Simple solution methods for separable mixed linear and quadratic knapsack problem ⋮ A computational study on the quadratic knapsack problem with multiple constraints ⋮ Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem ⋮ Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications ⋮ Branch-and-price for \(p\)-cluster editing ⋮ Optimizing a polyhedral-semidefinite relaxation of completely positive programs ⋮ Exact solution approach for a class of nonlinear bilevel knapsack problems ⋮ Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem ⋮ Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem ⋮ Lagrangian heuristics for the quadratic knapsack problem ⋮ Theoretical and computational study of several linearisation techniques for binary quadratic problems ⋮ Reformulation of the Quadratic Multidimensional Knapsack Problem as Copositive/Completely Positive Prorams ⋮ Knapsack ⋮ On linear conic relaxation of discrete quadratic programs ⋮ A Genetic Algorithm for Optimization of a Relational Knapsack Problem with Respect to a Description Logic Knowledge Base ⋮ A matheuristic for the 0--1 generalized quadratic multiple knapsack problem ⋮ Exact Solution Methods for the k-Item Quadratic Knapsack Problem ⋮ Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem ⋮ Computational comparison of exact solution methods for 0-1 quadratic programs: recommendations for practitioners ⋮ AN IMPROVED CONVEX 0-1 QUADRATIC PROGRAM REFORMULATION FOR CHANCE-CONSTRAINED QUADRATIC KNAPSACK PROBLEMS ⋮ Parametric convex quadratic relaxation of the quadratic knapsack problem ⋮ A nonlinear multidimensional knapsack problem in the optimal design of mixture experiments ⋮ Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems ⋮ Iterated responsive threshold search for the quadratic multiple knapsack problem ⋮ The polynomial robust knapsack problem ⋮ Solving the 0-1 quadratic knapsack problem with a competitive quantum inspired evolutionary algorithm ⋮ A note on semidefinite relaxation for 0-1 quadratic knapsack problems ⋮ Cutting planes for RLT relaxations of mixed 0-1 polynomial programs ⋮ A simplified binary artificial fish swarm algorithm for 0-1 quadratic knapsack problems ⋮ A dynamic inequality generation scheme for polynomial programming

Uses Software

SeDuMi

Cites Work

This page was built for publication: The quadratic knapsack problem -- a survey