{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T07:17:17Z","timestamp":1770707837598,"version":"3.49.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,1,3]],"date-time":"2022-01-03T00:00:00Z","timestamp":1641168000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,3]],"date-time":"2022-01-03T00:00:00Z","timestamp":1641168000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["BU 2313\/2"],"award-info":[{"award-number":["BU 2313\/2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["BU 2313\/6"],"award-info":[{"award-number":["BU 2313\/6"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack and the follower chooses an optimal packing according to his own profits, which may differ from those of the leader. To this bilevel problem, we add uncertainty in a natural way, assuming that the leader does not have full knowledge about the follower\u2019s problem. More precisely, adopting the robust optimization approach and assuming that the follower\u2019s profits belong to a given uncertainty set, our aim is to compute a solution that optimizes the worst-case follower\u2019s reaction from the leader\u2019s perspective. By investigating the complexity of this problem with respect to different types of uncertainty sets, we make first steps towards better understanding the combination of bilevel optimization and robust combinatorial optimization. We show that the problem can be solved in polynomial time for both discrete and interval uncertainty, but that the same problem becomes NP-hard when each coefficient can independently assume only a finite number of values. In particular, this demonstrates that replacing uncertainty sets by their convex hulls may change the problem significantly, in contrast to the situation in classical single-level robust optimization. For general polytopal uncertainty, the problem again turns out to be NP-hard, and the same is true for ellipsoidal uncertainty even in the uncorrelated case. All presented hardness results already apply to the evaluation of the leader\u2019s objective function.<\/jats:p>","DOI":"10.1007\/s10898-021-01117-9","type":"journal-article","created":{"date-parts":[[2022,1,3]],"date-time":"2022-01-03T05:03:23Z","timestamp":1641186203000},"page":"803-824","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["The robust bilevel continuous knapsack problem with uncertain coefficients in the follower\u2019s objective"],"prefix":"10.1007","volume":"83","author":[{"given":"Christoph","family":"Buchheim","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9190-642X","authenticated-orcid":false,"given":"Dorothee","family":"Henke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,3]]},"reference":[{"issue":"1","key":"1117_CR1","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1287\/opre.1030.0065","volume":"52","author":"D Bertsimas","year":"2004","unstructured":"Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52(1), 35\u201353 (2004)","journal-title":"Oper. Res."},{"key":"1117_CR2","unstructured":"Besan\u00e7on, M., Anjos, M.F., Brotcorne, L.: Near-optimal robust bilevel optimization. CoRR abs\/1908.04040 (2019)"},{"key":"1117_CR3","unstructured":"Besan\u00e7on, M., Anjos, M.F., Brotcorne, L.: Complexity of near-optimal robust versions of multilevel optimization problems. CoRR abs\/2011.00824 (2020)"},{"issue":"3","key":"1117_CR4","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.orl.2009.01.007","volume":"37","author":"L Brotcorne","year":"2009","unstructured":"Brotcorne, L., Hanafi, S., Mansi, R.: A dynamic programming algorithm for the bilevel knapsack problem. Oper. Res. Lett. 37(3), 215\u2013218 (2009)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"1117_CR5","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s13675-018-0103-0","volume":"6","author":"C Buchheim","year":"2018","unstructured":"Buchheim, C., Kurtz, J.: Robust combinatorial optimization under convex and discrete cost uncertainty. EURO J. Comput. Optim. 6(3), 211\u2013238 (2018)","journal-title":"EURO J. Comput. Optim."},{"issue":"2","key":"1117_CR6","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."},{"issue":"2","key":"1117_CR7","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/j.orl.2017.12.009","volume":"46","author":"M Carvalho","year":"2018","unstructured":"Carvalho, M., Lodi, A., Marcotte, P.: A polynomial algorithm for a continuous bilevel knapsack problem. Oper. Res. Lett. 46(2), 185\u2013188 (2018)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"1117_CR8","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1007\/s10957-017-1069-4","volume":"173","author":"TD Chuong","year":"2017","unstructured":"Chuong, T.D., Jeyakumar, V.: Finding robust global optimal values of bilevel polynomial programs with uncertain linear constraints. J. Optim. Theory Appl. 173(2), 683\u2013703 (2017)","journal-title":"J. Optim. Theory Appl."},{"issue":"1","key":"1117_CR9","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s10479-007-0176-2","volume":"153","author":"B Colson","year":"2007","unstructured":"Colson, B., Marcotte, P., Savard, G.: An overview of bilevel optimization. Ann. Oper. Res. 153(1), 235\u2013256 (2007)","journal-title":"Ann. Oper. Res."},{"issue":"2","key":"1117_CR10","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1287\/opre.5.2.266","volume":"5","author":"GB Dantzig","year":"1957","unstructured":"Dantzig, G.B.: Discrete-variable extremum problems. Oper. Res. 5(2), 266\u2013277 (1957)","journal-title":"Oper. Res."},{"issue":"3","key":"1117_CR11","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1080\/0233193031000149894","volume":"52","author":"S Dempe","year":"2003","unstructured":"Dempe, S.: Annotated bibliography on bilevel programming and mathematical programs with equilibirium constraints. Optimization 52(3), 333\u2013359 (2003)","journal-title":"Optimization"},{"key":"1117_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45827-3","volume-title":"Bilevel Programming Problems","author":"S Dempe","year":"2015","unstructured":"Dempe, S., Kalashnikov, V., P\u00e9rez-Vald\u00e9s, G.A., Kalashnykova, N.: Bilevel Programming Problems. Springer, Berlin (2015)"},{"issue":"2","key":"1117_CR13","first-page":"93","volume":"8","author":"S Dempe","year":"2000","unstructured":"Dempe, S., Richter, K.: Bilevel programming with knapsack constraints. CEJOR 8(2), 93\u2013107 (2000)","journal-title":"CEJOR"},{"key":"1117_CR14","unstructured":"DeNegre, S.: Interdiction and discrete bilevel linear programming. Ph.D. thesis, Lehigh University (2011)"},{"issue":"6","key":"1117_CR15","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1016\/j.orl.2020.09.007","volume":"48","author":"D Fischer","year":"2020","unstructured":"Fischer, D., Woeginger, G.J.: A faster algorithm for the continuous bilevel knapsack problem. Oper. Res. Lett. 48(6), 784\u2013786 (2020)","journal-title":"Oper. Res. Lett."},{"issue":"9","key":"1117_CR16","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1057\/jors.1981.156","volume":"32","author":"J Fortuny-Amat","year":"1981","unstructured":"Fortuny-Amat, J., McCarl, B.: A representation and economic interpretation of a two-level programming problem. J. Oper. Res. Soc. 32(9), 783\u2013792 (1981)","journal-title":"J. Oper. Res. Soc."},{"issue":"5","key":"1117_CR17","doi-asserted-by":"publisher","first-page":"1194","DOI":"10.1137\/0913069","volume":"13","author":"P Hansen","year":"1992","unstructured":"Hansen, P., Jaumard, B., Savard, G.: New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Stat. Comput. 13(5), 1194\u20131217 (1992)","journal-title":"SIAM J. Sci. Stat. Comput."},{"key":"1117_CR18","unstructured":"Henkel, C.: An algorithm for the global resolution of linear stochastic bilevel programs. Ph.D. thesis, University of Duisburg-Essen (2014)"},{"issue":"4","key":"1117_CR19","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(89)90136-1","volume":"33","author":"J Hershberger","year":"1989","unstructured":"Hershberger, J.: Finding the upper envelope of $$n$$ line segments in $${\\cal{O}}(n \\log n)$$ time. Inf. Process. Lett. 33(4), 169\u2013174 (1989)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1117_CR20","doi-asserted-by":"publisher","first-page":"894","DOI":"10.1137\/120863873","volume":"23","author":"M Hu","year":"2013","unstructured":"Hu, M., Fukushima, M.: Existence, uniqueness, and computation of robust Nash equilibria in a class of multi-leader-follower games. SIAM J. Optim. 23(2), 894\u2013916 (2013)","journal-title":"SIAM J. Optim."},{"key":"1117_CR21","unstructured":"H\u00fcgging, M.V.: The bilevel continuous knapsack problem with uncertain weights. Master\u2019s thesis, TU Dortmund University (2020)"},{"key":"1117_CR22","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.: Knapsack Problems. Springer, Berlin (2004)"},{"issue":"4","key":"1117_CR23","doi-asserted-by":"publisher","first-page":"1027","DOI":"10.1007\/s11590-020-01660-6","volume":"15","author":"T Kleinert","year":"2021","unstructured":"Kleinert, T., Labb\u00e9, M., Plein, F., Schmidt, M.: Closing the gap in linear bilevel optimization: a new valid primal-dual inequality. Optim. Lett. 15(4), 1027\u20131040 (2021)","journal-title":"Optim. Lett."},{"key":"1117_CR24","doi-asserted-by":"crossref","unstructured":"Kouvelis, P., Yu, G.: Robust Discrete Optimization and Its Applications. Springer (1996)","DOI":"10.1007\/978-1-4757-2620-6"},{"key":"1117_CR25","doi-asserted-by":"crossref","unstructured":"Mansi, R., Alves, C., Val\u00e9rio\u00a0de Carvalho, J.M., Hanafi, S.: An exact algorithm for bilevel 0-1 knapsack problems. Math. Probl. Eng. (2012). Article ID 504713","DOI":"10.1155\/2012\/504713"},{"issue":"2","key":"1117_CR26","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/s10479-016-2293-2","volume":"256","author":"P Sariddichainunta","year":"2017","unstructured":"Sariddichainunta, P., Inuiguchi, M.: Global optimality test for maximin solution of bilevel linear programming with ambiguous lower-level objective function. Ann. Oper. Res. 256(2), 285\u2013304 (2017)","journal-title":"Ann. Oper. Res."},{"issue":"1","key":"1117_CR27","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1137\/120864015","volume":"23","author":"W Wiesemann","year":"2013","unstructured":"Wiesemann, W., Tsoukalas, A., Kleniati, P.M., Rustem, B.: Pessimistic bilevel optimization. SIAM J. Optim. 23(1), 353\u2013380 (2013)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1117_CR28","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0166-218X(02)00427-4","volume":"131","author":"GJ Woeginger","year":"2003","unstructured":"Woeginger, G.J.: On the approximability of average completion time scheduling under precedence constraints. Discrete Appl. Math. 131(1), 237\u2013252 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1117_CR29","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s10898-017-0549-2","volume":"71","author":"MH Zare","year":"2018","unstructured":"Zare, M.H., \u00d6zalt\u0131n, O.Y., Prokopyev, O.A.: On a class of bilevel linear mixed-integer programs in adversarial settings. J. Global Optim. 71(1), 91\u2013113 (2018)","journal-title":"J. Global Optim."},{"issue":"4","key":"1117_CR30","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1016\/j.orl.2010.04.005","volume":"38","author":"OY \u00d6zalt\u0131n","year":"2010","unstructured":"\u00d6zalt\u0131n, O.Y., Prokopyev, O.A., Schaefer, A.J.: The bilevel knapsack problem with stochastic right-hand sides. Oper. Res. Lett. 38(4), 328\u2013333 (2010)","journal-title":"Oper. Res. Lett."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01117-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-021-01117-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01117-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,17]],"date-time":"2022-07-17T07:03:36Z","timestamp":1658041416000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-021-01117-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,3]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["1117"],"URL":"https:\/\/doi.org\/10.1007\/s10898-021-01117-9","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,3]]},"assertion":[{"value":"11 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2022","order":3,"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 conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}