A dynamic programming approach for consistency and propagation for knapsack constraints (Q1861937)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A dynamic programming approach for consistency and propagation for knapsack constraints |
scientific article; zbMATH DE number 1878990
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A dynamic programming approach for consistency and propagation for knapsack constraints |
scientific article; zbMATH DE number 1878990 |
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
