{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:31Z","timestamp":1740109291606,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T00:00:00Z","timestamp":1613606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T00:00:00Z","timestamp":1613606400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["185030"],"award-info":[{"award-number":["185030"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,7]]},"abstract":"Abstract<\/jats:title>For a set X<\/jats:italic> of integer points in a polyhedron, the smallest number of facets of any polyhedron whose set of integer points coincides with\u00a0X<\/jats:italic> is called the relaxation complexity\u00a0$${{\\,\\mathrm{rc}\\,}}(X)$$<\/jats:tex-math>\n \n \n \n rc<\/mml:mi>\n \n <\/mml:mrow>\n (<\/mml:mo>\n X<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This parameter, introduced by Kaibel & Weltge (2015), captures the complexity of linear descriptions of\u00a0X<\/jats:italic> without using auxiliary variables. Using tools from combinatorics, geometry of numbers, and quantifier elimination, we make progress on several open questions regarding $${{\\,\\mathrm{rc}\\,}}(X)$$<\/jats:tex-math>\n \n \n \n rc<\/mml:mi>\n \n <\/mml:mrow>\n (<\/mml:mo>\n X<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and its variant $${{\\,\\mathrm{rc}\\,}}_\\mathbb {Q}(X)$$<\/jats:tex-math>\n \n \n \n \n rc<\/mml:mi>\n \n <\/mml:mrow>\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>, restricting the descriptions of\u00a0X<\/jats:italic> to rational polyhedra. As our main results we show that $${{\\,\\mathrm{rc}\\,}}(X) = {{\\,\\mathrm{rc}\\,}}_\\mathbb {Q}(X)$$<\/jats:tex-math>\n \n \n \n rc<\/mml:mi>\n \n <\/mml:mrow>\n \n (<\/mml:mo>\n X<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \n \n \n rc<\/mml:mi>\n \n <\/mml:mrow>\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> when: (a) X<\/jats:italic> is at most four-dimensional, (b) X<\/jats:italic> represents every residue class in $$(\\mathbb {Z}\/2\\mathbb {Z})^d$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n Z<\/mml:mi>\n \/<\/mml:mo>\n 2<\/mml:mn>\n Z<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, (c) the convex hull of\u00a0X<\/jats:italic> contains an interior integer point, or (d) the lattice-width of\u00a0X<\/jats:italic> is above a certain threshold. Additionally, $${{\\,\\mathrm{rc}\\,}}(X)$$<\/jats:tex-math>\n \n \n \n rc<\/mml:mi>\n \n <\/mml:mrow>\n (<\/mml:mo>\n X<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can be algorithmically computed when\u00a0X<\/jats:italic> is at most three-dimensional, or X<\/jats:italic> satisfies one of the conditions (b), (c), or (d) above. Moreover, we obtain an improved lower bound on $${{\\,\\mathrm{rc}\\,}}(X)$$<\/jats:tex-math>\n \n \n \n rc<\/mml:mi>\n \n <\/mml:mrow>\n (<\/mml:mo>\n X<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in terms of the dimension of\u00a0X<\/jats:italic>.\n<\/jats:p>","DOI":"10.1007\/s10107-021-01623-4","type":"journal-article","created":{"date-parts":[[2021,2,19]],"date-time":"2021-02-19T15:47:09Z","timestamp":1613749629000},"page":"191-227","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Complexity of linear relaxations in integer programming"],"prefix":"10.1007","volume":"194","author":[{"given":"Gennadiy","family":"Averkov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5156-7953","authenticated-orcid":false,"given":"Matthias","family":"Schymura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,18]]},"reference":[{"key":"1623_CR1","volume-title":"Computational Study, Cook, The Traveling Salesman Problem","author":"DL Applegate","year":"2006","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., William, J.A.: Computational Study, Cook, The Traveling Salesman Problem. Princeton University Press, Princeton (2006)"},{"issue":"1","key":"1623_CR2","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s13366-012-0092-8","volume":"54","author":"G Averkov","year":"2013","unstructured":"Averkov, G.: A proof of Lov\u00e1sz\u2019s theorem on maximal lattice-free sets. Beitr. Algebra Geom. 54(1), 105\u2013109 (2013)","journal-title":"Beitr. Algebra Geom."},{"issue":"3","key":"1623_CR3","doi-asserted-by":"publisher","first-page":"1492","DOI":"10.1137\/120898371","volume":"27","author":"G Averkov","year":"2013","unstructured":"Averkov, G., Conforti, M., Del Pia, A., Di Summa, M., Faenza, Y.: On the convergence of the affine hull of the Chv\u00e1tal-Gomory closures. SIAM J. Discrete Math. 27(3), 1492\u20131502 (2013)","journal-title":"SIAM J. Discrete Math."},{"key":"1623_CR4","first-page":"2","volume":"3","author":"G Averkov","year":"2018","unstructured":"Averkov, G., Kr\u00fcmpelmann, J., Nill, B.: Lattice simplices with a fixed positive number of interior lattice points: a nearly optimal. Bound. Int. Math. Res. Not 3, 2\u201347 (2018)","journal-title":"Bound. Int. Math. Res. Not"},{"issue":"4","key":"1623_CR5","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1287\/moor.2016.0836","volume":"42","author":"G Averkov","year":"2017","unstructured":"Averkov, G., Kr\u00fcmpelmann, J., Weltge, S.: Notions of maximality for integral lattice-free polyhedra: the case of dimension three. Math. Oper. Res. 42(4), 1035\u20131062 (2017)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1623_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s13366-011-0028-8","volume":"53","author":"G Averkov","year":"2012","unstructured":"Averkov, G., Wagner, C.: Inequalities for the lattice width of lattice-free convex sets in the plane. Beitr. Algebra Geom. 53(1), 1\u201323 (2012)","journal-title":"Beitr. Algebra Geom."},{"issue":"4","key":"1623_CR7","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1287\/moor.1110.0510","volume":"36","author":"G Averkov","year":"2011","unstructured":"Averkov, G., Wagner, C., Weismantel, R.: Maximal Lattice-Free Polyhedra: Finiteness and an Explicit Description in Dimension Three. Math. Oper. Res. 36(4), 721\u2013742 (2011)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"1623_CR8","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1287\/moor.1100.0461","volume":"35","author":"A Basu","year":"2010","unstructured":"Basu, A., Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Maximal lattice-free convex sets in linear subspaces. Math. Oper. Res. 35(3), 704\u2013720 (2010)","journal-title":"Math. Oper. Res."},{"key":"1623_CR9","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-33099-2","volume-title":"Algorithms in Real Algebraic Geometry","author":"S Basu","year":"2006","unstructured":"Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics, vol. 10, 2nd edn. Springer, Berlin (2006)","edition":"2"},{"key":"1623_CR10","unstructured":"Blanco, M., Haase, C., Hofmann, J., Santos, F.: The Finiteness Threshold Width of Lattice Polytopes. https:\/\/arxiv.org\/abs\/1607.00798 (2016)"},{"issue":"2","key":"1623_CR11","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1137\/15M1014450","volume":"30","author":"M Blanco","year":"2016","unstructured":"Blanco, M., Santos, F.: Lattice 3-polytopes with few lattice points. SIAM J. Discrete Math. 30(2), 669\u2013686 (2016)","journal-title":"SIAM J. Discrete Math."},{"key":"1623_CR12","doi-asserted-by":"crossref","unstructured":"Blichfeldt, H.F.: A new principle in the geometry of numbers, with some applications. Trans. Am. Math. Soc. 15(3), 227\u2013235 (1914)","DOI":"10.1090\/S0002-9947-1914-1500976-6"},{"issue":"3","key":"1623_CR13","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1145\/1071596.1071601","volume":"6","author":"B Boigelot","year":"2005","unstructured":"Boigelot, B., Jodogne, S., Wolper, P.: An effective decision procedure for linear arithmetic over the integers and reals. ACM Trans. Comput. Logic 6(3), 614\u2013633 (2005)","journal-title":"ACM Trans. Comput. Logic"},{"issue":"2","key":"1623_CR14","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1090\/S0002-9939-1976-0396605-3","volume":"55","author":"I Borosh","year":"1976","unstructured":"Borosh, I., Treybig, L.B.: Bounds on positive integral solutions of linear Diophantine equations. Proc. Am. Math. Soc. 55(2), 299\u2013304 (1976)","journal-title":"Proc. Am. Math. Soc."},{"issue":"1","key":"1623_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10288-010-0122-z","volume":"8","author":"M Conforti","year":"2010","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR 8(1), 1\u201348 (2010)","journal-title":"4OR"},{"issue":"3","key":"1623_CR16","doi-asserted-by":"publisher","first-page":"1104","DOI":"10.1137\/120877635","volume":"26","author":"J Draisma","year":"2012","unstructured":"Draisma, J., McAllister, T.B., Nill, B.: Lattice-width directions and Minkowski\u2019s 3d-theorem. SIAM J. Discrete Math. 26(3), 1104\u20131107 (2012)","journal-title":"SIAM J. Discrete Math."},{"key":"1623_CR17","volume-title":"Gruber, Convex and Discrete Geometry, Grundlehren der Mathematischen Wissenschaften","author":"M Peter","year":"2007","unstructured":"Peter, M.: Gruber, Convex and Discrete Geometry, Grundlehren der Mathematischen Wissenschaften, vol. 336. Springer, Berlin (2007)"},{"issue":"3","key":"1623_CR18","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/3242953.3242964","volume":"5","author":"C Haase","year":"2018","unstructured":"Haase, C.: A survival guide to Presburger arithmetic. ACM SIGLOG News 5(3), 67\u201382 (2018)","journal-title":"ACM SIGLOG News"},{"key":"1623_CR19","doi-asserted-by":"crossref","unstructured":"Hammer, P.L., Ibaraki, T., Peled, U.N., Threshold numbers and threshold completions, Studies on graphs and discrete programming, vol. 11. North-Holland, Amsterdam-New York, pp. 125\u2013145 (1979)","DOI":"10.1016\/S0304-0208(08)73462-5"},{"key":"1623_CR20","unstructured":"Hojny, C.: Strong IP Formulations Need Large Coefficients. http:\/\/www.optimization-online.org\/DB_HTML\/2018\/11\/6934.html, (2018)"},{"issue":"5","key":"1623_CR21","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1016\/j.orl.2020.07.013","volume":"48","author":"C Hojny","year":"2020","unstructured":"Hojny, C.: Polynomial size IP formulations of knapsack may require exponentially large coefficients. Oper. Res. Lett. 48(5), 612\u2013618 (2020)","journal-title":"Oper. Res. Lett."},{"key":"1623_CR22","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1287\/opre.21.1.221","volume":"21","author":"GJ Robert","year":"1973","unstructured":"Robert, G.J.: There cannot be any algorithm for integer programming with quadratic constraints. Oper. Res. 21, 221\u2013224 (1973)","journal-title":"Oper. Res."},{"key":"1623_CR23","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0012-365X(75)90003-5","volume":"11","author":"G Robert","year":"1975","unstructured":"Robert, G.: Jeroslow, On defining sets of vertices of the hypercube by linear inequalities. Discrete Math. 11, 119\u2013124 (1975)","journal-title":"Discrete Math."},{"key":"1623_CR24","first-page":"2","volume":"85","author":"V Kaibel","year":"2011","unstructured":"Kaibel, V.: Extended formulations in combinatorial optimization. Optima 85, 2\u20137 (2011)","journal-title":"Optima"},{"issue":"1\u20132","key":"1623_CR25","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. Ser. B 154(1\u20132), 407\u2013425 (2015)","journal-title":"Math. Program. Ser. B"},{"issue":"1","key":"1623_CR26","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1051\/ro\/2018036","volume":"53","author":"L Liberti","year":"2019","unstructured":"Liberti, L.: Undecidability and hardness in mixed-integer nonlinear programming. RAIRO Oper. Res. 53(1), 81\u2013109 (2019)","journal-title":"RAIRO Oper. Res."},{"key":"1623_CR27","unstructured":"Lov\u00e1sz, L\u00e1szl\u00f3, Geometry of numbers and integer programming, Mathematical programming (Tokyo, : Math. Appl. (Japanese Ser.), vol. 6. SCIPRESS, Tokyo 1989, 177\u2013201 (1988)"},{"key":"1623_CR28","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF02187916","volume":"3","author":"N Megiddo","year":"1988","unstructured":"Megiddo, N.: On the complexity of polyhedral separability. Discrete Comput. Geom. 3, 325\u2013337 (1988)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"1623_CR29","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1287\/moor.1110.0503","volume":"36","author":"B Nill","year":"2011","unstructured":"Nill, B., Ziegler, G.M.: Projecting lattice polytopes without interior lattice points. Math. Oper. Res. 36(3), 462\u2013467 (2011)","journal-title":"Math. Oper. Res."},{"issue":"1\u20132","key":"1623_CR30","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1112\/S0025579300014339","volume":"48","author":"O Pikhurko","year":"2001","unstructured":"Pikhurko, O.: Lattice points in lattice polytopes. Mathematika 48(1\u20132), 15\u201324 (2001)","journal-title":"Mathematika"},{"key":"1623_CR31","unstructured":"Presburger, M.: \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. Comptes Rendus du I congres de Mathematiciens des Pays Slaves, pp. 92\u2013101 (1929)"},{"key":"1623_CR32","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/BF01899997","volume":"8","author":"CA Rogers","year":"1957","unstructured":"Rogers, C.A., Shephard, G.C.: The difference body of a convex body. Arch. Math. (Basel) 8, 220\u2013233 (1957)","journal-title":"Arch. Math. (Basel)"},{"key":"1623_CR33","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Chichester (1986)"},{"issue":"1","key":"1623_CR34","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. Math. Z. 27(1), 544\u2013548 (1928)","journal-title":"Math. Z."},{"key":"1623_CR35","doi-asserted-by":"publisher","DOI":"10.1525\/9780520348097","volume-title":"A Decision Method for Elementary Algebra and Geometry","author":"A Tarski","year":"1951","unstructured":"Tarski, A.: A Decision Method for Elementary Algebra and Geometry, 2nd edn. University of California Press, Berkeley (1951)","edition":"2"},{"key":"1623_CR36","volume-title":"Simple Games: Desirability Relations, Trading, Pseudoweightings","author":"AD Taylor","year":"1999","unstructured":"Taylor, A.D., Zwicker, W.S.: Simple Games: Desirability Relations, Trading, Pseudoweightings. Princeton University Press, Princeton (1999)"},{"key":"1623_CR37","doi-asserted-by":"crossref","unstructured":"Weispfenning, V.: Mixed Real-Integer Linear Quantifier Elimination. In: Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, ISSAC \u201999, (1999), pp.\u00a0129\u2013136","DOI":"10.1145\/309831.309888"},{"key":"1623_CR38","unstructured":"Weltge, S.: Sizes of Linear Descriptions in Combinatorial Optimization, Ph.D. thesis, Otto-von-Guericke-Universit\u00e4t Magdeburg, (2015)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01623-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01623-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01623-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T19:05:56Z","timestamp":1656356756000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01623-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,18]]},"references-count":38,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["1623"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01623-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2021,2,18]]},"assertion":[{"value":"23 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}