On equivalent knapsack problems (Q1082265): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:08, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On equivalent knapsack problems |
scientific article |
Statements
On equivalent knapsack problems (English)
0 references
1986
0 references
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\).
0 references
corner polyhedron
0 references
group knapsack
0 references
aggregating objective function and constraint
0 references
knapsack problem
0 references