{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:48Z","timestamp":1740109308634,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T00:00:00Z","timestamp":1640822400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T00:00:00Z","timestamp":1640822400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Brandenburgische TU Cottbus-Senftenberg"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,2]]},"abstract":"Abstract<\/jats:title>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> of the set of integer points\u00a0X<\/jats:italic> contained in a polyhedron is the smallest number of facets of any polyhedron\u00a0P<\/jats:italic> such that the integer points in\u00a0P<\/jats:italic> coincide with\u00a0X<\/jats:italic>. It is a useful tool to investigate the existence of compact linear descriptions of\u00a0X<\/jats:italic>. In this article, we derive tight and computable upper bounds on\u00a0$${{\\,\\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>, a variant of\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> in which the polyhedra\u00a0P<\/jats:italic> are required to be rational, and we show that\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> can be computed in polynomial time if\u00a0X<\/jats:italic> is 2-dimensional. Further, we investigate computable lower bounds on\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> with the particular focus on the existence of a finite set\u00a0$$Y \\subseteq \\mathbb {Z}^d$$<\/jats:tex-math>\n \n Y<\/mml:mi>\n \u2286<\/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> such that separating\u00a0X<\/jats:italic> and\u00a0$$Y \\setminus X$$<\/jats:tex-math>\n \n Y<\/mml:mi>\n \\<\/mml:mo>\n X<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> allows us to deduce $${{\\,\\mathrm{rc}\\,}}(X) \\ge k$$<\/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 \u2265<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In particular, we show for some choices of\u00a0X<\/jats:italic> that no such finite set\u00a0Y<\/jats:italic> exists to certify the value of\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>, providing a negative answer to a question by Weltge (2015). We also obtain an explicit formula for\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> for specific classes of sets\u00a0X<\/jats:italic> and present the first practically applicable approach to compute\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> for sets\u00a0X<\/jats:italic> that admit a finite certificate.<\/jats:p>","DOI":"10.1007\/s10107-021-01754-8","type":"journal-article","created":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T11:06:11Z","timestamp":1640862371000},"page":"1173-1200","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Computational aspects of relaxation complexity: possibilities and limitations"],"prefix":"10.1007","volume":"197","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2245-9958","authenticated-orcid":false,"given":"Gennadiy","family":"Averkov","sequence":"first","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"}]},{"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,12,30]]},"reference":[{"key":"1754_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-020-00246-4","author":"G Averkov","year":"2020","unstructured":"Averkov, G., Borger, C., Soprunov, I.: Classification of triples of lattice polytopes with a given mixed volume. Discrete Comput. Geom. (2020). https:\/\/doi.org\/10.1007\/s00454-020-00246-4. (online first)","journal-title":"Discrete Comput. Geom."},{"key":"1754_CR2","doi-asserted-by":"crossref","unstructured":"Averkov, G., Hojny, C., Schymura, M.: Computational Aspects of Relaxation Complexity. In: Proceedings 22nd Conference on Integer Programming and Combinatorial Optimization (IPCO), Lecture Notes in Computer Science, vol. 12707, pp. 368\u2013382. Springer, Cham (2021)","DOI":"10.1007\/978-3-030-73879-2_26"},{"key":"1754_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01623-4","author":"G Averkov","year":"2021","unstructured":"Averkov, G., Schymura, M.: Complexity of linear relaxations in integer programming. Math. Program. (2021). https:\/\/doi.org\/10.1007\/s10107-021-01623-4","journal-title":"Math. Program."},{"issue":"2","key":"1754_CR4","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s10107-017-1147-2","volume":"169","author":"J Bader","year":"2018","unstructured":"Bader, J., Hildebrand, R., Weismantel, R., Zenklusen, R.: Mixed integer reformulations of integer programs and the affine Tu-dimension of a matrix. Math. Program. 169(2), 565\u2013584 (2018). https:\/\/doi.org\/10.1007\/s10107-017-1147-2","journal-title":"Math. Program."},{"key":"1754_CR5","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s10589-016-9847-8","volume":"65","author":"P Belotti","year":"2016","unstructured":"Belotti, P., Bonami, P., Fischetti, M., Lodi, A., Monaci, M., Nogales-G\u00f3mes, A., Salvagnin, D.: On handling indicator constraints in mixed integer programming. Comput. Optim. Appl. 65, 545\u2013566 (2016)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"1754_CR6","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1007\/s00454-011-9376-2","volume":"47","author":"W Castryck","year":"2012","unstructured":"Castryck, W.: Moving out the edges of a lattice polygon. Discrete Comput. Geom. 47(3), 496\u2013518 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"1754_CR7","doi-asserted-by":"publisher","unstructured":"Cevallos, A., Weltge, S., Zenklusen, R.: Lifting linear extension complexity bounds to the mixed-integer setting. In: A.\u00a0Czumaj (ed.) Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pp. 788\u2013807. SIAM (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.51","DOI":"10.1137\/1.9781611975031.51"},{"issue":"2","key":"1754_CR8","first-page":"105","volume":"16","author":"M Conforti","year":"2011","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Corner polyhedron and intersection cuts. Surv. Oper. Res. Manag. Sci. 16(2), 105\u2013120 (2011)","journal-title":"Surv. Oper. Res. Manag. Sci."},{"issue":"1","key":"1754_CR9","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. Annals of Operations Research 204(1), 97\u2013143 (2013). https:\/\/doi.org\/10.1007\/s10479-012-1269-0","journal-title":"Annals of Operations Research"},{"key":"1754_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer programming","author":"M Conforti","year":"2014","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Integer programming, vol. 271. Springer, Cham (2014)"},{"key":"1754_CR11","doi-asserted-by":"publisher","first-page":"145","DOI":"10.4064\/aa-2-1-145-146","volume":"2","author":"JG van der Corput","year":"1936","unstructured":"van der Corput, J.G.: Verallgemeinerung einer Mordellschen Beweismethode in der Geometrie der Zahlen II. Acta Arith. 2, 145\u2013146 (1936)","journal-title":"Acta Arith."},{"key":"1754_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801389","volume-title":"An Introduction to Support Vector Machines and Other Kernel-based Learning Methods","author":"N Cristianini","year":"2000","unstructured":"Cristianini, N., Shawe-Taylor, J.: An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press, Cambridge (2000). https:\/\/doi.org\/10.1017\/CBO9780511801389"},{"key":"1754_CR13","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/S1385-7258(51)50053-7","volume":"54","author":"NG de Bruijn","year":"1951","unstructured":"de Bruijn, N.G., Erd\u0151s, P.: A colour problem for infinite graphs and a problem in the theory of relations. Indag. Math. 54, 371\u2013373 (1951). https:\/\/doi.org\/10.1016\/S1385-7258(51)50053-7","journal-title":"Indag. Math."},{"key":"1754_CR14","volume-title":"Algorithms in combinatorial geometry, monographs in theoretical computer science","author":"H Edelsbrunner","year":"1987","unstructured":"Edelsbrunner, H.: Algorithms in combinatorial geometry, monographs in theoretical computer science, vol. 10. Springer, Berlin Heidelberg (1987)"},{"key":"1754_CR15","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0890-5401(88)90049-1","volume":"77","author":"H Edelsbrunner","year":"1988","unstructured":"Edelsbrunner, H., Preparata, F.P.: Minimum polygonal separation. Inf. Comput. 77, 218\u2013232 (1988)","journal-title":"Inf. Comput."},{"key":"1754_CR16","first-page":"463","volume":"2","author":"P Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463\u2013470 (1935)","journal-title":"Compos. Math."},{"key":"1754_CR17","unstructured":"Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., Hendel, G., Hojny, C., Koch, T., Le\u00a0Bodic, P., Maher, S.J., Matter, F., Miltenberger, M., M\u00fchmer, E., M\u00fcller, B., Pfetsch, M.E., Schl\u00f6sser, F., Serrano, F., Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., Witzig, J.: The SCIP Optimization Suite 7.0. Technical report, Optimization Online (2020). http:\/\/www.optimization-online.org\/DB_HTML\/2020\/03\/7705.html"},{"key":"1754_CR18","doi-asserted-by":"crossref","unstructured":"Hammer, P.L., Ibaraki, T., Peled, U.N.: Threshold numbers and threshold completions. In: Studies on graphs and discrete programming (Brussels, 1979), Ann. Discrete Math., vol.\u00a011, pp. 125\u2013145. North-Holland, Amsterdam-New York (1981)","DOI":"10.1016\/S0304-0208(08)73462-5"},{"issue":"5","key":"1754_CR19","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":"1754_CR20","doi-asserted-by":"publisher","first-page":"100624","DOI":"10.1016\/j.disopt.2021.100624","volume":"39","author":"C Hojny","year":"2021","unstructured":"Hojny, C.: Strong IP formulations need large coefficients. Discrete Optim. 39, 100624 (2021)","journal-title":"Discrete Optim."},{"key":"1754_CR21","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":"1754_CR22","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0304-3975(78)90006-3","volume":"6","author":"D Johnson","year":"1978","unstructured":"Johnson, D., Preparata, F.: The densest hemisphere problem. Theoret. Comput. Sci. 6, 93\u2013107 (1978)","journal-title":"Theoret. Comput. Sci."},{"key":"1754_CR23","unstructured":"Kaibel, V.: Extended formulations in combinatorial optimization. Optima 85, 2\u20137 (2011). Newsletter of the Mathematical Optimization Society"},{"issue":"1\u20132, Ser. B","key":"1754_CR24","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\u20132, Ser. B), 407\u2013425 (2015)","journal-title":"Math. Program."},{"issue":"2","key":"1754_CR25","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1090\/S0002-9939-1953-0053256-2","volume":"4","author":"JB Kruskal","year":"1953","unstructured":"Kruskal, J.B.: Monotonic subsequences. Proc. Amer. Math. Soc. 4(2), 264\u2013274 (1953)","journal-title":"Proc. Amer. Math. Soc."},{"issue":"5","key":"1754_CR26","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.4153\/CJM-1991-058-4","volume":"43","author":"JC Lagarias","year":"1991","unstructured":"Lagarias, J.C., Ziegler, G.M.: Bounds for lattice polytopes containing a fixed number of interior points in a sublattice. Canad. J. Math. 43(5), 1022\u20131035 (1991)","journal-title":"Canad. J. Math."},{"issue":"2","key":"1754_CR27","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0020-0190(84)90033-4","volume":"18","author":"C Lee","year":"1984","unstructured":"Lee, C., Lee, D.: On a circle-cover minimization problem. Inf. Process. Lett. 18(2), 109\u2013115 (1984)","journal-title":"Inf. Process. Lett."},{"key":"1754_CR28","doi-asserted-by":"crossref","unstructured":"Maher, S., Miltenberger, M., Pedroso, J.P., Rehfeldt, D., Schwarz, R., Serrano, F.: PySCIPOpt: Mathematical programming in Python with the SCIP optimization suite. In: Mathematical Software\u2013ICMS 2016, pp. 301\u2013307. Springer International Publishing (2016)","DOI":"10.1007\/978-3-319-42432-3_37"},{"key":"1754_CR29","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":"4","key":"1754_CR30","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.orl.2013.03.010","volume":"41","author":"S Pokutta","year":"2013","unstructured":"Pokutta, S., Van Vyve, M.: A note on the extension complexity of the knapsack polytope. Oper. Res. Lett. 41(4), 347\u2013350 (2013)","journal-title":"Oper. Res. Lett."},{"key":"1754_CR31","unstructured":"Schrijver, A.: Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Ltd., Chichester (1986). A Wiley-Interscience Publication"},{"key":"1754_CR32","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF01896428","volume":"22","author":"J Spencer","year":"1971","unstructured":"Spencer, J.: Minimal scrambling sets of simple orders. Acta Math. Hungar. 22, 349\u2013353 (1971)","journal-title":"Acta Math. Hungar."},{"key":"1754_CR33","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, NJ (1999)"},{"key":"1754_CR34","unstructured":"The Sage Developers: SageMath, the Sage Mathematics Software System (Version 9.1) (2020). https:\/\/www.sagemath.org"},{"key":"1754_CR35","doi-asserted-by":"publisher","unstructured":"Weltge, S.: Sizes of Linear Descriptions in Combinatorial Optimization. Ph.D. thesis, Otto-von-Guericke-Universit\u00e4t Magdeburg (2015). https:\/\/doi.org\/10.25673\/4350","DOI":"10.25673\/4350"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01754-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01754-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01754-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T17:19:08Z","timestamp":1675703948000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01754-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,30]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1754"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01754-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2021,12,30]]},"assertion":[{"value":"26 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 December 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}