{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,23]],"date-time":"2025-05-23T16:10:05Z","timestamp":1748016605855,"version":"3.41.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T00:00:00Z","timestamp":1745798400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T00:00:00Z","timestamp":1745798400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Canadian Natural Sciences and Engineering Research Council","doi-asserted-by":"crossref","award":["2021-03307","2019-00094"],"award-info":[{"award-number":["2021-03307","2019-00094"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,5]]},"DOI":"10.1007\/s10878-025-01294-3","type":"journal-article","created":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T13:43:30Z","timestamp":1745847810000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A 3-space dynamic programming heuristic for the cubic knapsack problem"],"prefix":"10.1007","volume":"49","author":[{"given":"Ibrahim","family":"Dan Dije","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Franklin","family":"Djeumou Fomeni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leandro C.","family":"Coelho","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,28]]},"reference":[{"issue":"1","key":"1294_CR1","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.orl.2004.05.001","volume":"33","author":"WP Adams","year":"2005","unstructured":"Adams WP, Forrester RJ (2005) A simple recipe for concise mixed 0\u20131 linearizations. Oper Res Lett 33(1):55\u201361","journal-title":"Oper Res Lett"},{"key":"1294_CR2","volume-title":"Dynamic programming","author":"R Bellman","year":"1957","unstructured":"Bellman R (1957) Dynamic programming. Princeton University Press, Princeton"},{"issue":"2","key":"1294_CR3","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/0377-2217(94)00229-0","volume":"92","author":"A Billionnet","year":"1996","unstructured":"Billionnet A, Calmels F (1996) Linear programming for the 0\u20131 quadratic knapsack problem. Eur J Oper Res 92(2):310\u2013325","journal-title":"Eur J Oper Res"},{"key":"1294_CR4","doi-asserted-by":"crossref","unstructured":"Cacchiani V, Iori M, Locatelli A, Martello S (2022a) Knapsack problems\u2014an overview of recent advances. Part I: single knapsack problems. Comput Oper Res 143:105692","DOI":"10.1016\/j.cor.2021.105692"},{"key":"1294_CR5","doi-asserted-by":"crossref","unstructured":"Cacchiani V, Iori M, Locatelli A, Martello S (2022b) Knapsack problems-an overview of recent advances. Part II: multiple, multidimensional, and quadratic knapsack problems. Comput Oper Res 143:105693","DOI":"10.1016\/j.cor.2021.105693"},{"issue":"2","key":"1294_CR6","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1287\/ijoc.11.2.125","volume":"11","author":"A Caprara","year":"1999","unstructured":"Caprara A, Pisinger D, Toth P (1999) Exact solution of the quadratic knapsack problem. INFORMS J Comput 11(2):125\u2013137","journal-title":"INFORMS J Comput"},{"key":"1294_CR7","volume-title":"Combinatorial auctions","author":"P Cramton","year":"2010","unstructured":"Cramton P, Shoham Y, Steinberg R (2010) Combinatorial auctions. The MIT Press, Cambridge"},{"key":"1294_CR8","doi-asserted-by":"publisher","unstructured":"Dan Dije I, Djeumou\u00a0Fomeni F, Coelho LC (2025) Cubic knapsack problem instances. Mendeley Data. https:\/\/doi.org\/10.17632\/y28j8mgf8k.1","DOI":"10.17632\/y28j8mgf8k.1"},{"key":"1294_CR9","doi-asserted-by":"publisher","first-page":"1376","DOI":"10.1287\/mnsc.20.10.1376","volume":"20","author":"B Faaland","year":"1974","unstructured":"Faaland B (1974) An integer programming algorithm for portfolio selection. Manag Sci 20:1376\u20131384","journal-title":"Manag Sci"},{"key":"1294_CR10","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.ejor.2024.06.034","volume":"319","author":"ME Fennich","year":"2024","unstructured":"Fennich ME, Fomeni FD, Coelho LC (2024) A novel dynamic programming heuristic for the quadratic knapsack problem. Eur J Oper Res 319:102\u2013120","journal-title":"Eur J Oper Res"},{"key":"1294_CR11","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/j.dam.2023.02.003","volume":"335","author":"FD Fomeni","year":"2023","unstructured":"Fomeni FD (2023) A lifted-space dynamic programming algorithm for the quadratic knapsack problem. Discrete Appl Math 335:52\u201368","journal-title":"Discrete Appl Math"},{"issue":"1","key":"1294_CR12","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1287\/ijoc.2013.0555","volume":"26","author":"FD Fomeni","year":"2014","unstructured":"Fomeni FD, Letchford AN (2014) A dynamic programming heuristic for the quadratic knapsack problem. INFORMS J Comput 26(1):173\u2013182","journal-title":"INFORMS J Comput"},{"key":"1294_CR13","doi-asserted-by":"publisher","first-page":"100579","DOI":"10.1016\/j.disopt.2020.100579","volume":"44","author":"FD Fomeni","year":"2022","unstructured":"Fomeni FD, Kaparis K, Letchford AN (2022) A cut-and-branch algorithm for the quadratic knapsack problem. Discrete Optim 44:100579","journal-title":"Discrete Optim"},{"issue":"4","key":"1294_CR14","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1080\/02331934.2015.1091821","volume":"65","author":"RJ Forrester","year":"2016","unstructured":"Forrester RJ (2016) Tightening concise linear reformulations of 0\u20131 cubic programs. Optimization 65(4):877\u2013903","journal-title":"Optimization"},{"issue":"1","key":"1294_CR15","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1007\/s10878-021-00840-z","volume":"44","author":"RJ Forrester","year":"2022","unstructured":"Forrester RJ, Waddell LA (2022) Strengthening a linear reformulation of the 0\u20131 cubic knapsack problem via variable reordering. J Comb Optim 44(1):498\u2013517","journal-title":"J Comb Optim"},{"key":"1294_CR16","first-page":"132","volume":"8","author":"G Gallo","year":"1980","unstructured":"Gallo G, Hammer PL, Simeone B (1980) Quadratic knapsack problems. Combin Optim 8:132\u2013149","journal-title":"Combin Optim"},{"key":"1294_CR17","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/j.tre.2019.05.009","volume":"127","author":"F Hammami","year":"2019","unstructured":"Hammami F, Rekik M, Coelho LC (2019) Exact and heuristic solution approaches for the bid construction problem in transportation procurement auctions with a heterogeneous fleet. Transport Res Part E Logist Transport Rev 127:150\u2013177","journal-title":"Transport Res Part E Logist Transport Rev"},{"key":"1294_CR18","doi-asserted-by":"publisher","first-page":"105982","DOI":"10.1016\/j.cor.2022.105982","volume":"148","author":"F Hammami","year":"2022","unstructured":"Hammami F, Rekik M, Coelho LC (2022) An exact method for the combinatorial bids generation problem with uncertainty on clearing prices, bids success, and contracts materialization. Comput Oper Res 148:105982","journal-title":"Comput Oper Res"},{"key":"1294_CR19","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"},{"issue":"4598","key":"1294_CR20","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671\u2013680","journal-title":"Science"},{"key":"1294_CR21","first-page":"321","volume":"8","author":"DC Marinescu","year":"2018","unstructured":"Marinescu DC (2018) Cloud resource management and scheduling. Cloud Comput 8:321\u2013363","journal-title":"Cloud Comput"},{"key":"1294_CR22","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, Chichester"},{"issue":"6","key":"1294_CR23","doi-asserted-by":"publisher","first-page":"1446","DOI":"10.1109\/TCBB.2016.2595583","volume":"14","author":"S Mohammadi","year":"2016","unstructured":"Mohammadi S, Gleich DF, Kolda TG, Grama A (2016) Triangular alignment (tame): a tensor-based approach for higher-order network alignment. IEEE\/ACM Trans Comput Biol Bioinf 14(6):1446\u20131458","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"1294_CR24","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1287\/mnsc.17.5.320","volume":"17","author":"DE Peterson","year":"1971","unstructured":"Peterson DE, Laughhunn DJ (1971) Capital expenditure programming and some alternative approaches to risk. Manag Sci 17:320\u2013336","journal-title":"Manag Sci"},{"key":"1294_CR25","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1287\/ijoc.1050.0172","volume":"19","author":"D Pisinger","year":"2007","unstructured":"Pisinger D, Rasmussen A, Sandvik R (2007) Solution of large quadratic knapsack problems through aggressive reduction. INFORMS J Comput 19:280\u2013290","journal-title":"INFORMS J Comput"},{"issue":"1","key":"1294_CR26","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1002\/nav.3800220110","volume":"22","author":"HM Salkin","year":"1975","unstructured":"Salkin HM, De Kluyver CA (1975) The knapsack problem: a survey. Naval Res Logist Quart 22(1):127\u2013144","journal-title":"Naval Res Logist Quart"},{"issue":"2","key":"1294_CR27","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.ejor.2016.06.013","volume":"255","author":"J Schauer","year":"2016","unstructured":"Schauer J (2016) Asymptotic behavior of the quadratic knapsack problem. Eur J Oper Res 255(2):357\u2013363","journal-title":"Eur J Oper Res"},{"issue":"7","key":"1294_CR28","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1287\/mnsc.12.7.485","volume":"12","author":"HM Weingartner","year":"1966","unstructured":"Weingartner HM (1966) Capital budgeting of interrelated projects: survey and synthesis. Manag Sci 12(7):485\u2013516","journal-title":"Manag Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01294-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01294-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01294-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,23]],"date-time":"2025-05-23T15:34:34Z","timestamp":1748014474000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01294-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,28]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["1294"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01294-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2025,4,28]]},"assertion":[{"value":"26 March 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"60"}}