An exact algorithm for large unbounded knapsack problems
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.
- A better step-off algorithm for the knapsack problem
- A Linear Programming Approach to the Cutting Stock Problem—Part II
- A New Algorithm for the 0-1 Knapsack Problem
- A Polynomial Algorithm for the Two-Variable Integer Programming Problem
- A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables
- An Algorithm for Large Zero-One Knapsack Problems
- An algorithm for the solution of the 0-1 knapsack problem
- An Enumeration Algorithm for Knapsack Problems
- An upper bound for the zero-one knapsack problem and a branch and bound algorithm
- scientific article; zbMATH DE number 3427118 (Why is no real title available?)
- scientific article; zbMATH DE number 3989108 (Why is no real title available?)
- scientific article; zbMATH DE number 44282 (Why is no real title available?)
- scientific article; zbMATH DE number 3580280 (Why is no real title available?)
- scientific article; zbMATH DE number 3314878 (Why is no real title available?)
- On equivalent knapsack problems
- Some applications of the theory of dynamic programming -- a review
- The Theory and Computation of Knapsack Functions
- When the Greedy Solution Solves a Class of Knapsack Problems
- New pseudopolynomial complexity bounds for the bounded and other integer knapsack related problems
- An algorithm for the continuous variable upper bound knapsack problem
- A note on dominance relation in unbounded knapsack problems
- An empirical analysis of exact algorithms for the unbounded knapsack problem
- A constructive periodicity bound for the unbounded knapsack problem
- Exact optimization and decomposition approaches for shelf space allocation
- Complexity of solving the subset sum problem with the branch-and-bound method with domination and cardinality filtering
- Strip generation algorithms for constrained two-dimensional two-staged cutting problems
- Using 3D-printing in disaster response: the two-stage stochastic 3D-printing knapsack problem
- Algorithms for some hard knapsack problems
- Algorithms with guarantee value for knapsack problems
- The unbounded knapsack problem
- A study on the budget constrained facility location model considering inventory management cost
- Robust efficiency measures for linear knapsack problem variants
- Fractal patterns related to dividing coins
- Determining the K-best solutions of knapsack problems
- Tight bounds for periodicity theorems on the unbounded knapsack problem
- scientific article; zbMATH DE number 1264415 (Why is no real title available?)
- scientific article; zbMATH DE number 6869279 (Why is no real title available?)
- An improved branch and bound algorithm for a strongly correlated unbounded knapsack problem
- Extension of Brickell’S Algorithm for Breaking High Density Knapsacks
- A theory of auto-scaling for resource reservation in cloud services
- Unbounded knapsack problems with arithmetic weight sequences
- An approximate solution approach for a scenario-based capital budgeting model
This page was built for publication: An exact algorithm for large unbounded knapsack problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q913659)
