  


New Turnpike Theorems for the Unbounded Knapsack Problem
Ping H. Huang(huang74purdue.edu) Abstract: We develop sharp bounds on turnpike theorems for the unbounded knapsack problem. Turnpike theorems specify when it is optimal to load at least one unit of the best item (i.e., the one with the highest “bangforbuck” ratio) and, thus can be used for problem preprocessing. The successive application of the turnpike theorems can drastically reduce the size of the knapsack problems to be solved. Two of our theorems subsume known results as special cases. The third one is an entirely different result. We show that all three theorems specify sharp bounds in the sense that no smaller bounds can be found under the assumed conditions. We also prove that two of the bounds can be obtained in constant time. Computational results on randomly generated problems demonstrate the effectiveness of the turnpike theorems both in terms of how often they can be applied and the resulting reduction in the size of the knapsack problems. Keywords: Integer Programming, Knapsack Problem, Number Theory, Preprocessing, Turnpike Theorems Category 1: Combinatorial Optimization (Other ) Category 2: Integer Programming (Other ) Citation: Download: [PDF] Entry Submitted: 05/07/2008 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  