HEURISTIC AND REDUCTION ALGORITHMS FOR THE KNAPSACK SHARING PROBLEM

Authors
YAMADA T FUTAKAWA M
Citation
T. Yamada et M. Futakawa, HEURISTIC AND REDUCTION ALGORITHMS FOR THE KNAPSACK SHARING PROBLEM, Computers & operations research, 24(10), 1997, pp. 961-967
Citations number
10
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science","Computer Science Interdisciplinary Applications","Engineering, Industrial
Journal title
Computers & operations research → ACNP
ISSN journal
03050548
Volume
24
Issue
10
Year of publication
1997
Pages
961 - 967
Database
ISI
SICI code
0305-0548(1997)24:10<961:HARAFT>2.0.ZU;2-D
Abstract
KSP is newly formulated as an extension of the knapsack problem. KSP i s NP-hard, and we give a fast algorithm to find an upper bound to this problem. Based on this we develop a heuristic algorithm to solve KSP approximately. Also, a pegging test is derived that enables us to redu ce the size of the original problem. Computational experiments are car ried out to examine the behavior of the developed algorithms for sever al instance types of different statistical characteristics. (C) 1997 E lsevier Science Ltd.