The quadratic knapsack problem -- a survey

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

David Pisinger

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

90C22: Semidefinite programming

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90C27: Combinatorial optimization

90-02: Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

68W25: Approximation algorithms

Related Items

Knapsack

Uses Software

• SeDuMi

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An O(n) algorithm for quadratic knapsack problems
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Geometric algorithms and combinatorial optimization
• Linear programming for the \(0-1\) quadratic knapsack problem
• Lagrangean methods for the 0-1 quadratic knapsack problem
• An extended formulation approach to the edge-weighted maximal clique problem
• A cutting-plane approach to the edge-weighted maximal clique problem
• Min-cut clustering
• On the \(0/1\) knapsack polytope
• The quadratic assignment problem. Theory and algorithms
• A semidefinite programming approach to the quadratic knapsack problem
• A new upper bound for the 0-1 quadratic knapsack problem
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• The cut polytope and the Boolean quadric polytope
• The quadratic 0-1 knapsack problem with series-parallel support
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Quadratic knapsack problems
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• Approximations of pseudo-Boolean functions; applications to game theory
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Technical Note—A Note on Zero-One Programming
• Facets of the knapsack polytope
• Minimum cuts and related problems
• Efficient Methods For Solving Quadratic 0–1 Knapsack Problems
• A Minimal Algorithm for the 0-1 Knapsack Problem
• Exact Solution of the Quadratic Knapsack Problem
• A Spectral Bundle Method for Semidefinite Programming
• Quadratic knapsack relaxations using cutting planes and semidefinite programming
• A Fast Parametric Maximum Flow Algorithm and Applications
• A Branch and Bound Algorithm for Integer Quadratic Knapsack Problems
• A Selection Problem of Shared Fixed Costs and Network Flows
• The traveling-salesman problem and minimum spanning trees: Part II
• Handbook of semidefinite programming. Theory, algorithms, and applications