Optimization Online


New Turnpike Theorems for the Unbounded Knapsack Problem

Ping H. Huang(huang74***at***purdue.edu)
Thomas L. Morin(TMorin1***at***aol.com)

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 “bang-for-buck” 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 )


Download: [PDF]

Entry Submitted: 05/07/2008
Entry Accepted: 05/07/2008
Entry Last Modified: 05/07/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society