Indexed by:
Abstract:
The 0-1 linear knapsack problem with a single continuous variable (KPC) is an extension of the binary knapsack problem (KP). It is an NP-hard problem. In this paper, we show that KPC can be reduced to KP and a pseudo-knapsack problem (PKP), which is similar to the traditional knapsack problem except that the profits of items may be non-positive, and the weight sum has two sided limits on capacity. We use the Dynamic Programming algorithm COMBO (Martello et al., Manag Sci 45(3):414-424, 1999) to solve KP, and modify the branch and bound method EXPKNAP (Pisinger, Eur J Oper Res 87:175-187, 1995) for KP to solve the PKP. Numerical experiments show the efficiency of our method.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
JOURNAL OF GLOBAL OPTIMIZATION
ISSN: 0925-5001
Year: 2011
Issue: 4
Volume: 50
Page: 657-673
1 . 1 9 6
JCR@2011
1 . 3 0 0
JCR@2023
ESI Discipline: ENGINEERING;
JCR Journal Grade:1
CAS Journal Grade:2
Cited Count:
SCOPUS Cited Count: 16
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: