×

zbMATH — the first resource for mathematics

A dynamic programming approach for consistency and propagation for knapsack constraints. (English) Zbl 1027.90075
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.

MSC:
90C27 Combinatorial optimization
90C39 Dynamic programming
PDF BibTeX XML Cite
Full Text: DOI