{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T21:06:59Z","timestamp":1778792819220,"version":"3.51.4"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T00:00:00Z","timestamp":1652227200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T00:00:00Z","timestamp":1652227200000},"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, BU 2313\/6"],"award-info":[{"award-number":["BU 2313\/2, 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 Optim Theory Appl"],"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, while the follower chooses a feasible packing maximizing his own profit. The leader\u2019s aim is to optimize a linear objective function in the capacity and in the follower\u2019s solution, but with respect to different item values. We address a stochastic version of this problem where the follower\u2019s profits are uncertain from the leader\u2019s perspective, and only a probability distribution is known. Assuming that the leader aims at optimizing the expected value of her objective function, we first observe that the stochastic problem is tractable as long as the possible scenarios are given explicitly as part of the input, which also allows to deal with general distributions using a sample average approximation. For the case of independently and uniformly distributed item values, we show that the problem is #P-hard in general, and the same is true even for evaluating the leader\u2019s objective function. Nevertheless, we present pseudo-polynomial time algorithms for this case, running in time linear in the total size of the items. Based on this, we derive an additive approximation scheme for the general case of independently distributed item values, which runs in pseudo-polynomial time.<\/jats:p>","DOI":"10.1007\/s10957-022-02037-8","type":"journal-article","created":{"date-parts":[[2022,5,11]],"date-time":"2022-05-11T18:04:15Z","timestamp":1652292255000},"page":"521-542","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The Stochastic Bilevel Continuous Knapsack Problem with Uncertain Follower\u2019s Objective"],"prefix":"10.1007","volume":"194","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6097-1867","authenticated-orcid":false,"given":"Jannik","family":"Irmai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,11]]},"reference":[{"issue":"3","key":"2037_CR1","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). https:\/\/doi.org\/10.1016\/j.orl.2009.01.007","journal-title":"Oper. Res. Lett."},{"key":"2037_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-021-01117-9","author":"C Buchheim","year":"2022","unstructured":"Buchheim, C., Henke, D.: The robust bilevel continuous knapsack problem with uncertain coefficients in the follower\u2019s objective. J. Glob. Optim. (2022). https:\/\/doi.org\/10.1007\/s10898-021-01117-9","journal-title":"J. Glob. Optim."},{"issue":"5","key":"2037_CR3","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1016\/j.orl.2021.07.009","volume":"49","author":"C Buchheim","year":"2021","unstructured":"Buchheim, C., Henke, D., Hommelsheim, F.: On the complexity of robust bilevel optimization with uncertain follower\u2019s objective. Oper. Res. Lett. 49(5), 703\u2013707 (2021). https:\/\/doi.org\/10.1016\/j.orl.2021.07.009","journal-title":"Oper. Res. Lett."},{"key":"2037_CR4","doi-asserted-by":"publisher","unstructured":"Burtscheidt, J., Claus, M.: Bilevel linear optimization under uncertainty. In: Dempe, S., Zemkoho, A. (eds.) Bilevel Optimization: Advances and Next Challenges, pp. 485\u2013511. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-52119-6_17","DOI":"10.1007\/978-3-030-52119-6_17"},{"issue":"1","key":"2037_CR5","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). https:\/\/doi.org\/10.1007\/s10479-007-0176-2","journal-title":"Ann. Oper. Res."},{"issue":"2","key":"2037_CR6","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). https:\/\/doi.org\/10.1287\/OPRE.5.2.266","journal-title":"Oper. Res."},{"issue":"3","key":"2037_CR7","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 equilibrium constraints. Optimization 52(3), 333\u2013359 (2003). https:\/\/doi.org\/10.1080\/0233193031000149894","journal-title":"Optimization"},{"key":"2037_CR8","doi-asserted-by":"publisher","unstructured":"Dempe, S., Kalashnikov, V., P\u00e9rez-Vald\u00e9s, G.A., Kalashnykova, N.: Bilevel Programming Problems. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-662-45827-3","DOI":"10.1007\/978-3-662-45827-3"},{"key":"2037_CR9","doi-asserted-by":"publisher","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co Ltd (1979). https:\/\/doi.org\/10.1090\/S0273-0979-1980-14848-X","DOI":"10.1090\/S0273-0979-1980-14848-X"},{"key":"2037_CR10","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/s10107-015-0958-2","volume":"159","author":"GA Hanasusanto","year":"2016","unstructured":"Hanasusanto, G.A., Kuhn, D., Wiesemann, W.: A comment on \u201ccomputational complexity of stochastic programming problems\u2019\u2019. Math. Program. 159, 557\u2013569 (2016). https:\/\/doi.org\/10.1007\/s10107-015-0958-2","journal-title":"Math. Program."},{"issue":"5","key":"2037_CR11","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). https:\/\/doi.org\/10.1137\/0913069","journal-title":"SIAM J. Sci. Stat. Comput."},{"key":"2037_CR12","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":"2037_CR13","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"OH Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463\u2013468 (1975). https:\/\/doi.org\/10.1145\/321906.321909","journal-title":"J. ACM"},{"key":"2037_CR14","unstructured":"Irmai, J.: The Stochastic Bilevel Selection Problem. Master\u2019s thesis, TU Dortmund University (2021)"},{"issue":"4","key":"2037_CR15","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0167-6377(99)00052-8","volume":"25","author":"M Patriksson","year":"1999","unstructured":"Patriksson, M., Wynter, L.: Stochastic mathematical programs with equilibrium constraints. Oper. Res. Lett. 25(4), 159\u2013167 (1999). https:\/\/doi.org\/10.1016\/S0167-6377(99)00052-8","journal-title":"Oper. Res. Lett."},{"key":"2037_CR16","doi-asserted-by":"publisher","unstructured":"Shapiro, A., Dentcheva, D., Ruszczynski, A.: Lectures on Stochastic Programming. Society for Industrial and Applied Mathematics (2009). https:\/\/doi.org\/10.1137\/1.9780898718751","DOI":"10.1137\/1.9780898718751"},{"key":"2037_CR17","unstructured":"Warwel, L.V.: The Stochastic Bilevel Continuous Knapsack Problem. Master\u2019s thesis, TU Dortmund University (2020)"}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-022-02037-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-022-02037-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-022-02037-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T20:10:41Z","timestamp":1657224641000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-022-02037-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,11]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["2037"],"URL":"https:\/\/doi.org\/10.1007\/s10957-022-02037-8","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,11]]},"assertion":[{"value":"27 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 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 have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}