Optimal strategy for solving a special case of the knapsack problem by the branch and bound method

DOI10.3103/S0027132221030050MaRDI QIDQ2666932zbMATH OpenFDO

Authors Roman Kolpakov

Publication date 23 November 2021

Published in Moscow University Mathematics Bulletin (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3103/S0027132221030050

zbMATH Keywords

branch and bound methodknapsack problemproblem solution complexitysolution strategy

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem
• A well-solvable special case of the bounded knapsack problem
• scientific article; zbMATH DE number 4139486
• An asymptotic estimate for the complexity of the branch and bound method with branching with respect to a fractional variable for the knapsack problem
• A new bound for the quadratic knapsack problem and its use in a branch and bound algorithm

Cites work

• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• On the best choice of a branching variable in the subset sum problem
• Upper and lower bounds for the complexity of the branch and bound method for the knapsack problem

Cited in

(3)

• A well-solvable special case of the bounded knapsack problem
• scientific article; zbMATH DE number 1149800 (Why is no real title available?)
• An improved branch and bound algorithm for a strongly correlated unbounded knapsack problem

This page was built for publication: Optimal strategy for solving a special case of the knapsack problem by the branch and bound method

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