A novel dynamic programming heuristic for the quadratic knapsack problem

DOI10.1016/J.EJOR.2024.06.034MaRDI QIDQ6982615zbMATH OpenFDO

Authors M. Eliass Fennich, Franklin Djeumou Fomeni, Leandro C. Coelho

Publication date 16 May 2025

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.EJOR.2024.06.034

zbMATH Keywords

binary quadratic problemscombinatorial optimizationdynamic programmingheuristicsquadratic knapsack problem

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Quadratic programming (90C20) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Cites work

• A cut-and-branch algorithm for the quadratic knapsack problem
• A dynamic programming heuristic for the quadratic knapsack problem
• A lifted-space dynamic programming algorithm for the quadratic knapsack problem
• An effective GRASP and tabu search for the 0-1 quadratic knapsack problem
• An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
• An iterated ``hyperplane exploration approach for the quadratic knapsack problem
• Asymptotic behavior of the quadratic knapsack problem
• Dynamic programming revisited: Improving knapsack algorithms
• Exact Solution of the Quadratic Knapsack Problem
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 4112385 (Why is no real title available?)
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 1380608 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• Linear programming for the \(0-1\) quadratic knapsack problem
• Quadratic knapsack problems
• Revisiting \textit{Where are the hard knapsack problems?} via instance space analysis
• Solution of large quadratic knapsack problems through aggressive reduction
• The linearization problem of a binary quadratic problem and its applications
• The quadratic 0-1 knapsack problem with series-parallel support
• The quadratic knapsack problem -- a survey
• Theoretical and computational study of several linearisation techniques for binary quadratic problems
• Using a mixed integer programming tool for solving the 0-1 quadratic knapsack problem

Cited in

(6)

• On budget-constrained coverage in multi-interface networks: branchwidth and treewidth perspectives
• Tight upper and lower bounds for the quadratic knapsack problem through binary decision diagrams
• The quadratic knapsack problem
• A 3-space dynamic programming heuristic for the cubic knapsack problem
• A fast and effective breakpoints heuristic algorithm for the quadratic knapsack problem
• Discrete optimization: a quantum revolution?

This page was built for publication: A novel dynamic programming heuristic for the quadratic knapsack problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6982615)