{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:09Z","timestamp":1740109329721,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,7,13]],"date-time":"2023-07-13T00:00:00Z","timestamp":1689206400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,13]],"date-time":"2023-07-13T00:00:00Z","timestamp":1689206400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003500","name":"Universit\u00e0 degli Studi di Padova","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003500","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,5]]},"abstract":"Abstract<\/jats:title>For a finite set\u00a0$$X \\subset \\mathbb {Z}^d$$<\/jats:tex-math>\n \n X<\/mml:mi>\n \u2282<\/mml:mo>\n \n \n Z<\/mml:mi>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that can be represented as $$X = Q \\cap \\mathbb {Z}^d$$<\/jats:tex-math>\n \n X<\/mml:mi>\n =<\/mml:mo>\n Q<\/mml:mi>\n \u2229<\/mml:mo>\n \n \n Z<\/mml:mi>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for some polyhedron Q<\/jats:italic>, we call Q<\/jats:italic> a relaxation of X<\/jats:italic> and define the relaxation complexity\u00a0$${\\text {rc}}(X)$$<\/jats:tex-math>\n \n rc<\/mml:mtext>\n (<\/mml:mo>\n X<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of\u00a0X<\/jats:italic> as the least number of facets among all possible relaxations\u00a0Q<\/jats:italic> of\u00a0X<\/jats:italic>. The rational relaxation complexity\u00a0$${\\text {rc}}_\\mathbb {Q}(X)$$<\/jats:tex-math>\n \n \n rc<\/mml:mtext>\n Q<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n X<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> restricts the definition of\u00a0$${\\text {rc}}(X)$$<\/jats:tex-math>\n \n rc<\/mml:mtext>\n (<\/mml:mo>\n X<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> to rational polyhedra Q<\/jats:italic>. In this article, we focus on\u00a0$$X = \\Delta _d$$<\/jats:tex-math>\n \n X<\/mml:mi>\n =<\/mml:mo>\n \n \u0394<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the vertex set of the standard simplex, which consists of the null vector and the standard unit vectors in\u00a0$$\\mathbb {R}^d$$<\/jats:tex-math>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We show that\u00a0$${\\text {rc}}(\\Delta _d) \\le d$$<\/jats:tex-math>\n \n rc<\/mml:mtext>\n (<\/mml:mo>\n \n \u0394<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n \u2264<\/mml:mo>\n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for every\u00a0$$d \\ge 5$$<\/jats:tex-math>\n \n d<\/mml:mi>\n \u2265<\/mml:mo>\n 5<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. That is, since $${\\text {rc}}_\\mathbb {Q}(\\Delta _d)=d+1$$<\/jats:tex-math>\n \n \n rc<\/mml:mtext>\n Q<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n \n \u0394<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n d<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, irrationality can reduce the minimal size of relaxations. This answers an open question posed by Kaibel and Weltge (Math Program 154(1):407\u2013425, 2015). Moreover, we prove the asymptotic statement\u00a0$${\\text {rc}}(\\Delta _d) \\in O(\\nicefrac {d}{\\sqrt{\\log (d)}})$$<\/jats:tex-math>\n \n rc<\/mml:mtext>\n \n (<\/mml:mo>\n \n \u0394<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2208<\/mml:mo>\n O<\/mml:mi>\n \n (<\/mml:mo>\n \n d<\/mml:mi>\n \n \n log<\/mml:mo>\n (<\/mml:mo>\n d<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msqrt>\n <\/mml:mfrac>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which shows that the ratio $$\\nicefrac {{\\text {rc}}(\\Delta _d)}{{\\text {rc}}_\\mathbb {Q}(\\Delta _d)}$$<\/jats:tex-math>\n \n \n \n rc<\/mml:mtext>\n (<\/mml:mo>\n \n \u0394<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n \n \n rc<\/mml:mtext>\n Q<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n \n \u0394<\/mml:mi>\n d<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> goes to\u00a00, as $$d \\rightarrow \\infty $$<\/jats:tex-math>\n \n d<\/mml:mi>\n \u2192<\/mml:mo>\n \u221e<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s10107-023-01994-w","type":"journal-article","created":{"date-parts":[[2023,7,13]],"date-time":"2023-07-13T13:01:51Z","timestamp":1689253311000},"page":"745-771","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The role of rationality in integer-programming relaxations"],"prefix":"10.1007","volume":"205","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6805-6903","authenticated-orcid":false,"given":"Manuel","family":"Aprile","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gennadiy","family":"Averkov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Di Summa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5324-8996","authenticated-orcid":false,"given":"Christopher","family":"Hojny","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,13]]},"reference":[{"issue":"1","key":"1994_CR1","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/s10107-014-0855-0","volume":"154","author":"V Kaibel","year":"2015","unstructured":"Kaibel, V., Weltge, S.: Lower bounds on the sizes of integer programs without additional variables. Math. Program. 154(1), 407\u2013425 (2015)","journal-title":"Math. Program."},{"key":"1994_CR2","doi-asserted-by":"publisher","unstructured":"Weltge, S.: Sizes of Linear Descriptions in Combinatorial Optimization. PhD thesis. Otto-von-Guericke-Universit\u00e4t Magdeburg, 2015. https:\/\/doi.org\/10.25673\/4350","DOI":"10.25673\/4350"},{"key":"1994_CR3","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0012-365X(75)90003-5","volume":"11","author":"RG Jeroslow","year":"1975","unstructured":"Jeroslow, R.G.: On defining sets of vertices of the hypercube by linear inequalities. Discrete Math. 11, 119\u2013124 (1975)","journal-title":"Discrete Math."},{"key":"1994_CR4","doi-asserted-by":"crossref","unstructured":"Averkov, G., Schymura, M.: Complexity of linear relaxations in integer programming. Math. Program., 1\u201337 (2021)","DOI":"10.1007\/s10107-021-01623-4"},{"key":"1994_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-023-00241-9","author":"G Averkov","year":"2023","unstructured":"Averkov, G., Hojny, C., Schymura, M.: Efficient MIP techniques for computing the relaxation complexity. Math. Program. Comput. (2023). https:\/\/doi.org\/10.1007\/s12532-023-00241-9","journal-title":"Math. Program. Comput."},{"key":"1994_CR6","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.1007\/s10107-021-01754-8","volume":"197","author":"G Averkov","year":"2023","unstructured":"Averkov, G., Hojny, C., Schymura, M.: Computational aspects of relaxation complexity: possibilities and limitations. Math. Program. 197, 1173\u20131200 (2023). https:\/\/doi.org\/10.1007\/s10107-021-01754-8","journal-title":"Math. Program."},{"issue":"1","key":"1994_CR7","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10479-012-1269-0","volume":"204","author":"M Conforti","year":"2013","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Extended formulations in combinatorial optimization. Ann. Oper. Res. 204(1), 97\u2013143 (2013)","journal-title":"Ann. Oper. Res."},{"issue":"3","key":"1994_CR8","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"M Yannakakis","year":"1991","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441\u2013466 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"1994_CR9","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0024-3795(93)90224-C","volume":"190","author":"JE Cohen","year":"1993","unstructured":"Cohen, J.E., Rothblum, U.G.: Nonnegative ranks, decompositions, and factorizations of nonnegative matrices. Linear Algebra Appl. 190, 149\u2013168 (1993)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"1994_CR10","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/16M1078835","volume":"1","author":"D Chistikov","year":"2017","unstructured":"Chistikov, D., Kiefer, S., Marusic, I., Shirmohammadi, M., Worrell, J.: Nonnegative matrix factorization requires irrationality. SIAM J. Appl. Algebra Geometry 1(1), 285\u2013307 (2017)","journal-title":"SIAM J. Appl. Algebra Geometry"},{"key":"1994_CR11","unstructured":"Shitov, Y.: Nonnegative rank depends on the field II. In: arXiv preprint arXiv:1605.07173 (2016)"},{"issue":"1","key":"1994_CR12","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s10107-014-0755-3","volume":"153","author":"Y Faenza","year":"2015","unstructured":"Faenza, Y., Fiorini, S., Grappe, R., Tiwary, H.R.: Extended formulations, nonnegative factorizations, and randomized communication protocols. Math. Program. 153(1), 75\u201394 (2015)","journal-title":"Math. Program."},{"issue":"2","key":"1994_CR13","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.orl.2022.01.011","volume":"50","author":"M Aprile","year":"2022","unstructured":"Aprile, M.: Extended formulations for matroid polytopes through randomized protocols. Oper. Res. Lett. 50(2), 145\u2013149 (2022)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1994_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s10107-020-01535-9","volume":"183","author":"M Aprile","year":"2020","unstructured":"Aprile, M., Faenza, Y.: Extended formulations from communication protocols in output-efficient time. Math. Program. 183(1), 41\u201359 (2020)","journal-title":"Math. Program."},{"issue":"1","key":"1994_CR15","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1287\/moor.2021.1137","volume":"47","author":"M Aprile","year":"2022","unstructured":"Aprile, M., Fiorini, S.: Regular matroids have polynomial extension complexity. Math. Oper. Res. 47(1), 540\u2013559 (2022)","journal-title":"Math. Oper. Res."},{"key":"1994_CR16","doi-asserted-by":"crossref","unstructured":"Kaibel, V., Loos, A.: Branched polyhedral systems. In: International Conference on Integer Programming and Combinatorial Optimization. Springer. pp. 177\u2013190 (2010)","DOI":"10.1007\/978-3-642-13036-6_14"},{"key":"1994_CR17","unstructured":"Tiwary, H.R., Kouteck\u2018y, M., Kolman, P.: Extension complexity, MSO logic, and treewidth. In: Discrete Mathematics & Theoretical Computer Science 22 (2020)"},{"issue":"4","key":"1994_CR18","first-page":"4","volume":"28","author":"M Aprile","year":"2021","unstructured":"Aprile, M., Fiorini, S., Huynh, T., Joret, G., Wood, D.R.: Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond. Electr. J. Combinat. 28(4), 4\u201347 (2021)","journal-title":"Electr. J. Combinat."},{"issue":"3","key":"1994_CR19","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0167-6377(91)90028-N","volume":"10","author":"RK Martin","year":"1991","unstructured":"Martin, R.K.: Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett. 10(3), 119\u2013128 (1991)","journal-title":"Oper. Res. Lett."},{"key":"1994_CR20","unstructured":"Wong, R.T.: Integer programming formulations of the traveling salesman problem. In: Proceedings of the IEEE International Conference of Circuits and Computers. IEEE Press Piscataway NJ., pp. 149\u2013152 (1980)"},{"issue":"2","key":"1994_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2716307","volume":"62","author":"S Fiorini","year":"2015","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., De Wolf, R.: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM (JACM) 62(2), 1\u201323 (2015)","journal-title":"J. ACM (JACM)"},{"issue":"6","key":"1994_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3127497","volume":"64","author":"T Rothvo\u00df","year":"2017","unstructured":"Rothvo\u00df, T.: The matching polytope has exponential extension complexity. J. ACM (JACM) 64(6), 1\u201319 (2017)","journal-title":"J. ACM (JACM)"},{"key":"1994_CR23","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1987","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, London (1987)"},{"key":"1994_CR24","unstructured":"Gruber, P., Lekkerkerker, C.G.: Geometry of Numbers, 2-nd edition (1987)"},{"key":"1994_CR25","unstructured":"Developers, S.: SageMath, the Sage Mathematics Software System (Version 9.3) (2021).https:\/\/www.sagemath.org"},{"key":"1994_CR26","doi-asserted-by":"crossref","unstructured":"Henk, M., Richter-Gebert, J., Ziegler, G.M.: Basic properties of convex polytopes. In: Handbook of Discrete and Computational Geometry, pp. 255\u2013382 (2004)","DOI":"10.1201\/9781420035315.pt2"},{"key":"1994_CR27","unstructured":"Lee, C.W., Santos, F.: Subdivisions and triangulations of polytopes. In: Handbook of Discrete and Computational Geometry. Chapman and Hall\/CRC, pp. 415\u2013447 (2017)"},{"key":"1994_CR28","unstructured":"van, Lint, J.H., Wilson, R.M.: A Course in Combinatorics. Repr. Cambridge: Cambridge University Press (1993)"},{"key":"1994_CR29","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/BF01171114","volume":"27","author":"E Sperner","year":"1928","unstructured":"Sperner, E.: Ein Satz \u00fcber Untermengen einer endlichen Menge. Mathematische Zeitschrift 27, 544\u2013548 (1928)","journal-title":"Mathematische Zeitschrift"},{"key":"1994_CR30","unstructured":"Odlyzko, A.M.: Asymptotic enumeration methods. In: R. L. Graham, M. Gr\u00f6tschel, and L. Lov\u00e1sz (Eds.) Handbook of Combinatorics. Vol. 2. 1063. North-Holland, Chap. 22 (1995)"},{"key":"1994_CR31","volume-title":"The Probabilistic Method","author":"N Alon","year":"2016","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley, London (2016)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01994-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-01994-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01994-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T14:17:21Z","timestamp":1712413041000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-01994-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,13]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1994"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-01994-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2023,7,13]]},"assertion":[{"value":"26 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}