A lifted-space dynamic programming algorithm for the quadratic knapsack problem

DOI10.1016/J.DAM.2023.02.003MaRDI QIDQ6041830zbMATH OpenOpenAlexFDO

Authors Franklin Djeumou Fomeni

Publication date 15 May 2023

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

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

zbMATH Keywords

dynamic programminglocal searchinteger programmingknapsack problemsbinary quadratic optimization

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• A dynamic programming heuristic for the quadratic knapsack problem
• A cut-and-branch algorithm for the quadratic knapsack problem
• New algorithm for quadratic integer knapsack problems
• Exact Solution of the Quadratic Knapsack Problem
• An iterated ``hyperplane exploration approach for the quadratic knapsack problem

Cites work

• 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 1795719 (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?)
• 0-1 quadratic knapsack problem solved with VNS algorithm
• A cut-and-branch algorithm for the quadratic knapsack problem
• A dynamic programming heuristic for the quadratic knapsack problem
• A semidefinite programming approach to the quadratic knapsack problem
• An Algorithm for Large Zero-One Knapsack Problems
• An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
• An iterated ``hyperplane exploration approach for the quadratic knapsack problem
• Approximation of the quadratic knapsack problem
• Approximation of the quadratic knapsack problem
• Asymptotic behavior of the quadratic knapsack problem
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Exact Solution of the Quadratic Knapsack Problem
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• Lagrangian heuristics for the quadratic knapsack problem
• Linear programming for the \(0-1\) quadratic knapsack problem
• On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
• Parametric convex quadratic relaxation of the quadratic knapsack problem
• Quadratic knapsack problems
• Reducibility among combinatorial problems
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Sequence independent lifting in mixed integer programming
• Solution of large quadratic knapsack problems through aggressive reduction
• Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
• The quadratic 0-1 knapsack problem with series-parallel support
• The quadratic knapsack problem -- a survey
• Using a mixed integer programming tool for solving the 0-1 quadratic knapsack problem

Cited in

(7)

• An iterated ``hyperplane exploration approach for the quadratic knapsack problem
• Lagrangian heuristics for the quadratic knapsack problem
• A cut-and-branch algorithm for the quadratic knapsack problem
• A logarithmic descent direction algorithm for the quadratic knapsack problem
• New algorithm for quadratic integer knapsack problems
• A dynamic programming heuristic for the quadratic knapsack problem
• An approximate dynamic programming approach to convex quadratic knapsack problems

This page was built for publication: A lifted-space dynamic programming algorithm for the quadratic knapsack problem

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