{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:39Z","timestamp":1740122439412,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T00:00:00Z","timestamp":1674604800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T00:00:00Z","timestamp":1674604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u00e0 degli Studi di Roma La Sapienza"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose a general solution approach for min-max-robust counterparts of combinatorial optimization problems with uncertain linear objectives. We focus on the discrete scenario case, but our approach can be extended to other types of uncertainty sets such as polytopes or ellipsoids. Concerning the underlying certain problem, the algorithm is entirely oracle-based, i.e., our approach only requires a (primal) algorithm for solving the certain problem. It is thus particularly useful in case the certain problem is well-studied but its combinatorial structure cannot be directly exploited in a tailored robust optimization approach, or in situations where the underlying problem is only defined implicitly by a given software. The idea of our algorithm is to solve the convex relaxation of the robust problem by a simplicial decomposition approach, the main challenge being the non-differentiability of the objective function in the case of discrete or polytopal uncertainty. The resulting dual bounds are then used within a tailored branch-and-bound framework for solving the robust problem to optimality. By a computational evaluation, we show that our method outperforms straightforward linearization approaches on the robust minimum spanning tree problem. Moreover, using the Concorde solver for the certain oracle, our approach computes much better dual bounds for the robust traveling salesman problem in the same amount of time.\n<\/jats:p>","DOI":"10.1007\/s10898-023-01271-2","type":"journal-article","created":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T09:03:14Z","timestamp":1674637394000},"page":"27-51","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An oracle-based framework for robust combinatorial optimization"],"prefix":"10.1007","volume":"88","author":[{"given":"Enrico","family":"Bettiol","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Buchheim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1189-5917","authenticated-orcid":false,"given":"Marianna","family":"De Santis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Rinaldi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,25]]},"reference":[{"key":"1271_CR1","unstructured":"Bertsekas, D.P.: Convex Optimization Theory. Athena Scientific, Belmont, MA (2009)"},{"key":"1271_CR2","unstructured":"Bertsekas, D.P.: Convex Optimization Algorithms. Athena Scientific, Belmont, MA (2015)"},{"issue":"1","key":"1271_CR3","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1137\/090772204","volume":"21","author":"DP Bertsekas","year":"2011","unstructured":"Bertsekas, D.P., Huizhen, Yu.: A unifying polyhedral approximation framework for convex optimization. SIAM J. Optim. 21(1), 333\u2013360 (2011). https:\/\/doi.org\/10.1137\/090772204","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1271_CR4","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s10589-019-00151-4","volume":"75","author":"E Bettiol","year":"2020","unstructured":"Bettiol, E., L\u00e9tocart, L., Rinaldi, F., Traversi, E.: A conjugate direction based simplicial decomposition framework for solving a specific class of dense convex quadratic programs. Comput. Optim. Appl. 75(2), 321\u2013360 (2020). https:\/\/doi.org\/10.1007\/s10589-019-00151-4","journal-title":"Comput. Optim. Appl."},{"key":"1271_CR5","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1016\/j.dam.2020.07.002","volume":"285","author":"C Buchheim","year":"2020","unstructured":"Buchheim, C.: A note on the nonexistence of oracle-polynomial algorithms for robust combinatorial optimization. Discret. Appl. Math. 285, 591\u2013593 (2020). https:\/\/doi.org\/10.1016\/j.dam.2020.07.002","journal-title":"Discret. Appl. Math."},{"issue":"1\u20132","key":"1271_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-016-1053-z","volume":"163","author":"C Buchheim","year":"2017","unstructured":"Buchheim, C., Kurtz, J.: Min-max-min robust combinatorial optimization. Math. Program. 163(1\u20132), 1\u201323 (2017). https:\/\/doi.org\/10.1007\/s10107-016-1053-z","journal-title":"Math. Program."},{"issue":"3","key":"1271_CR7","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). https:\/\/doi.org\/10.1007\/s13675-018-0103-0","journal-title":"EURO J. Comput. Optim."},{"issue":"4","key":"1271_CR8","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1007\/s12532-019-00160-8","volume":"11","author":"C Buchheim","year":"2019","unstructured":"Buchheim, C., De Santis, M.: An active set algorithm for robust combinatorial optimization based on separation oracles. Math. Program. Comput. 11(4), 755\u2013789 (2019). https:\/\/doi.org\/10.1007\/s12532-019-00160-8","journal-title":"Math. Program. Comput."},{"issue":"3","key":"1271_CR9","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1007\/s10898-017-0571-4","volume":"70","author":"C Buchheim","year":"2018","unstructured":"Buchheim, C., De Santis, M., Rinaldi, F., Trieu, L.: A Frank-Wolfe based branch-and-bound algorithm for mean-risk optimization. J. Global Optim. 70(3), 625\u2013644 (2018). https:\/\/doi.org\/10.1007\/s10898-017-0571-4","journal-title":"J. Global Optim."},{"key":"1271_CR10","unstructured":"Concorde TSP solver. https:\/\/www.math.uwaterloo.ca\/tsp\/concorde\/index.html"},{"key":"1271_CR11","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E.D., More, J.J.: Benchmarking optimization software with performance profiles. Math. Progr. 91, 201\u2013213 (2002)","journal-title":"Math. Progr."},{"key":"1271_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-012-0039-y","author":"M Fischetti","year":"2012","unstructured":"Fischetti, M., Monaci, M.: Cutting plane versus compact formulations for uncertain (integer) linear programs. Math. Progr. Comput. (2012). https:\/\/doi.org\/10.1007\/s12532-012-0039-y","journal-title":"Math. Progr. Comput."},{"key":"1271_CR13","doi-asserted-by":"crossref","unstructured":"Hearn, Donald\u00a0W, Lawphongpanich, S., Ventura, Jose\u00a0A.: Restricted simplicial decomposition: Computation and extensions. In: Computation Mathematical Programming, pp 99\u2013118. Springer, (1987). https:\/\/doi.org\/10.1007\/BFb0121181","DOI":"10.1007\/BFb0121181"},{"issue":"1","key":"1271_CR14","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/BF01580219","volume":"6","author":"CA Holloway","year":"1974","unstructured":"Holloway, C.A.: An extension of the frank and wolfe method of feasible directions. Math. Program. 6(1), 14\u201327 (1974). https:\/\/doi.org\/10.1007\/BF01580219","journal-title":"Math. Program."},{"key":"1271_CR15","unstructured":"IBM ILOG CPLEX Optimizer, (2021). https:\/\/www.ibm.com\/it-it\/analytics\/cplex-optimizer"},{"issue":"2","key":"1271_CR16","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/s10589-020-00207-w","volume":"77","author":"N K\u00e4mmerling","year":"2020","unstructured":"K\u00e4mmerling, N., Kurtz, J.: Oracle-based algorithms for binary two-stage robust optimization. Comput. Optim. Appl. 77(2), 539\u2013569 (2020). https:\/\/doi.org\/10.1007\/s10589-020-00207-w","journal-title":"Comput. Optim. Appl."},{"key":"1271_CR17","volume-title":"Robust Discrete Optimization and its Applications","author":"P Kouvelis","year":"1996","unstructured":"Kouvelis, P., Gang, Y.: Robust Discrete Optimization and its Applications. Springer, Berlin (1996)"},{"issue":"1","key":"1271_CR18","doi-asserted-by":"publisher","first-page":"48","DOI":"10.2307\/2033241","volume":"7","author":"JB Kruskal","year":"1956","unstructured":"Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedi. Am. Math. Soc. 7(1), 48\u201350 (1956). https:\/\/doi.org\/10.2307\/2033241","journal-title":"Proceedi. Am. Math. Soc."},{"key":"1271_CR19","unstructured":"Kurtz, J.: New complexity results and algorithms for min-max-min robust combinatorial optimization. arXiv:2106.03107, (2021)"},{"key":"1271_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39568-1","volume-title":"First-order and Stochastic Optimization Methods for Machine Learning","author":"G Lan","year":"2020","unstructured":"Lan, G.: First-order and Stochastic Optimization Methods for Machine Learning. Springer Nature, New York (2020)"},{"issue":"1","key":"1271_CR21","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1287\/trsc.26.1.4","volume":"26","author":"T Larsson","year":"1992","unstructured":"Larsson, T., Patriksson, M.: Simplicial decomposition with disaggregated representation for the traffic assignment problem. Transp. Sci. 26(1), 4\u201317 (1992). https:\/\/doi.org\/10.1287\/trsc.26.1.4","journal-title":"Transp. Sci."},{"issue":"3","key":"1271_CR22","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1080\/10556780802712889","volume":"24","author":"A Mutapcic","year":"2009","unstructured":"Mutapcic, A., Boyd, S.: Cutting-set methods for robust convex optimization with pessimizing oracles. Optim. Methods Softw. 24(3), 381\u2013406 (2009). https:\/\/doi.org\/10.1080\/10556780802712889","journal-title":"Optim. Methods Softw."},{"key":"1271_CR23","unstructured":"TSPLIB. http:\/\/comopt.ifi.uni-heidelberg.de\/software\/TSPLIB95"},{"issue":"1","key":"1271_CR24","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF01581238","volume":"59","author":"JA Ventura","year":"1993","unstructured":"Ventura, J.A., Hearn, D.W.: Restricted simplicial decomposition for convex constrained problems. Math. Program. 59(1), 71\u201385 (1993). https:\/\/doi.org\/10.1007\/BF01581238","journal-title":"Math. Program."},{"issue":"1","key":"1271_CR25","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/BF01584323","volume":"13","author":"B Von Hohenbalken","year":"1977","unstructured":"Von Hohenbalken, B.: Simplicial decomposition in nonlinear programming algorithms. Math. Program. 13(1), 49\u201368 (1977). https:\/\/doi.org\/10.1007\/BF01584323","journal-title":"Math. Program."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-023-01271-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-023-01271-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-023-01271-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,10]],"date-time":"2024-01-10T10:03:19Z","timestamp":1704880999000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-023-01271-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,25]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["1271"],"URL":"https:\/\/doi.org\/10.1007\/s10898-023-01271-2","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2023,1,25]]},"assertion":[{"value":"24 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 January 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}