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

DOI10.1016/j.dam.2023.02.003zbMath1519.90203OpenAlexW3175250543MaRDI QIDQ6041830

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

integer programmingdynamic programminglocal searchknapsack problemsbinary quadratic optimization

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic behavior of the quadratic knapsack problem
• An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
• 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
• A semidefinite programming approach to the quadratic knapsack problem
• An iterated ``hyperplane exploration approach for the quadratic knapsack problem
• Approximation of the quadratic knapsack problem
• The quadratic 0-1 knapsack problem with series-parallel support
• Sequence independent lifting in mixed integer programming
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
• Parametric convex quadratic relaxation of the quadratic knapsack problem
• 0-1 quadratic knapsack problem solved with VNS algorithm
• A cut-and-branch algorithm for the quadratic knapsack problem
• Detecting high log-densities
• Using a Mixed Integer Programming Tool for Solving the 0–1 Quadratic Knapsack Problem
• Solution of Large Quadratic Knapsack Problems Through Aggressive Reduction
• A Dynamic Programming Heuristic for the Quadratic Knapsack Problem
• Approximation of the Quadratic Knapsack Problem
• An Algorithm for Large Zero-One Knapsack Problems
• Quadratic knapsack problems
• Exact Solution of the Quadratic Knapsack Problem
• Reducibility among Combinatorial Problems
• Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Lagrangian heuristics for the quadratic knapsack problem

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