{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T16:02:52Z","timestamp":1740153772376,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T00:00:00Z","timestamp":1681171200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T00:00:00Z","timestamp":1681171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The relaxation complexity <jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\,\\textrm{rc}\\,}}(X)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mspace\/>\n                      <mml:mtext>rc<\/mml:mtext>\n                      <mml:mspace\/>\n                    <\/mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>X<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of the set of integer points <jats:italic>X<\/jats:italic> contained in a polyhedron is the minimal number of inequalities needed to formulate a linear optimization problem over <jats:italic>X<\/jats:italic> without using auxiliary variables. Besides its relevance in integer programming, this concept has interpretations in aspects of social choice, symmetric cryptanalysis, and machine learning. We employ efficient mixed-integer programming techniques to compute a robust and numerically more practical variant of the relaxation complexity. Our proposed models require row or column generation techniques and can be enhanced by symmetry handling and suitable propagation algorithms. Theoretically, we compare the quality of our models in terms of their LP relaxation values. The performance of those models is investigated on a broad test set and is underlined by their ability to solve challenging instances that could not be solved previously.<\/jats:p>","DOI":"10.1007\/s12532-023-00241-9","type":"journal-article","created":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T13:02:41Z","timestamp":1681218161000},"page":"549-580","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient MIP techniques for computing the relaxation complexity"],"prefix":"10.1007","volume":"15","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":[[2023,4,11]]},"reference":[{"key":"241_CR1","doi-asserted-by":"crossref","unstructured":"Aprile, M., Averkov, G., Di\u00a0Summa, M., Hojny, C.: The role of rationality in integer-programming relaxations. https:\/\/arxiv.org\/abs\/2206.12253 (2022)","DOI":"10.1007\/s10107-023-01994-w"},{"key":"241_CR2","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1023\/A:1013649822153","volume":"112","author":"A Astorino","year":"2002","unstructured":"Astorino, A., Gaudioso, M.: Polyhedral separability through successive LP. J. Optim. Theory Appl. 112, 265\u2013293 (2002)","journal-title":"J. Optim. Theory Appl."},{"key":"241_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01754-8","author":"G Averkov","year":"2021","unstructured":"Averkov, G., Hojny, C., Schymura, M.: Computational aspects of relaxation complexity: possibilities and limitations. Math. Program. (2021). https:\/\/doi.org\/10.1007\/s10107-021-01754-8","journal-title":"Math. Program."},{"key":"241_CR4","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":"241_CR5","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":"241_CR6","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s10107-019-01457-1","volume":"186","author":"P Bendotti","year":"2021","unstructured":"Bendotti, P., Fouilhoux, P., Rottner, C.: Orbitopal fixing for the full (sub-)orbitope and application to the unit commitment problem. Math. Program. 186, 337\u2013372 (2021). https:\/\/doi.org\/10.1007\/s10107-019-01457-1","journal-title":"Math. Program."},{"key":"241_CR7","doi-asserted-by":"publisher","unstructured":"Cevallos, A., Weltge, S., Zenklusen, R.: Lifting linear extension complexity bounds to the mixed-integer setting. In: Czumaj, A. (ed.) Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7\u201310, 2018, pp. 788\u2013807. SIAM (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.51","DOI":"10.1137\/1.9781611975031.51"},{"issue":"1","key":"241_CR8","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). https:\/\/doi.org\/10.1007\/s10479-012-1269-0","journal-title":"Ann. Oper. Res."},{"key":"241_CR9","doi-asserted-by":"crossref","unstructured":"Dundar, M.M., Wolf, M., Lakare, S., Salganicoff, M., Raykar, V.C.: Polyhedral classifier for target detection: a case study: colorectal cancer. In: ICML \u201908: Proceedings of the 25th International Conference on Machine Learning, pp. 288\u2013295 (2008)","DOI":"10.1145\/1390156.1390193"},{"key":"241_CR10","unstructured":"Fukuda, K.: cdd\/cdd+ Reference Manual. Institute for Operations Research, ETH-Zentrum, pp. 91\u2013111 (1997)"},{"key":"241_CR11","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"},{"issue":"5","key":"241_CR12","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":"241_CR13","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":"241_CR14","doi-asserted-by":"publisher","unstructured":"Hojny, C.: christopherhojny\/relaxation_complexity: Version 1.0.0 (2023). https:\/\/doi.org\/10.5281\/zenodo.7755327","DOI":"10.5281\/zenodo.7755327"},{"key":"241_CR15","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/s10107-018-1239-7","volume":"175","author":"C Hojny","year":"2019","unstructured":"Hojny, C., Pfetsch, M.E.: Polytopes associated with symmetry handling. Math. Program. 175, 197\u2013240 (2019). https:\/\/doi.org\/10.1007\/s10107-018-1239-7","journal-title":"Math. Program."},{"key":"241_CR16","doi-asserted-by":"publisher","DOI":"10.1002\/9781118033036","volume-title":"Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction","author":"JN Hooker","year":"2000","unstructured":"Hooker, J.N.: Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction. Wiley, New York (2000)"},{"key":"241_CR17","unstructured":"Hrube\u0161, P., Talebanfard, N.: On the extension complexity of polytopes separating subsets of the Boolean cube. arXiv: 2105.11996 (2021)"},{"key":"241_CR18","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":"241_CR19","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. Theor. Comput. Sci. 6, 93\u2013107 (1978)","journal-title":"Theor. Comput. Sci."},{"key":"241_CR20","unstructured":"Junttila, T., Kaski, P.: bliss: A tool for computing automorphism groups and canonical labelings of graphs. http:\/\/www.tcs.hut.fi\/Software\/bliss\/ (2012)"},{"key":"241_CR21","first-page":"2","volume":"85","author":"V Kaibel","year":"2011","unstructured":"Kaibel, V.: Extended formulations in combinatorial optimization. Optima 85, 2\u20137 (2011). (Newsletter of the Mathematical Optimization Society)","journal-title":"Optima"},{"issue":"1\u20132, Ser. B","key":"241_CR22","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."},{"key":"241_CR23","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1007\/s11590-015-0917-0","volume":"10","author":"S Kurz","year":"2016","unstructured":"Kurz, S., Napel, S.: Dimension of the Lisbon voting rules in the EU council: a challenge and new world record. Optim. Lett. 10, 1245\u20131256 (2016)","journal-title":"Optim. Lett."},{"key":"241_CR24","unstructured":"Manwani, N., Sastry, P.S.: Learning polyhedral classifiers using logistic function. In: Sugiyama, M., Yang, Q. (eds.) Proceedings of 2nd Asian Conference on Machine Learning, Proceedings of Machine Learning Research, vol.\u00a013, pp. 17\u201330. PMLR, Tokyo, Japan (2010). https:\/\/proceedings.mlr.press\/v13\/manwani10a.html"},{"key":"241_CR25","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s10589-007-9041-0","volume":"38","author":"C Orsenigo","year":"2007","unstructured":"Orsenigo, C., Vercellis, C.: Accurately learning from few examples with a polyhedral classifier. Comput. Optim. Appl. 38, 235\u2013247 (2007)","journal-title":"Comput. Optim. Appl."},{"key":"241_CR26","unstructured":"Ryan, D., Foster, B.: An integer programming approach to scheduling. In: Wren, A. (ed.) Computer scheduling of public transport: Urban passenger vehicle and crew scheduling. North-Holland, pp. 269\u2013280 (1981)"},{"issue":"1","key":"241_CR27","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0167-6377(93)90079-V","volume":"13","author":"JK Sankaran","year":"1993","unstructured":"Sankaran, J.K.: A note on resolving infeasibility in linear programs by constraint relaxation. Oper. Res. Lett. 13(1), 19\u201320 (1993). https:\/\/doi.org\/10.1016\/0167-6377(93)90079-V","journal-title":"Oper. Res. Lett."},{"key":"241_CR28","first-page":"158","volume-title":"Advances in Cryptology - ASIACRYPT 2014","author":"S Sun","year":"2014","unstructured":"Sun, S., Hu, L., Wang, P., Qiao, K., Ma, X., Song, L.: Automatic security evaluation and (related-key) differential characteristic search: application to simon, present, lblock, des(l) and other bit-oriented block ciphers. In: Sarkar, P., Iwata, T. (eds.) Advances in Cryptology - ASIACRYPT 2014, pp. 158\u2013178. Springer, Berlin Heidelberg (2014)"},{"key":"241_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-77645-3","volume-title":"Mathematics and Politics: Strategy, Voting, Power and Proof","author":"AD Taylor","year":"2008","unstructured":"Taylor, A.D., Pacelli, A.M.: Mathematics and Politics: Strategy, Voting, Power and Proof, 2nd edn. Springer, New York (2008)","edition":"2"},{"key":"241_CR30","unstructured":"Udovenko, A.: Milp modeling of boolean functions by minimum number of inequalities. Cryptology ePrint Archive, Report 2021\/1099. https:\/\/ia.cr\/2021\/1099 (2021)"},{"key":"241_CR31","unstructured":"van\u00a0der Hulst, R.: A Branch-Price-and-Cut Algorithm for Graph Coloring. https:\/\/essay.utwente.nl\/88263\/ (2021)"},{"key":"241_CR32","doi-asserted-by":"publisher","unstructured":"Weltge, S.: Sizes of Linear Descriptions in Combinatorial Optimization. Ph.D. thesis, Otto-von-Guericke-Universit\u00e4t Magdeburg. https:\/\/doi.org\/10.25673\/4350 (2015)","DOI":"10.25673\/4350"}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-023-00241-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-023-00241-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-023-00241-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T15:17:45Z","timestamp":1690211865000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-023-00241-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,11]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["241"],"URL":"https:\/\/doi.org\/10.1007\/s12532-023-00241-9","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"type":"print","value":"1867-2949"},{"type":"electronic","value":"1867-2957"}],"subject":[],"published":{"date-parts":[[2023,4,11]]},"assertion":[{"value":"10 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The code generated during the current study is available in the github repository  (githash c2edaaae). A persistent link to the code can be found in [].","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}