Article ID: | iaor20031611 |
Country: | Netherlands |
Volume: | 115 |
Issue: | 1 |
Start Page Number: | 73 |
End Page Number: | 93 |
Publication Date: | Sep 2002 |
Journal: | Annals of Operations Research |
Authors: | Fahle Torsten, Sellmann Meinolf |
Keywords: | knapsack problem, constraint programming |
We present cost based filtering methods for Knapsack Problems (KPs). Cost based filtering aims at fixing variables with respect to the objective function. It is an important technique when solving complex problems such as Quadratic Knapsack Problems, or KPs with additional constraints (Constrained Knapsack Problems (CKPs)). They evolve, e.g., when Constraint Based Column Generation is applied to appropriate optimization problems. We develop new reduction algorithms for KP. They are used as propagation routines for the CKP with Θ(