Cost Based Filtering for the Constrained Knapsack Problem
Cost Based Filtering for the Constrained Knapsack Problem
复制标题
约束背包问题的基于成本的过滤
DOI：
--
复制
发表时间：
2002
影响因子：
4.8
通讯作者：
Meinolf Sellmann
中科院分区：
文献类型：
--
作者：
Torsten Fahle;Meinolf Sellmann
我们提出了基于成本的背包问题（KPs）的过滤方法。基于成本的过滤旨在相对于目标函数固定变量。它是解决诸如二次背包问题或具有附加约束的KPs（约束背包问题（CKPs））等复杂问题时的重要技术。他们进化，例如，当基于约束的列生成应用于适当的优化问题时。我们开发新的约简算法KP。它们被用作CKP的传播例程，具有Θ（nlog n）预处理时间和每次调用的Θ（n）时间。这总计为Ω（log n）增量调用的摊销时间Θ（n），其中后续问题可能相对于必然包括和排除的项目的任意集合而不同。
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 Θ(nlog 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.