.png){kind=icon}
Return
A new polynomial time algorithm for 0-1 multiple knapsack problem based on dominant principles
.png){kind=icon}
PRE
AI
DOI：10.1016/j.amc.2007.10.045.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper presents a heuristic to solve the 0-1 multi-constrained knapsack problem (01MKP) which is NP-hard. In this heuristic the dominance property of the constraints is exploited to reduce the search space to find near optimal solutions of 01MKP. This heuristic is tested for 10 benchmark problems of sizes up to 105 and for seven classical problems of sizes up to 500, taken from the literature and the results are compared with optimum solutions. Space and computational complexity of solving 01MKP using this approach are also presented. The encouraging results especially for relatively large size test problems indicate that this heuristic can successfully be used for finding good solutions for highly constrained NP-hard problems. (c) 2008 Elsevier Inc. All rights reserved.
Keywords:
0-1 multi-constrained knapsack problem
heuristic
computational complexity
NP-hard problems
Journal
IF:
3.4
Papers:
2.3W
Citations:
3.3W
Organization
Cited Papers
.png){kind=icon}
ShareSaveShareSave
Patient personality and mortality: A 4-year prospective examination of chronic renal insufficiency.
PREAI
ShareSave
View more