{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T19:42:58Z","timestamp":1781379778647,"version":"3.54.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T00:00:00Z","timestamp":1724284800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T00:00:00Z","timestamp":1724284800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["CGS D - 578589"],"award-info":[{"award-number":["CGS D - 578589"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s10107-024-02133-9","type":"journal-article","created":{"date-parts":[[2024,8,23]],"date-time":"2024-08-23T14:49:16Z","timestamp":1724424556000},"page":"847-879","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints"],"prefix":"10.1007","volume":"210","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0546-4774","authenticated-orcid":false,"given":"Noah","family":"Weninger","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8785-5906","authenticated-orcid":false,"given":"Ricardo","family":"Fukasawa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,8,22]]},"reference":[{"key":"2133_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejco.2021.100007","volume":"9","author":"T Kleinert","year":"2021","unstructured":"Kleinert, T., Labb\u00e9, M., Ljubi\u0107, I., Schmidt, M.: A survey on mixed-integer programming techniques in bilevel optimization. EURO J. Comput. Optim. 9, 100007 (2021)","journal-title":"EURO J. Comput. Optim."},{"key":"2133_CR2","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/978-3-030-52119-6_20","volume-title":"Bilevel Optimization: Advances and Next Challenges","author":"S Dempe","year":"2020","unstructured":"Dempe, S.: Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography. In: Dempe, S., Zemkoho, A. (eds.) Bilevel Optimization: Advances and Next Challenges, pp. 581\u2013672. Springer, Cham (2020)"},{"issue":"3","key":"2133_CR3","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1016\/j.ejor.2019.06.024","volume":"283","author":"JC Smith","year":"2020","unstructured":"Smith, J.C., Song, Y.: A survey of network interdiction models and algorithms. Eur. J. Oper. Res. 283(3), 797\u2013811 (2020)","journal-title":"Eur. J. Oper. Res."},{"key":"2133_CR4","unstructured":"DeNegre, S.: Interdiction and discrete bilevel linear programming. PhD thesis, Lehigh University (2011)"},{"issue":"2","key":"2133_CR5","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1137\/130906593","volume":"24","author":"A Caprara","year":"2014","unstructured":"Caprara, A., Carvalho, M., Lodi, A., Woeginger, G.J.: A study on the computational complexity of the bilevel knapsack problem. SIAM J. Optim. 24(2), 823\u2013838 (2014)","journal-title":"SIAM J. Optim."},{"key":"2133_CR6","volume-title":"The Theory of the Market Economy","author":"H Von Stackelberg","year":"1952","unstructured":"Von Stackelberg, H.: The Theory of the Market Economy. Oxford University Press, England (1952)"},{"key":"2133_CR7","unstructured":"Chen, L., Wu, X., Zhang, G.: Approximation algorithms for interdiction problem with packing constraints. arXiv preprint arXiv:2204.11106 (2022)"},{"key":"2133_CR8","doi-asserted-by":"publisher","first-page":"2271","DOI":"10.1016\/j.cor.2004.03.002","volume":"32","author":"D Pisinger","year":"2005","unstructured":"Pisinger, D.: Where are the hard knapsack problems? Comput. Operations Res. 32, 2271\u20132284 (2005)","journal-title":"Comput. Operations Res."},{"issue":"2","key":"2133_CR9","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1287\/ijoc.2015.0676","volume":"28","author":"A Caprara","year":"2016","unstructured":"Caprara, A., Carvalho, M., Lodi, A., Woeginger, G.J.: Bilevel knapsack with interdiction constraints. Informs J. Comput. 28(2), 319\u2013333 (2016)","journal-title":"Informs J. Comput."},{"key":"2133_CR10","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10898-015-0274-7","volume":"66","author":"Y Tang","year":"2016","unstructured":"Tang, Y., Richard, J.-P.P., Smith, J.C.: A class of algorithms for mixed-integer bilevel min-max optimization. J. Glob. Optim. 66, 225\u2013262 (2016)","journal-title":"J. Glob. Optim."},{"issue":"6","key":"2133_CR11","doi-asserted-by":"publisher","first-page":"1615","DOI":"10.1287\/opre.2017.1650","volume":"65","author":"M Fischetti","year":"2017","unstructured":"Fischetti, M., Ljubi\u0107, I., Monaci, M., Sinnl, M.: A new general-purpose algorithm for mixed-integer bilevel linear programs. Oper. Res. 65(6), 1615\u20131637 (2017)","journal-title":"Oper. Res."},{"key":"2133_CR12","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1287\/ijoc.2018.0831","volume":"31","author":"M Fischetti","year":"2019","unstructured":"Fischetti, M., Ljubic, I., Monaci, M., Sinnl, M.: Interdiction games and monotonicity, with application to knapsack problems. Informs J. Comput. 31, 390\u2013410 (2019)","journal-title":"Informs J. Comput."},{"key":"2133_CR13","unstructured":"Lozano, L., Bergman, D., Cire, A.A.: Constrained shortest-path reformulations for discrete bilevel and robust optimization. arXiv preprint arXiv:2206.12962 (2022)"},{"key":"2133_CR14","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.ejor.2017.11.043","volume":"267","author":"M Fischetti","year":"2018","unstructured":"Fischetti, M., Monaci, M., Sinnl, M.: A dynamic reformulation heuristic for generalized interdiction problems. Eur. J. Operations Res. 267, 40\u201351 (2018)","journal-title":"Eur. J. Operations Res."},{"issue":"1","key":"2133_CR15","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s10107-020-01482-5","volume":"183","author":"F Della Croce","year":"2020","unstructured":"Della Croce, F., Scatamacchia, R.: An exact approach for the bilevel knapsack problem with interdiction constraints and extensions. Math. Program. 183(1), 249\u2013281 (2020)","journal-title":"Math. Program."},{"issue":"1","key":"2133_CR16","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0377-2217(94)00013-3","volume":"87","author":"D Pisinger","year":"1995","unstructured":"Pisinger, D.: An expanding-core algorithm for the exact 0\u20131 knapsack problem. Eur. J. Oper. Res. 87(1), 175\u2013187 (1995)","journal-title":"Eur. J. Oper. Res."},{"key":"2133_CR17","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1007\/978-3-031-32726-1_31","volume-title":"Integer Programming and Combinatorial Optimization","author":"N Weninger","year":"2023","unstructured":"Weninger, N., Fukasawa, R.: A Fast Combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints. In: Del Pia, A., Kaibel, V. (eds.) Integer Programming and Combinatorial Optimization, pp. 438\u2013452. Springer, Cham (2023)"},{"key":"2133_CR18","doi-asserted-by":"crossref","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack problems. Springer, Berlin, Heidelberg (2004)","DOI":"10.1007\/978-3-540-24777-7"},{"issue":"3","key":"2133_CR19","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1287\/mnsc.45.3.414","volume":"45","author":"S Martello","year":"1999","unstructured":"Martello, S., Pisinger, D., Toth, P.: Dynamic programming and strong bounds for the 0\u20131 knapsack problem. Manag. Sci. 45(3), 414\u2013424 (1999)","journal-title":"Manag. Sci."},{"issue":"4","key":"2133_CR20","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s12532-020-00183-6","volume":"12","author":"S Tahernejad","year":"2020","unstructured":"Tahernejad, S., Ralphs, T.K., DeNegre, S.T.: A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation. Math. Program. Comput. 12(4), 529\u2013568 (2020)","journal-title":"Math. Program. Comput."},{"key":"2133_CR21","unstructured":"Fontan, F.: Knapsack Solver (Github source code repository). https:\/\/github.com\/fontanf\/knapsacksolver. Accessed 20 Mar 2023 (2017)"},{"issue":"2","key":"2133_CR22","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E.D., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201\u2013213 (2002)","journal-title":"Math. Program."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02133-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02133-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02133-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T15:59:30Z","timestamp":1740758370000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02133-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,22]]},"references-count":22,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["2133"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02133-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,22]]},"assertion":[{"value":"9 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}