{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T15:08:06Z","timestamp":1775574486646,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2022,2,2]],"date-time":"2022-02-02T00:00:00Z","timestamp":1643760000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,2]],"date-time":"2022-02-02T00:00:00Z","timestamp":1643760000000},"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":"crossref","award":["Research Training Group 1855"],"award-info":[{"award-number":["Research Training Group 1855"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"crossref","award":["FA8655-20-1-7012"],"award-info":[{"award-number":["FA8655-20-1-7012"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"crossref","award":["FA8655-20-1-7019"],"award-info":[{"award-number":["FA8655-20-1-7019"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider stochastic problems in which both the objective function and the feasible set are affected by uncertainty. We address these problems using a <jats:italic>K<\/jats:italic>-adaptability approach, in which <jats:italic>K<\/jats:italic> solutions for a given problem are computed before the uncertainty dissolves and afterwards the best of them can be chosen for the realized scenario. We analyze the complexity of the resulting problem from a theoretical viewpoint, showing that, even in case the deterministic problem can be solved in polynomial time, deciding if a feasible solution exists is <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard for discrete probability distributions. Besides that, we prove that an approximation factor for the underlying problem can be carried over to our problem. Finally, we present exact approaches including a branch-and-price algorithm. An extensive computational analysis compares the performances of the proposed algorithms on a large set of randomly generated instances.\n<\/jats:p>","DOI":"10.1007\/s10107-021-01767-3","type":"journal-article","created":{"date-parts":[[2022,2,2]],"date-time":"2022-02-02T12:02:52Z","timestamp":1643803372000},"page":"567-595","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["K-adaptability in stochastic optimization"],"prefix":"10.1007","volume":"196","author":[{"given":"Enrico","family":"Malaguti","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9978-7613","authenticated-orcid":false,"given":"Michele","family":"Monaci","sequence":"additional","affiliation":[]},{"given":"Jonas","family":"Pruente","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,2]]},"reference":[{"key":"1767_CR1","volume-title":"Robust Optimization. Princeton Series in Applied Mathematics","author":"A Ben-Tal","year":"2009","unstructured":"Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2009)"},{"key":"1767_CR2","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1287\/moor.23.4.769","volume":"23","author":"A Ben-Tal","year":"1998","unstructured":"Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23, 769\u2013805 (1998)","journal-title":"Math. Oper. Res."},{"key":"1767_CR3","doi-asserted-by":"publisher","first-page":"2751","DOI":"10.1109\/TAC.2010.2049764","volume":"55","author":"D Bertsimas","year":"2010","unstructured":"Bertsimas, D., Caramanis, C.: Finite adaptability in multistage linear optimization. IEEE Trans. Autom. Control 55, 2751\u20132766 (2010)","journal-title":"IEEE Trans. Autom. Control"},{"key":"1767_CR4","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1287\/moor.1090.0440","volume":"35","author":"D Bertsimas","year":"2010","unstructured":"Bertsimas, D., Goyal, V.: On the power of robust solutions in two-stage stochastic and adaptive optimization problems. Math. Oper. Res. 35, 284\u2013305 (2010)","journal-title":"Math. Oper. Res."},{"key":"1767_CR5","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, 35\u201353 (2004)","journal-title":"Oper. Res."},{"key":"1767_CR6","volume-title":"Introduction to Stochastic Programming. Springer Series in Operations Research and Financial Engineering","author":"JR Birge","year":"1997","unstructured":"Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer Series in Operations Research and Financial Engineering. Springer, Berlin (1997)"},{"key":"1767_CR7","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1016\/j.ejor.2019.03.045","volume":"277","author":"C Buchheim","year":"2019","unstructured":"Buchheim, C., Pruente, J.: $$k$$-adaptability in stochastic combinatorial optimization under objective uncertainty. Eur. J. Oper. Res. 277, 953\u2013963 (2019)","journal-title":"Eur. J. Oper. Res."},{"key":"1767_CR8","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-05465-5_3","volume-title":"Robust and Online Large-Scale Optimization. Lecture Notes in Computer Science","author":"M Fischetti","year":"2009","unstructured":"Fischetti, M., Monaci, M.: Light robustness. In: Ahuja, R.K., M\u00f6hring, R., Zaroliagis, C. (eds.) Robust and Online Large-Scale Optimization. Lecture Notes in Computer Science, vol. 5868, pp. 61\u201384. Springer, Berlin (2009)"},{"key":"1767_CR9","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1287\/opre.2015.1392","volume":"63","author":"GA Hanasusanto","year":"2015","unstructured":"Hanasusanto, G.A., Kuhn, D., Wiesemann, W.: $$k$$-adaptability in two-stage robust binary programming. Oper. Res. 63, 877\u2013891 (2015)","journal-title":"Oper. Res."},{"key":"1767_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-05465-5_1","volume-title":"Robust and Online Large-Scale Optimization. Lecture Notes in Computer Science","author":"C Liebchen","year":"2009","unstructured":"Liebchen, C., L\u00fcbbecke, M., M\u00f6hring, R.H., Stiller, S.: The concept of recoverable robustness, linear programming recovery, and railway applications. In: Ahuja, R.K., M\u00f6hring, R., Zaroliagis, C. (eds.) Robust and Online Large-Scale Optimization. Lecture Notes in Computer Science, vol. 5868, pp. 1\u201327. Springer, Berlin (2009)"},{"issue":"3","key":"1767_CR11","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0304-3975(81)90081-5","volume":"15","author":"A Paz","year":"1981","unstructured":"Paz, A., Moran, S.: Non deterministic polynomial optimization problems and their approximations. Theor. Comput. Sci. 15(3), 251\u2013277 (1981)","journal-title":"Theor. Comput. Sci."},{"key":"1767_CR12","doi-asserted-by":"crossref","unstructured":"Pr\u00e9kopa, A.: Programming under probabilistic constraint and maximizing probabilities under constraints. In: Pr\u00e9kopa A (ed.) Stochastic Programming. Mathematics and Its Applications vol. 324, pp. 319\u2013371. Springer, Dordrecht (1995)","DOI":"10.1007\/978-94-017-3087-7_11"},{"key":"1767_CR13","volume-title":"Stochastic Programming. Handbooks in Operations Research and Management Science","author":"A Ruszczynski","year":"2003","unstructured":"Ruszczynski, A., Shapiro, A.: Stochastic Programming. Handbooks in Operations Research and Management Science. Elsevier, Amsterdam (2003)"},{"key":"1767_CR14","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00186-014-0474-9","volume":"80","author":"A Sch\u00f6bel","year":"2014","unstructured":"Sch\u00f6bel, A.: Generalized light robustness and the trade-off between robustness and nominal quality. Math. Methods Oper. Res. 80, 161\u2013191 (2014)","journal-title":"Math. Methods Oper. Res."},{"key":"1767_CR15","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1287\/opre.21.5.1154","volume":"21","author":"AL Soyster","year":"1973","unstructured":"Soyster, A.L.: Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21, 1154\u20131157 (1973)","journal-title":"Oper. Res."},{"key":"1767_CR16","first-page":"1154","volume":"21","author":"A Subramanyam","year":"2019","unstructured":"Subramanyam, A., Gounaris, C.E., Wiesemann, W.: $$k$$-adaptability in two-stage mixed-integer robust optimization. Math. Program. Comput. 21, 1154\u20131157 (2019)","journal-title":"Math. Program. Comput."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01767-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01767-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01767-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T23:33:41Z","timestamp":1667864021000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01767-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,2]]},"references-count":16,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1767"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01767-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,2]]},"assertion":[{"value":"14 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}