A dynamic programming approach for consistency and propagation for knapsack constraints (Q1861937): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 12:36, 1 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A dynamic programming approach for consistency and propagation for knapsack constraints |
scientific article |
Statements
A dynamic programming approach for consistency and propagation for knapsack constraints (English)
0 references
10 March 2003
0 references
A dynamic programming structure is suggested to represent knapsack constraints. With this structure hyper-arc consistency is achieved to determine infeasibility before all variables are set, to generate all solutions quickly, and to provide incrementality by updating the structure after domain reduction. Test cases illustrate significant reduction in branching.
0 references
global constraints
0 references
dynamic programming
0 references
knapsack constraints
0 references
