Bounds on the size of branch-and-bound proofs for integer knapsacks

DOI10.1016/j.orl.2007.04.011zbMath1151.90060OpenAlexW2065207772MaRDI QIDQ924879

Bala Krishnamoorthy

Publication date: 29 May 2008

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2007.04.011

zbMATH Keywords

integer programmingknapsack problembranch-and-bound proofs

Mathematics Subject Classification ID

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

Related Items (3)

Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ Yet harder knapsack problems ⋮ Thinner is not always better: cascade knapsack problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lattice translates of a polytope and the Frobenius problem
• The Frobenius Problem and Maximal Lattice Free Bodies
• Hard Knapsack Problems
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• On the linear diophantine problem of Frobenius.
• Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances
• Trivial integer programs unsolvable by branch-and-bound
• On a linear diophantine problem of Frobenius
• Hard Equality Constrained Integer Knapsacks

This page was built for publication: Bounds on the size of branch-and-bound proofs for integer knapsacks