An exact algorithm for large unbounded knapsack problems (Q913659)

The authors give upper bounds for the objective function of the problem \[ \max \sum p_ jx_ j,\text{ subject to }\sum w_ jx_ j\leq c, \] where \(x_ j\geq 0\) and integer. The bounds are obtained by careful use of the three largest ratios \(p_ j/w_ j\). A branch and bound algorithm based on earlier results of the authors [Adv. Oper. Res., Proc. 2nd Eur. Congr., Stockholm 1976, 295-301 (1977; Zbl 0372.90094)] takes into accunt the fact that in the most cases only a small subset of the variables are nonzero in the optimal solution. Computational experiments with correlated and uncorrelated uniformly random data show the high efficiency of the presented method, for example, the average running time for problems with 250.000 variables is about 66 seconds.