A branch-and-bound algorithm for multi-dimensional quadratic 0–1 knapsack problems

DOI10.1007/s11741-007-0308-zzbMath1174.90708OpenAlexW2080502781MaRDI QIDQ5436249

Hongbo Sheng, Juan Sun, Xiaoling Sun

Publication date: 14 January 2008

Published in: Journal of Shanghai University (English Edition) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11741-007-0308-z

zbMATH Keywords

Lagrangian relaxationbranch-and-bound methodmulti-dimensional quadratic \(0\)-\(1\) knapsack problem

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Uses Software

• Knapsack

Cites Work

• Lagrangean methods for the 0-1 quadratic knapsack problem
• On the supermodular knapsack problem
• A new approach to the maximum-flow problem
• Quadratic knapsack problems
• Minimum cuts and related problems
• Efficient Methods For Solving Quadratic 0–1 Knapsack Problems
• Exact Solution of the Quadratic Knapsack Problem
• A Fast Parametric Maximum Flow Algorithm and Applications
• A Selection Problem of Shared Fixed Costs and Network Flows