Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10523843 | Discrete Optimization | 2005 | 10 Pages |
Abstract
We consider a class of random knapsack instances described by Chvátal, who showed that with probability going to 1, such instances require an exponential number of branch-and-bound nodes. We show that even with the use of simple lifted cover inequalities, an exponential number of nodes is required with probability going to 1.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Brady Hunsaker, Craig A. Tovey,