A Dynamic Programming Heuristic for the Quadratic Knapsack Problem

DOI10.1287/ijoc.2013.0555zbMath1356.90165OpenAlexW2123981023WikidataQ57702148 ScholiaQ57702148MaRDI QIDQ2967622

Franklin Djeumou Fomeni, Adam N. Letchford

Publication date: 1 March 2017

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/62702/1/2014_qkp_heuristic.pdf

zbMATH Keywords

integer programmingdynamic programmingknapsack problems

Mathematics Subject Classification ID

Integer programming (90C10) Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

A new family of facet defining inequalities for the maximum edge-weighted clique problem, Dual mean field search for large scale linear and quadratic knapsack problems, On exact solution approaches for bilevel quadratic 0-1 knapsack problem, 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, An iterated ``hyperplane exploration approach for the quadratic knapsack problem, A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem, New concepts of principal component analysis based on maximum separation of clusters, Dual mean field annealing scheme for binary optimization under linear constraints, A cut-and-branch algorithm for the quadratic knapsack problem, A lifted-space dynamic programming algorithm for the quadratic knapsack problem, Matheuristics: survey and synthesis, An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating, Network-Based Approximate Linear Programming for Discrete Optimization, Lagrangian heuristics for the quadratic knapsack problem, Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The quadratic knapsack problem -- a survey
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Linear programming for the \(0-1\) quadratic knapsack problem
• Lagrangean methods for the 0-1 quadratic knapsack problem
• The quadratic 0-1 knapsack problem with series-parallel support
• Detecting high log-densities
• Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction
• An Algorithm for Large Zero-One Knapsack Problems
• Quadratic knapsack problems
• Exact Solution of the Quadratic Knapsack Problem
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique