A dynamic programming approach for consistency and propagation for knapsack constraints (Q1861937)
From MaRDI portal
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
