๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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

โœ Scribed by Bala Krishnamoorthy

Publisher
Elsevier Science
Year
2008
Tongue
English
Weight
172 KB
Volume
36
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

โœฆ Synopsis

Using a direct counting argument, we derive lower and upper bounds for the number of nodes enumerated by linear programming-based branch-and-bound (B&B) method to prove the integer infeasibility of a knapsack. We prove by example that the size of the B&B tree could be exponential in the worst case.

๐Ÿ“œ SIMILAR VOLUMES

The critical-item, upper bounds, and a b
The critical-item, upper bounds, and a branch-and-bound algorithm for the tree knapsack problem
โœ Shaw, Dong X.; Cho, Geon ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 155 KB ๐Ÿ‘ 2 views

The tree knapsack problem (TKP) is a generalized 0-1 knapsack problem where all the items (nodes) are subjected to a partial ordering represented by a rooted tree. If a node is selected to be packed into the knapsack, then all the items on the path from the selected node to the root must also be pac