{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:21:58Z","timestamp":1740140518180,"version":"3.37.3"},"reference-count":19,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["11971091","11701062"],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005047","name":"Liaoning Natural Science Foundation","doi-asserted-by":"crossref","award":["2019-MS-062","2020-BS-076"],"id":[{"id":"10.13039\/501100005047","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2021,12]]},"abstract":" In this paper, we propose a fast algorithm based on a new algorithm to calculate the upper bound for the knapsack problem with conflict graph (KPCG). The KPCG is an extension of the 0-1 knapsack problem. A pre-defined conflict graph defines the incompatibility properties between pairs of items. The goal is to determine which items should be packed into the knapsack to maximize the total profit on the premise of satisfying the capacity constraint and the incompatibility constraints. The experimental results show that for the graph with density greater than or equal to 0.1, the branch-and-bound algorithm based on the new algorithm is 1.6458 and 1.6352 times faster than the state-of-the-art algorithm on random and correlated instances, respectively, and can achieve speedups of up to 4.6477 for some low density instances. Moreover, the branch-and-bound algorithm based on the new algorithm can optimally solve more instances than the state-of-the-art algorithm in a given time limit. <\/jats:p>","DOI":"10.1142\/s021759592150010x","type":"journal-article","created":{"date-parts":[[2021,2,10]],"date-time":"2021-02-10T10:18:34Z","timestamp":1612952314000},"source":"Crossref","is-referenced-by-count":3,"title":["A Fast Algorithm for Knapsack Problem with Conflict Graph"],"prefix":"10.1142","volume":"38","author":[{"given":"Jiaxin","family":"Li","sequence":"first","affiliation":[{"name":"Software School, Dalian University of Technology, Dalian, P. R. China"}]},{"given":"Yan","family":"Lan","sequence":"additional","affiliation":[{"name":"Dalian Minzu University, Dalian, P. R. China"}]},{"given":"Feng","family":"Chen","sequence":"additional","affiliation":[{"name":"Software Technology Research Laboratory, De Montfort University, UK"}]},{"given":"Xin","family":"Han","sequence":"additional","affiliation":[{"name":"Software School, Dalian University of Technology, Dalian, P. R. China"}]},{"given":"Jacek","family":"Blazewicz","sequence":"additional","affiliation":[{"name":"Institute of Computing Science, Pozna\u0144 University of Technology, Pozna\u0144, Poland"},{"name":"Institute of Bioorganic Chemistry, Polish Academy of Sciences, Pozna\u0144, Poland"},{"name":"European Center for Bioinformatics and Genomics, Pozna\u0144, Poland"}]}],"member":"219","published-online":{"date-parts":[[2021,3,25]]},"reference":[{"key":"S021759592150010XBIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2011.01.019"},{"key":"S021759592150010XBIB002","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2016.0742"},{"key":"S021759592150010XBIB003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-99849-7"},{"key":"S021759592150010XBIB004","first-page":"67","volume":"173","author":"Diestel R","year":"2000","journal-title":"Mathematical Gazette"},{"key":"S021759592150010XBIB005","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"key":"S021759592150010XBIB006","doi-asserted-by":"publisher","DOI":"10.1007\/BF00226291"},{"key":"S021759592150010XBIB007","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0395-5"},{"volume-title":"Knapsack Problems","year":"2004","author":"Hans K","key":"S021759592150010XBIB008"},{"key":"S021759592150010XBIB009","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-012-0042-3"},{"key":"S021759592150010XBIB010","doi-asserted-by":"publisher","DOI":"10.1080\/0305215X.2013.819096"},{"key":"S021759592150010XBIB011","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2602046"},{"key":"S021759592150010XBIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.10.004"},{"key":"S021759592150010XBIB013","doi-asserted-by":"publisher","DOI":"10.1504\/IJOR.2012.044026"},{"key":"S021759592150010XBIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"S021759592150010XBIB016","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.03.020"},{"key":"S021759592150010XBIB017","unstructured":"Martelo, S and P Toth , (1990). Knapsack Problems. New York: Wiley p. 306."},{"key":"S021759592150010XBIB018","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00186"},{"key":"S021759592150010XBIB019","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1120.0499"},{"key":"S021759592150010XBIB020","first-page":"2864","volume":"43","author":"Yamada T","year":"2002","journal-title":"Information Processing Society of Japan Journal"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021759592150010X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,16]],"date-time":"2021-11-16T12:58:28Z","timestamp":1637067508000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S021759592150010X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,25]]},"references-count":19,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["10.1142\/S021759592150010X"],"URL":"https:\/\/doi.org\/10.1142\/s021759592150010x","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"type":"print","value":"0217-5959"},{"type":"electronic","value":"1793-7019"}],"subject":[],"published":{"date-parts":[[2021,3,25]]}}}