On equivalent knapsack problems
By aggregating objective function and constraint of a knapsack problem max\(\{\) c'x\(|\) a'x\(\leq b\), \(x\geq 0\) integral\(\}\) an equivalent problem of the following form is obtained: Let \(t=[c_ 1b/a_ 1]+1\) and let \(F(z)=\min \{(c+ta)'x|\) c'x\(\equiv z mod t\), \(x\geq 0\), integral\(\}\). Then z is an optimal value of the given problem if it is maximal subject to \(0\leq z<t\) and \(z+tb\geq F(z)\). Such a value z can be determined by dynamic programming with recursion: \(F(z)=\min_{j}(c_ j+ta_ j+F(z-c_ j))\). This procedure can be speeded up by calculating a recursion only for the values \(1,2,...,c_ 1-1\). Since the classical recursions use computation modulo \(a_ 1\), the new method might be advantageous if \(c_ 1<a_ 1\).
- A relation between the knapsack and group knapsack problems
- On aggregating two linear diophantine equations
- An empirical analysis of exact algorithms for the unbounded knapsack problem
- Solving the knapsack problem via \(\mathbb Z\)-transform
- New results for aggregating integer-valued equations
- When two-constraint binary knapsack problem is equivalent to classical knapsack problem?
- Minimal equivalent binary knapsack inequalities
- scientific article; zbMATH DE number 4139488 (Why is no real title available?)
- scientific article; zbMATH DE number 4143769 (Why is no real title available?)
- CONSTRUCTION OF THE F-, P-AND K-TREES OF A KNAPSAK PROBLEM AND THEIR COMPUTATIONAL EXPERIMENTS
- On Pleasant Knapsack Problems
- A New Knapsack Solution Approach by Integer Equivalent Aggregation and Consistency Determination
- scientific article; zbMATH DE number 2119958 (Why is no real title available?)
- Hard Equality Constrained Integer Knapsacks
- Integer knapsack problems with profit functions of the same value range
- A transformation of hard (equality constrained) knapsack problems into constrained shortest path problems
- An exact algorithm for large unbounded knapsack problems
This page was built for publication: On equivalent knapsack problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1082265)
