{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T12:48:19Z","timestamp":1776775699858,"version":"3.51.2"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2016,12,23]],"date-time":"2016-12-23T00:00:00Z","timestamp":1482451200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soft Comput"],"published-print":{"date-parts":[[2018,3]]},"DOI":"10.1007\/s00500-016-2465-7","type":"journal-article","created":{"date-parts":[[2016,12,24]],"date-time":"2016-12-24T11:06:59Z","timestamp":1482577619000},"page":"2025-2043","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Optimization algorithms for the disjunctively constrained knapsack problem"],"prefix":"10.1007","volume":"22","author":[{"given":"Mariem","family":"Ben Salem","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raouia","family":"Taktak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1079-1892","authenticated-orcid":false,"given":"A. Ridha","family":"Mahjoub","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Han\u00eane","family":"Ben-Abdallah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,23]]},"reference":[{"issue":"4","key":"2465_CR1","doi-asserted-by":"crossref","first-page":"811","DOI":"10.1016\/j.cie.2011.01.019","volume":"60","author":"H Akeb","year":"2011","unstructured":"Akeb H, Hifi M, Mounir MEOA (2011) Local branching-based algorithms for the disjunctively constrained knapsack problem. Comput Ind Eng 60(4):811\u2013820","journal-title":"Comput Ind Eng"},{"key":"2465_CR2","doi-asserted-by":"crossref","unstructured":"Atamt\u00fcrk A, Narayanan V (2009) The submodular knapsack polytope. Discrete Optim 6(4):333\u2013344","DOI":"10.1016\/j.disopt.2009.03.002"},{"issue":"1","key":"2465_CR3","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1007\/BF01580440","volume":"8","author":"E Balas","year":"1975","unstructured":"Balas E (1975) Facets of the knapsack polytope. Math Program 8(1):146\u2013164","journal-title":"Math Program"},{"issue":"1","key":"2465_CR4","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1137\/0134010","volume":"34","author":"E Balas","year":"1978","unstructured":"Balas E, Zemel E (1978) Facets of the knapsack polytope from minimal covers. SIAM J Appl Math 34(1):119\u2013148","journal-title":"SIAM J Appl Math"},{"key":"2465_CR5","unstructured":"Bettinelli A, Cacchiani V, Malaguti E (2014) Bounds and algorithms for the knapsack problem with conflict graph. Tech. rep., Technical Report OR-14-16, DEIS\u2013University of Bologna, Bologna, Italy"},{"issue":"3","key":"2465_CR6","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0166-218X(90)90053-F","volume":"41","author":"EA Boyd","year":"1993","unstructured":"Boyd EA (1993) Polyhedral results for the precedence-constrained knapsack problem. Discrete Appl Math 41(3):185\u2013201","journal-title":"Discrete Appl Math"},{"issue":"5","key":"2465_CR7","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1287\/opre.31.5.803","volume":"31","author":"H Crowder","year":"1983","unstructured":"Crowder H, Johnson EL, Padberg M (1983) Solving large-scale zero-one linear programming problems. Oper Res 31(5):803\u2013834","journal-title":"Oper Res"},{"issue":"3","key":"2465_CR8","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1287\/moor.12.3.451","volume":"12","author":"R Euler","year":"1987","unstructured":"Euler R, J\u00fcnger M, Reinelt G (1987) Generalizations of cliques, odd cycles and anticycles and their relation to independence system polyhedra. Math Oper Res 12(3):451\u2013462","journal-title":"Math Oper Res"},{"issue":"3","key":"2465_CR9","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/s10107-003-0420-8","volume":"96","author":"IR Farias Jr de","year":"2003","unstructured":"de Farias Jr IR, Nemhauser GL (2003) A polyhedral study of the cardinality constrained knapsack problem. Math Program 96(3):439\u2013467","journal-title":"Math Program"},{"issue":"4","key":"2465_CR10","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1016\/S0167-6377(02)00124-4","volume":"30","author":"V Gabrel","year":"2002","unstructured":"Gabrel V, Minoux M (2002) A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems. Oper Res Lett 30(4):252\u2013264","journal-title":"Oper Res Lett"},{"key":"2465_CR11","volume-title":"Computers and intractability: a guide to the theory of np-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of np-completeness. Freeman, San Francisco"},{"key":"2465_CR12","volume-title":"Geometric algorithms and combinatorial optimization","author":"M Gr\u00f6tschel","year":"2012","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A (2012) Geometric algorithms and combinatorial optimization. Springer, Berlin"},{"issue":"4","key":"2465_CR13","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1287\/ijoc.10.4.427","volume":"10","author":"Z Gu","year":"1998","unstructured":"Gu Z, Nemhauser GL, Savelsbergh MW (1998) Lifted cover inequalities for 0\u20131 integer programs: computation. INFORMS J Comput 10(4):427\u2013437","journal-title":"INFORMS J Comput"},{"issue":"1","key":"2465_CR14","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BF01580442","volume":"8","author":"PL Hammer","year":"1975","unstructured":"Hammer PL, Johnson EL, Peled UN (1975) Facet of regular 0\u20131 polytopes. Math Program 8(1):179\u2013206","journal-title":"Math Program"},{"issue":"1","key":"2465_CR15","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.ejor.2006.03.046","volume":"179","author":"S Hanafi","year":"2007","unstructured":"Hanafi S, Glover F (2007) Exploiting nested inequalities and surrogate constraints. Eur J Oper Res 179(1):50\u201363","journal-title":"Eur J Oper Res"},{"issue":"9","key":"2465_CR16","doi-asserted-by":"crossref","first-page":"2657","DOI":"10.1016\/j.cor.2005.10.004","volume":"34","author":"M Hifi","year":"2007","unstructured":"Hifi M, Michrafy M (2007) Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem. Comput Oper Res 34(9):2657\u20132673","journal-title":"Comput Oper Res"},{"key":"2465_CR17","doi-asserted-by":"crossref","unstructured":"Hifi M, Negre S, Mounir MQA (2009) Local branching-based algorithm for the disjunctively constrained knapsack problem. In: IEEE international conference on computers and industrial engineering, 2009. pp 279\u2013284","DOI":"10.1109\/ICCIE.2009.5223682"},{"key":"2465_CR18","doi-asserted-by":"crossref","unstructured":"Hifi M, Negre S, Saadi T, Saleh S, Wu L (2014) A parallel large neighborhood search-based heuristic for the disjunctively constrained knapsack problem. In: IEEE international processing symposium workshops (IPDPSW) parallel and distributed, pp 1547\u20131551","DOI":"10.1109\/IPDPSW.2014.173"},{"key":"2465_CR19","doi-asserted-by":"crossref","unstructured":"Hifi M, Otmani N (2011) A first level scatter search for disjunctively constrained knapsack problems. In: IEEE international conference on communications, computing and control applications (CCCA). pp 1\u20136","DOI":"10.1109\/CCCA.2011.6031544"},{"key":"2465_CR20","doi-asserted-by":"crossref","unstructured":"Hifi M, Saleh S, Wu L, Chen J (2015) A hybrid guided neighborhood search for the disjunctively constrained knapsack problem. Cogent Eng 2(1):1068,969","DOI":"10.1080\/23311916.2015.1068969"},{"issue":"1","key":"2465_CR21","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.ejor.2007.01.032","volume":"186","author":"K Kaparis","year":"2008","unstructured":"Kaparis K, Letchford AN (2008) Local and global lifted cover inequalities for the 0\u20131 multidimensional knapsack problem. Eur J Oper Res 186(1):91\u2013103","journal-title":"Eur J Oper Res"},{"key":"2465_CR22","doi-asserted-by":"crossref","unstructured":"Kaparis K, Letchford AN (2010a) Cover inequalities. Wiley Encyclopedia of Operations Research and Management Science","DOI":"10.1002\/9780470400531.eorms0204"},{"issue":"1\u20132","key":"2465_CR23","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/s10107-010-0359-5","volume":"124","author":"K Kaparis","year":"2010","unstructured":"Kaparis K, Letchford AN (2010b) Separation algorithms for 0\u20131 knapsack polytopes. Math Program 124(1\u20132):69\u201391","journal-title":"Math Program"},{"issue":"1","key":"2465_CR24","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/S0167-6377(98)00025-X","volume":"23","author":"D Klabjan","year":"1998","unstructured":"Klabjan D, Nemhauser GL, Tovey C (1998) The complexity of cover inequality separation. Oper Res Lett 23(1):35\u201340","journal-title":"Oper Res Lett"},{"key":"2465_CR25","unstructured":"Mahjoub AR (2010) Polyhedral approaches. In: Paschos V (ed) Concepts of combinatorial optimization. ISTE-Wiely, pp 261\u2013324"},{"key":"2465_CR26","volume-title":"Dynamic programming and tight bounds for the 0\u20131 knapsack problem","author":"S Martello","year":"1997","unstructured":"Martello S, Pisinger D, Toth P (1997) Dynamic programming and tight bounds for the 0\u20131 knapsack problem. K\u00f8benhavns Universitet, Datalogisk Institut"},{"key":"2465_CR27","volume-title":"Knapsack problems: algorithms and computer implementations","author":"S Martello","year":"1990","unstructured":"Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, New York"},{"issue":"5","key":"2465_CR28","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1057\/jors.1992.71","volume":"43","author":"G Nemhauser","year":"1992","unstructured":"Nemhauser G, Sigismondi G (1992) A strong cutting plane\/branch-and-bound algorithm for node packing. J Oper Res Soc 43(5):443\u2013457","journal-title":"J Oper Res Soc"},{"issue":"1","key":"2465_CR29","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1007\/BF01580222","volume":"6","author":"GL Nemhauser","year":"1974","unstructured":"Nemhauser GL, Trotter LE Jr (1974) Properties of vertex packing and independence system polyhedra. Math Program 6(1):48\u201361","journal-title":"Math Program"},{"issue":"2","key":"2465_CR30","doi-asserted-by":"crossref","first-page":"233","DOI":"10.7155\/jgaa.00186","volume":"13","author":"U Pferschy","year":"2009","unstructured":"Pferschy U, Schauer J (2009) The knapsack problem with conflict graphs. J Graph Algorithms Appl 13(2):233\u2013249","journal-title":"J Graph Algorithms Appl"},{"issue":"4","key":"2465_CR31","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1287\/opre.47.4.570","volume":"47","author":"D Pisinger","year":"1999","unstructured":"Pisinger D (1999) Core problems in knapsack algorithms. Oper Res 47(4):570\u2013575","journal-title":"Oper Res"},{"issue":"2","key":"2465_CR32","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1287\/ijoc.1120.0499","volume":"25","author":"R Sadykov","year":"2013","unstructured":"Sadykov R, Vanderbeck F (2013) Bin packing with conflicts: a generic branch-and-price algorithm. INFORMS J Comput 25(2):244\u2013255","journal-title":"INFORMS J Comput"},{"key":"2465_CR33","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A Schrijver","year":"2002","unstructured":"Schrijver A (2002) Combinatorial optimization: polyhedra and efficiency. Springer, Berlin"},{"key":"2465_CR34","unstructured":"Senisuka A, You B, Yamada T (2005) Reduction and exact algorithms for the disjunctively constrained knapsack problem. In: International symposium, operational research Bremen"},{"issue":"1","key":"2465_CR35","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1287\/opre.35.1.45","volume":"35","author":"TJ Roy Van","year":"1987","unstructured":"Van Roy TJ, Wolsey LA (1987) Solving mixed integer programming problems using automatic reformulation. Oper Res 35(1):45\u201357","journal-title":"Oper Res"},{"issue":"3","key":"2465_CR36","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF02614517","volume":"77","author":"R Weismantel","year":"1997","unstructured":"Weismantel R (1997) On the 0\/1 knapsack polytope. Math Program 77(3):49\u201368","journal-title":"Math Program"},{"issue":"1","key":"2465_CR37","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/BF01580441","volume":"8","author":"LA Wolsey","year":"1975","unstructured":"Wolsey LA (1975) Faces for a linear inequality in 0\u20131 variables. Math Program 8(1):165\u2013178","journal-title":"Math Program"},{"key":"2465_CR38","volume-title":"Integer and combinatorial optimization","author":"LA Wolsey","year":"1999","unstructured":"Wolsey LA, Nemhauser GL (1999) Integer and combinatorial optimization. Wiley-Interscience, New York"},{"key":"2465_CR39","unstructured":"Yamada T, Kataoka S, Watanabe K (2002) Heuristic and exact algorithms for the disjunctively constrained knapsack problem. Inform Proces Soc Jpn J 43(9)"},{"issue":"4","key":"2465_CR40","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1287\/moor.14.4.760","volume":"14","author":"E Zemel","year":"1989","unstructured":"Zemel E (1989) Easily computable facets of the knapsack polytope. Math Oper Res 14(4):760\u2013764","journal-title":"Math Oper Res"},{"issue":"2","key":"2465_CR41","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/j.disopt.2010.09.005","volume":"8","author":"B Zeng","year":"2011","unstructured":"Zeng B, Richard JPP (2011) A polyhedral study on 0\u20131 knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting. Discrete Optim 8(2):277\u2013301","journal-title":"Discrete Optim"}],"container-title":["Soft Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00500-016-2465-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-016-2465-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-016-2465-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,16]],"date-time":"2019-09-16T18:37:58Z","timestamp":1568659078000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00500-016-2465-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,23]]},"references-count":41,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["2465"],"URL":"https:\/\/doi.org\/10.1007\/s00500-016-2465-7","relation":{},"ISSN":["1432-7643","1433-7479"],"issn-type":[{"value":"1432-7643","type":"print"},{"value":"1433-7479","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,23]]}}}