𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the facets of the mixed–integer knapsack polyhedron

✍ Scribed by Alper Atamtürk

Publisher
Springer-Verlag
Year
2003
Tongue
English
Weight
318 KB
Volume
98
Category
Article
ISSN
0025-5610

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Bounds on the size of branch-and-bound p
Bounds on the size of branch-and-bound proofs for integer knapsacks
✍ Bala Krishnamoorthy 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 172 KB

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.