logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

Cost based filtering for the constrained knapsack problem

delete2002-01-01
delete34
PRE
AI
T
Torsten Fahle *
M
Meinolf Sellmann
DOI：10.1023/A:1021193019522delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
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 Theta(n log n) preprocessing time and Theta(n) time per call. This sums up to an amortized time Theta(n) for Omega(log n) incremental calls where the subsequent problems may differ with respect to arbitrary sets of necessarily included and excluded items.
Keywords:
constraint programming
constrained knapsack problems
cost based filtering
optimization constraints
reduction algorithms
AI Summary

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.

Journal

Annals of Operations Research cover
Annals of Operations Research
IF:
4.5
Papers:
8.0K
Citations:
2.1W

Organization

No organization information available