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 (17)

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

This page was built for publication: A Dynamic Programming Heuristic for the Quadratic Knapsack Problem