{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:39:43Z","timestamp":1740145183911,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,8,11]],"date-time":"2020-08-11T00:00:00Z","timestamp":1597104000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,11]],"date-time":"2020-08-11T00:00:00Z","timestamp":1597104000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2017\/26\/D\/ST6\/00423"],"award-info":[{"award-number":["2017\/26\/D\/ST6\/00423"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the robust version of items selection problem, in which the goal is to choose representatives from a family of sets, preserving constraints on the allowed items\u2019 combinations. We prove NP-hardness of the deterministic version, and establish polynomially solvable special cases. Next, we consider the robust version in which we aim at minimizing the maximum regret of the solution under interval parameter uncertainty. We show that this problem is hard for the second level of polynomial-time hierarchy. We develop exact solution algorithms for the robust problem, based on cut generation and mixed-integer programming, and present the results of computational experiments.<\/jats:p>","DOI":"10.1007\/s11590-020-01626-8","type":"journal-article","created":{"date-parts":[[2020,8,11]],"date-time":"2020-08-11T21:08:09Z","timestamp":1597180089000},"page":"649-667","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Robust approach to restricted items selection problem"],"prefix":"10.1007","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8999-8748","authenticated-orcid":false,"given":"Maciej","family":"Drwal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,8,11]]},"reference":[{"key":"1626_CR1","doi-asserted-by":"publisher","DOI":"10.21236\/ADA594171","volume-title":"Network Flows","author":"RK Ahuja","year":"1988","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice Hall, Upper Saddle River (1988)"},{"issue":"6","key":"1626_CR2","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1016\/j.orl.2004.12.002","volume":"33","author":"H Aissi","year":"2005","unstructured":"Aissi, H., Bazgan, C., Vanderpooten, D.: Complexity of the min-max and min-max regret assignment problems. Oper. Res. Lett. 33(6), 634\u2013640 (2005)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"1626_CR3","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1016\/j.ejor.2008.09.012","volume":"197","author":"H Aissi","year":"2009","unstructured":"Aissi, H., Bazgan, C., Vanderpooten, D.: Min-max and min-max regret versions of combinatorial optimization problems: a survey. Eur. J. Oper. Res. 197(2), 427\u2013438 (2009)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"1626_CR4","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/PL00011424","volume":"90","author":"I Averbakh","year":"2001","unstructured":"Averbakh, I.: On the complexity of a class of combinatorial optimization problems with uncertainty. Math. Program. 90(2), 263\u2013272 (2001)","journal-title":"Math. Program."},{"issue":"3","key":"1626_CR5","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/S0166-218X(03)00462-1","volume":"138","author":"I Averbakh","year":"2004","unstructured":"Averbakh, I., Lebedev, V.: Interval data minmax regret network optimization problems. Discr. Appl. Math. 138(3), 289\u2013301 (2004)","journal-title":"Discr. Appl. Math."},{"issue":"1","key":"1626_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0167-6377(99)00016-4","volume":"25","author":"A Ben-Tal","year":"1999","unstructured":"Ben-Tal, A., Nemirovski, A.: Robust solutions of uncertain linear programs. Oper. Res. Lett. 25(1), 1\u201313 (1999)","journal-title":"Oper. Res. Lett."},{"issue":"1\u20133","key":"1626_CR7","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10107-003-0396-4","volume":"98","author":"D Bertsimas","year":"2003","unstructured":"Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. 98(1\u20133), 49\u201371 (2003)","journal-title":"Math. Program."},{"issue":"1","key":"1626_CR8","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."},{"issue":"2","key":"1626_CR9","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s10107-003-0474-7","volume":"100","author":"E Conde","year":"2004","unstructured":"Conde, E.: An improved algorithm for selecting p items with uncertain returns according to the minmax-regret criterion. Math. Program. 100(2), 345\u2013353 (2004)","journal-title":"Math. Program."},{"issue":"3","key":"1626_CR10","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s10288-012-0227-7","volume":"11","author":"VG Deineko","year":"2013","unstructured":"Deineko, V.G., Woeginger, G.J.: Complexity and in-approximability of a selection problem in robust optimization. 4OR 11(3), 249\u2013252 (2013)","journal-title":"4OR"},{"issue":"2","key":"1626_CR11","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s10288-012-0202-3","volume":"10","author":"A Dolgui","year":"2012","unstructured":"Dolgui, A., Kovalev, S.: Min\u2013max and min\u2013max (relative) regret approaches to representatives selection problem. 4OR 10(2), 181\u2013192 (2012)","journal-title":"4OR"},{"key":"1626_CR12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.cor.2017.10.010","volume":"91","author":"M Drwal","year":"2018","unstructured":"Drwal, M.: Robust scheduling to minimize the weighted number of late jobs with interval due-date uncertainty. Comput. Oper. Res. 91, 13\u201320 (2018)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"1626_CR13","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1016\/j.orl.2016.03.005","volume":"44","author":"M Drwal","year":"2016","unstructured":"Drwal, M., Rischke, R.: Complexity of interval minmax regret scheduling on parallel identical machines with total completion time criterion. Oper. Res. Lett. 44(3), 354\u2013358 (2016)","journal-title":"Oper. Res. Lett."},{"key":"1626_CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M Garey","year":"2002","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, W.H (2002)"},{"key":"1626_CR15","doi-asserted-by":"crossref","unstructured":"Goerigk, M., Sch\u00f6bel, A.: Algorithm engineering in robust optimization. In: Kliemann, L., Sanders, P. (eds.) Algorithm Engineering, . Lecture Notes in Computer Science, vol. 9220, pp. 245\u2013279. Springer, Cham (2016)","DOI":"10.1007\/978-3-319-49487-6_8"},{"issue":"2","key":"1626_CR16","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/j.jmsy.2011.07.008","volume":"31","author":"M Jahromi","year":"2012","unstructured":"Jahromi, M., Tavakkoli-Moghaddam, R.: A novel 0\u20131 linear integer programming model for dynamic machine-tool selection and operation allocation in a flexible manufacturing system. J. Manuf. Syst. 31(2), 224\u2013231 (2012)","journal-title":"J. Manuf. Syst."},{"key":"1626_CR17","volume-title":"Stochastic Programming","author":"P Kall","year":"1994","unstructured":"Kall, P., Wallace, S.W., Kall, P.: Stochastic Programming. Springer, Berlin (1994)"},{"key":"1626_CR18","volume-title":"Discrete Optimization with Interval Data: Minmax Regret and Fuzzy Approach","author":"A Kasperski","year":"2008","unstructured":"Kasperski, A.: Discrete Optimization with Interval Data: Minmax Regret and Fuzzy Approach. Springer, Berlin (2008)"},{"issue":"1","key":"1626_CR19","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.orl.2014.10.007","volume":"43","author":"A Kasperski","year":"2015","unstructured":"Kasperski, A., Kurpisz, A., Zieli\u0144ski, P.: Approximability of the robust representatives selection problem. Oper. Res. Lett. 43(1), 16\u201319 (2015)","journal-title":"Oper. Res. Lett."},{"key":"1626_CR20","unstructured":"Kasperski, A., Zielinski, P.: Minmax (regret) scheduling problems. In: Y. Sotskov F. Werner (eds.)Sequencing and Scheduling with Inaccurate Data. pp. 159\u2013210, Nova Science Publishers, Inc., Hauppauge, NY (2014)"},{"issue":"3","key":"1626_CR21","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2- $$\\varepsilon $$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1626_CR22","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/S0360-8352(03)00019-6","volume":"45","author":"CS Lee","year":"2003","unstructured":"Lee, C.S., Kim, S.S., Choi, J.S.: Operation sequence and tool selection in flexible manufacturing systems under dynamic tool allocation. Comput. Ind. Eng. 45(1), 61\u201373 (2003)","journal-title":"Comput. Ind. Eng."},{"key":"1626_CR23","doi-asserted-by":"crossref","unstructured":"Liebchen, C., L\u00fcbbecke, M., M\u00f6hring, R., Stiller, S.: The concept of recoverable robustness, linear programming recovery, and railway applications. In: Ahuja, R.K., M\u00f6hring, R.H., Zaroliagis, C.D. (eds.) Robust and online large-scale optimization. Lecture Notes in Computer Science, vol. 5868, Springer, Berlin, Heidelberg (2009)","DOI":"10.1007\/978-3-642-05465-5_1"},{"issue":"8","key":"1626_CR24","doi-asserted-by":"publisher","first-page":"1153","DOI":"10.1016\/j.cor.2010.11.009","volume":"38","author":"J Pereira","year":"2011","unstructured":"Pereira, J., Averbakh, I.: Exact and heuristic algorithms for the interval data robust assignment problem. Comput. Oper. Res. 38(8), 1153\u20131163 (2011)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"1626_CR25","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1016\/j.ejor.2008.12.036","volume":"200","author":"B Roy","year":"2010","unstructured":"Roy, B.: Robustness in operational research and decision aiding: A multi-faceted issue. Eur. J. Oper. Res. 200(3), 629\u2013638 (2010)","journal-title":"Eur. J. Oper. Res."},{"key":"1626_CR26","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver, A.: Theory of linear and integer programming. Wiley, New York (1998)"},{"key":"1626_CR27","unstructured":"Stockmeyer, L.J.: The polynomial-time hierarchy. Theor. Comput. Sci. 3(1), 1\u201322 (1976)"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-020-01626-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-020-01626-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-020-01626-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,6]],"date-time":"2022-11-06T15:25:42Z","timestamp":1667748342000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-020-01626-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,11]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["1626"],"URL":"https:\/\/doi.org\/10.1007\/s11590-020-01626-8","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2020,8,11]]},"assertion":[{"value":"7 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}