{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T21:16:43Z","timestamp":1776374203901,"version":"3.51.2"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,7,18]],"date-time":"2018-07-18T00:00:00Z","timestamp":1531872000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,7,18]],"date-time":"2018-07-18T00:00:00Z","timestamp":1531872000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"DICYT ,Scientific and Technological Research Office, University of Santiago of Chile"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cent Eur J Oper Res"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s10100-018-0569-0","type":"journal-article","created":{"date-parts":[[2018,7,19]],"date-time":"2018-07-19T04:23:06Z","timestamp":1531974186000},"page":"589-609","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Complexity indices for the multidimensional knapsack problem"],"prefix":"10.1007","volume":"29","author":[{"given":"Ivan","family":"Derpich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlos","family":"Herrera","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felipe","family":"Sep\u00falveda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hugo","family":"Ubilla","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,7,18]]},"reference":[{"issue":"11","key":"569_CR22","doi-asserted-by":"publisher","first-page":"2017","DOI":"10.1016\/j.cor.2010.02.002","volume":"37","author":"E Angelelli","year":"2010","unstructured":"Angelelli E, Mansini R, Speranza MG, Grazia (2010) Kernel search: a general heuristic for the multi-dimensional knapsack problem. Comput Oper Res 37(11):2017\u20132026. https:\/\/doi.org\/10.1016\/j.cor.2010.02.002","journal-title":"Comput Oper Res"},{"issue":"11","key":"569_CR1","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1057\/jors.1990.166","volume":"41","author":"JE Beasley","year":"1990","unstructured":"Beasley JE (1990) OR-Library: distributing test problems by electronic mail. J Oper Res Soc 41(11):1069\u20131072. https:\/\/doi.org\/10.1057\/jors.1990.166","journal-title":"J Oper Res Soc"},{"issue":"5","key":"569_CR23","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1080\/00207540210163892","volume":"41","author":"A Bolat","year":"2003","unstructured":"Bolat A (2003) A mathematical model for selecting mixed models with due dates. Int J Prod Res 41(5):897\u2013918. https:\/\/doi.org\/10.1080\/00207540210163892","journal-title":"Int J Prod Res"},{"issue":"2","key":"569_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.dam.2009.08.007","volume":"158","author":"S Boussier","year":"2010","unstructured":"Boussier S, Vasquez M, Vimont Y, Hanafi S, Michelon P (2010) A multilevel search strategy for the 0\u20131 multidimensional knapsack problem. Discrete Appl Math 158(2):97\u2013109","journal-title":"Discrete Appl Math"},{"key":"569_CR3","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.jmsy.2008.07.001","volume":"27","author":"N Cherbaka","year":"2008","unstructured":"Cherbaka N, Meller R (2008) Single-plant sourcing decisions with a multidimensional knapsack model. J Manuf Syst 27:7\u201318. https:\/\/doi.org\/10.1016\/j.jmsy.2008.07.001","journal-title":"J Manuf Syst"},{"issue":"1","key":"569_CR4","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1023\/A:1009642405419","volume":"4","author":"PC Chu","year":"1998","unstructured":"Chu PC, Beasley JE (1998) A genetic algorithm for the multidimensional knapsack problem. J Heuristics 4(1):63\u201386. https:\/\/doi.org\/10.1023\/A:1009642405419","journal-title":"J Heuristics"},{"issue":"1","key":"569_CR5","first-page":"35","volume":"1","author":"D Cvetkovic","year":"2012","unstructured":"Cvetkovic D (2012) Complexity indices for the travelling salesman problem and data mining. Trans Comb 1(1):35\u201343","journal-title":"Trans Comb"},{"key":"569_CR6","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1287\/moor.28.4.625.20509","volume":"28","author":"R Freund","year":"2003","unstructured":"Freund R, Vera J (2003) On the complexity of estimating condition measures for conic convex optimization. Math Oper Res 28:625\u2013664","journal-title":"Math Oper Res"},{"issue":"3","key":"569_CR7","first-page":"95","volume":"10","author":"J Grand\u00f3n","year":"2011","unstructured":"Grand\u00f3n J, Derpich I (2011) A heuristic for the multi-knapsack problem. WSEAS Trans Math 10(3):95\u2013104","journal-title":"WSEAS Trans Math"},{"key":"569_CR8","doi-asserted-by":"publisher","first-page":"2329","DOI":"10.1093\/ietisy\/e88-d.10.2329","volume":"10","author":"RJ James","year":"2005","unstructured":"James RJ, Nakagawa Y (2005) Enumeration methods for repeatedly solving multidimensional knapsack sub-problems. IEICE Trans Inf Syst 10:2329\u20132340","journal-title":"IEICE Trans Inf Syst"},{"key":"569_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin"},{"key":"569_CR10","series-title":"Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/3-540-16486-3_99","volume-title":"Structure in complexity theory","author":"K Ko","year":"1986","unstructured":"Ko K, Orponen P, Schoning U, Watanabe O (1986) What is a hard instance of a computational problem? In: Selman AL (ed) Structure in complexity theory. Lecture notes in computer science. Springer, Berlin, pp 197\u2013217. https:\/\/doi.org\/10.1007\/3-540-16486-3_99"},{"issue":"3","key":"569_CR11","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1504\/IJMOR.2012.046684","volume":"4","author":"M Lalami","year":"2012","unstructured":"Lalami M, Elkihel M, Baz D, Boyer V (2012) A procedure-based heuristic for 0\u20131 multiple knapsack problems. Int J Math Oper Res 4(3):214\u2013224","journal-title":"Int J Math Oper Res"},{"issue":"3","key":"569_CR12","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0377-2217(84)90286-8","volume":"16","author":"M Magazine","year":"1984","unstructured":"Magazine M, Oguz O (1984) A heuristic algorithm for the multidimensional zero-one knapsack problem. Eur J Oper Res 16(3):319\u2013326","journal-title":"Eur J Oper Res"},{"issue":"8","key":"569_CR13","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1057\/palgrave.jors.260140","volume":"53","author":"R Mansini","year":"2002","unstructured":"Mansini R, Speranza MG (2002) A multidimensional knapsack model for asset-backed securitization. J Oper Res Soc 53(8):822\u2013832. https:\/\/doi.org\/10.1057\/palgrave.jors.260140","journal-title":"J Oper Res Soc"},{"issue":"3","key":"569_CR14","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1287\/ijoc.1110.0460","volume":"24","author":"R Mansini","year":"2012","unstructured":"Mansini R, Speranza M (2012) CORAL: an exact algorithm for the multidimensional knapsack problem. INFORMS J Comput 24(3):399\u2013415. https:\/\/doi.org\/10.1287\/ijoc.1110.0460","journal-title":"INFORMS J Comput"},{"issue":"1","key":"569_CR15","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0377-2217(99)00260-X","volume":"123","author":"S Martello","year":"2000","unstructured":"Martello S, Pisinger D, Toth P (2000) New trends in exact algorithms for the 0\u20131 knapsack problem. Eur J Oper Res 123(1):325\u2013332","journal-title":"Eur J Oper Res"},{"key":"569_CR16","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0377-2217(94)00344-0","volume":"91","author":"BD Reyck","year":"1996","unstructured":"Reyck BD, Herroelen W (1996) On the use of the complexity index as a measure of complexity in activity networks. Eur J Oper Res 91:347\u2013366","journal-title":"Eur J Oper Res"},{"key":"569_CR17","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1287\/mnsc.15.4.B196","volume":"15","author":"S Senju","year":"1968","unstructured":"Senju S, Toyoda Y (1968) An approach to linear programming with 0\u20131 variables. Manag Sci 15:196\u2013207","journal-title":"Manag Sci"},{"key":"569_CR18","doi-asserted-by":"crossref","unstructured":"Song Y, Zhang C, Fang Y (2008). Multiple multidimensional knapsack problem and its applications in cognitive radio networks. In: Military communications conference IEEE","DOI":"10.1109\/MILCOM.2008.4753629"},{"issue":"4","key":"569_CR19","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1137\/040609264","volume":"16","author":"J Vera","year":"2006","unstructured":"Vera J, Derpich I (2006) Incorporating condition measures in the context of combinatorial optimization. SIAM J Optim 16(4):965\u2013985","journal-title":"SIAM J Optim"},{"issue":"1","key":"569_CR20","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1057\/palgrave.jors.2602102","volume":"58","author":"A Volgenant","year":"2007","unstructured":"Volgenant A, Zwiers I (2007) Partial enumeration in heuristics for some combinatorial optimization problems. J Oper Res Soc 58(1):73\u201379. https:\/\/doi.org\/10.1057\/palgrave.jors.2602102","journal-title":"J Oper Res Soc"},{"key":"569_CR21","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/j.ejor.2008.11.036","volume":"199","author":"C Wilbaut","year":"2009","unstructured":"Wilbaut C, Salhi S, Hanafi S (2009) An iterative variable-based fixation heuristic for the 0\u20131 multidimensional knapsack problem. Eur J Oper Res 199:339\u2013348","journal-title":"Eur J Oper Res"}],"container-title":["Central European Journal of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-018-0569-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10100-018-0569-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-018-0569-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,25]],"date-time":"2021-04-25T03:19:48Z","timestamp":1619320788000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10100-018-0569-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,18]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["569"],"URL":"https:\/\/doi.org\/10.1007\/s10100-018-0569-0","relation":{},"ISSN":["1435-246X","1613-9178"],"issn-type":[{"value":"1435-246X","type":"print"},{"value":"1613-9178","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,18]]},"assertion":[{"value":"18 July 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}