• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Lin, Geng (Lin, Geng.) [1] | Zhu, Wenxing (Zhu, Wenxing.) [2] (Scholars:朱文兴) | Ali, M. M. (Ali, M. M..) [3]

Indexed by:

EI Scopus SCIE

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:

Branch and bound Knapsack problem Mixed integer programming

Community:

  • [ 1 ] [Lin, Geng]Fuzhou Univ, Ctr Discrete Math & Theoret Comp Sci, Fuzhou 350108, Peoples R China
  • [ 2 ] [Zhu, Wenxing]Fuzhou Univ, Ctr Discrete Math & Theoret Comp Sci, Fuzhou 350108, Peoples R China
  • [ 3 ] [Ali, M. M.]Univ Witwatersrand, Sch Computat & Appl Math, ZA-2050 Johannesburg, South Africa

Reprint 's Address:

  • 朱文兴

    [Zhu, Wenxing]Fuzhou Univ, Ctr Discrete Math & Theoret Comp Sci, Fuzhou 350108, Peoples R China

Show more details

Related Keywords:

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:

WoS CC 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

Online/Total:135/10131752
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1