A Dynamic Programming Approach for Consistency and Propagation fo.pdf.pdf' (202.11 kB)
0/0

A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints

Download (202.11 kB)
journal contribution
posted on 01.01.1975 by Michael Trick
Knapsack constraints are a key modeling structure in constraint programming. These constraints are normally handled with simple bounding arguments. We propose a dynamic programming structure to represent these constraints. With this structure, we are able to achieve hyper-arc consistency, to determine infeasibility before all variables are set, to generate all solutions quickly, and to provide incrementality by updating the structure after domain reduction. Testing on a difficult set of multiple knapsack instances shows significant reduction in branching.

History

Publisher Statement

All Rights Reserved

Date

01/01/1975

Exports

Exports