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

Unbounded knapsack problem: Dynamic programming revisited

delete2000-06-01
delete108
PRE
AI
R
Rumen Andonov *
P
Poirriez, V
S
Sanjay Rajopadhye
DOI：10.1016/S0377-2217(99)00265-9delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
We present EDUK, an efficient dynamic programming algorithm for the unbounded knapsack problem. It is based primarily on a new and useful dominance relation, called threshold dominance, which is a strict generalization of all the previously known dominance relations. We show that combining it with a sparse representation of the iteration domain and the periodicity property leads to a drastic reduction of the solution space. We present computational experiments with various data instances to validate our ideas and demonstrate the efficiency of EDUK vis-a-vis the well-known exact algorithm MTU2. (C) 2000 Elsevier Science B.V. All rights reserved.
Keywords:
integer programming
dominances
dynamic programming
periodicity
combinatorial optimization
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

European Journal of Operational Research cover
European Journal of Operational Research
IF:
6
Papers:
2.2W
Citations:
6.4W

Organization

No organization information available