Cost based filtering for the constrained knapsack problem

Cost based filtering for the constrained knapsack problem

0.00 Avg rating0 Votes
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: ,
Keywords: knapsack problem, constraint programming
Abstract:

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 Θ(n log n) preprocessing time and Θ(n) time per call. This sums up to an amortized time Θ(n) for Ω(log n) incremental calls where the subsequent problems may differ with respect to arbitrary sets of necessarily included and excluded items.

Reviews

Required fields are marked *. Your email address will not be published.