{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T12:56:01Z","timestamp":1753275361604,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2020,7,15]],"date-time":"2020-07-15T00:00:00Z","timestamp":1594771200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,15]],"date-time":"2020-07-15T00:00:00Z","timestamp":1594771200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1740425"],"award-info":[{"award-number":["CCF-1740425"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["615640-ForEFront"],"award-info":[{"award-number":["615640-ForEFront"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,11]]},"abstract":"Abstract<\/jats:title>In convex integer programming, various procedures have been developed to strengthen convex relaxations of sets of integer points. On the one hand, there exist several general-purpose methods that strengthen relaxations without specific knowledge of the set S<\/jats:italic> of feasible integer points, such as popular linear programming or semi-definite programming hierarchies. On the other hand, various methods have been designed for obtaining strengthened relaxations for very specific sets S<\/jats:italic> that arise in combinatorial optimization. We propose a new efficient method that interpolates between these two approaches. Our procedure strengthens any convex set containing a set $$ S \\subseteq \\{0,1\\}^n $$<\/jats:tex-math>\n \n S<\/mml:mi>\n \u2286<\/mml:mo>\n \n \n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> by exploiting certain additional information about S<\/jats:italic>. Namely, the required extra information will be in the form of a Boolean formula $$\\phi $$<\/jats:tex-math>\n \u03d5<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> defining the target set S<\/jats:italic>. The new relaxation is obtained by \u201cfeeding\u201d the convex set into the formula $$\\phi $$<\/jats:tex-math>\n \u03d5<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We analyze various aspects regarding the strength of our procedure. As one application, interpreting an iterated application of our procedure as a hierarchy, our findings simplify, improve, and extend previous results by Bienstock and Zuckerberg on covering problems.<\/jats:p>","DOI":"10.1007\/s10107-020-01542-w","type":"journal-article","created":{"date-parts":[[2020,7,15]],"date-time":"2020-07-15T11:02:29Z","timestamp":1594810949000},"page":"467-482","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Strengthening convex relaxations of 0\/1-sets using Boolean formulas"],"prefix":"10.1007","volume":"190","author":[{"given":"Samuel","family":"Fiorini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tony","family":"Huynh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Weltge","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,15]]},"reference":[{"key":"1542_CR1","doi-asserted-by":"crossref","unstructured":"Averkov, G., Kaibel, V., Weltge, S.: Maximum semidefinite and linear extension complexity of families of polytopes. Math. Program. 167(2), Ser. A, pp. 381\u2013394 (2018). MR 3755737","DOI":"10.1007\/s10107-017-1134-7"},{"key":"1542_CR2","doi-asserted-by":"crossref","unstructured":"Balas, E.: Disjunctive programming. Ann. Discrete Math. 5, 3\u201351 (1979). Discrete optimization (Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications, Banff, Alta., 1977), II. MR 558566","DOI":"10.1016\/S0167-5060(08)70342-X"},{"key":"1542_CR3","doi-asserted-by":"crossref","unstructured":"Bazzi, A., Fiorini, S., Huang, S., Svensson, O.: Small extended formulation for knapsack cover inequalities from monotone circuits. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms 2017, (2017)","DOI":"10.1137\/1.9781611974782.153"},{"key":"1542_CR4","doi-asserted-by":"crossref","unstructured":"Bazzi, A., Fiorini, S., Pokutta, S., Svensson, O.: No small linear program approximates vertex cover within a factor 2\u2013e. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp.\u00a01123\u20131142 (2015)","DOI":"10.1109\/FOCS.2015.73"},{"issue":"1","key":"1542_CR5","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.ipl.2005.09.008","volume":"97","author":"A Beimel","year":"2006","unstructured":"Beimel, A., Weinreb, E.: Monotone circuits for monotone weighted threshold functions. Inf. Process. Lett. 97(1), 12\u201318 (2006)","journal-title":"Inf. Process. Lett."},{"key":"1542_CR6","doi-asserted-by":"crossref","unstructured":"Benchetrit, Y., Fiorini, S., Huynh, T., Weltge, S.: Characterizing Polytopes Contained in the $$0\/1$$-Cube with Bounded Chv\u00e1tal-Gomory Rank. Mathematics of Operations Research (2018)","DOI":"10.1287\/moor.2017.0880"},{"issue":"1","key":"1542_CR7","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1137\/S1052623402420346","volume":"15","author":"D Bienstock","year":"2004","unstructured":"Bienstock, D., Zuckerberg, M.: Subset algebra lift operators for 0\u20131 integer programming. SIAM J. Optim. 15(1), 63\u201395 (2004). MR 2112976","journal-title":"SIAM J. Optim."},{"key":"1542_CR8","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/s10107-005-0598-z","volume":"105","author":"D Bienstock","year":"2006","unstructured":"Bienstock, D., Zuckerberg, M.: Approximate fixed-rank closures of covering problems. Math. Program. Ser. A 105, 9\u201327 (2006)","journal-title":"Math. Program. Ser. A"},{"key":"1542_CR9","unstructured":"Bienstock, D., Zuckerberg, M.: Simpler derivation of bounded pitch inequalities for set covering, and minimum knapsack sets, arXiv:1806.07435 (2018)"},{"key":"1542_CR10","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","volume":"4","author":"V Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4, 305\u2013337 (1973). MR 0313080","journal-title":"Discrete Math."},{"key":"1542_CR11","doi-asserted-by":"crossref","unstructured":"Cornu\u00e9jols, G., Lee, D.: On some polytopes contained in the 0,1 hypercube that have a small Chv\u00e1tal rank. In: International Conference on Integer Programming and Combinatorial Optimization, pp.\u00a0300\u2013311. Springer (2016)","DOI":"10.1007\/978-3-319-33461-5_25"},{"issue":"2","key":"1542_CR12","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s004930050057","volume":"19","author":"F Eisenbrand","year":"1999","unstructured":"Eisenbrand, F.: On the membership problem for the elementary closure of a polyhedron. Combinatorica 19(2), 297\u2013300 (1999)","journal-title":"Combinatorica"},{"key":"1542_CR13","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Gro\u00df, M., K\u00f6nemann, J., Sanit\u00e0, L.: Approximating weighted tree augmentation via Chv\u00e1tal-Gomory cuts. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0817\u2013831. SIAM, Philadelphia, PA (2018). MR 3775841","DOI":"10.1137\/1.9781611975031.53"},{"key":"1542_CR14","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Massar, S., Pokutta, S., Tiwary, H. R., de Wolf, R.: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM 62(2), 1\u201323 (2015)","DOI":"10.1145\/2716307"},{"key":"1542_CR15","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Jain, R., Watson, T.: Extension complexity of independent set polytopes. In: Proc. FOCS 2016, (2016)","DOI":"10.1109\/FOCS.2016.67"},{"key":"1542_CR16","doi-asserted-by":"crossref","unstructured":"Hoory, S., Magen, A., Pitassi, T.: Monotone circuits for the majority function. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, pp.\u00a0410\u2013425 (2006)","DOI":"10.1007\/11830924_38"},{"issue":"11","key":"1542_CR17","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1016\/j.ipl.2012.02.009","volume":"112","author":"Pavel Hrube\u0161","year":"2012","unstructured":"Hrube\u0161, Pavel: On the nonnegative rank of distance matrices. Inf. Process. Lett. 112(11), 457\u2013461 (2012). MR 2905148","journal-title":"Inf. Process. Lett."},{"key":"1542_CR18","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"M Karchmer","year":"1990","unstructured":"Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math. 3, 255\u2013265 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"1542_CR19","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/S0167-6377(98)00025-X","volume":"23","author":"D Klabjan","year":"1998","unstructured":"Klabjan, D., Nemhauser, G.L., Tovey, C.: The complexity of cover inequality separation. Oper. Res. Lett. 23, 35\u201340 (1998)","journal-title":"Oper. Res. Lett."},{"key":"1542_CR20","doi-asserted-by":"crossref","unstructured":"Lasserre, J. B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. Integer programming and combinatorial optimization (Utrecht, 2001), Lecture Notes in Comput. Sci., vol. 2081, pp.\u00a0293\u2013303. Springer, Berlin (2001). MR 2041934","DOI":"10.1007\/3-540-45535-3_23"},{"issue":"2","key":"1542_CR21","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and $$0$$-$$1$$ optimization. SIAM J. Optim. 1(2), 166\u2013190 (1991). MR 1098425","journal-title":"SIAM J. Optim."},{"key":"1542_CR22","doi-asserted-by":"crossref","unstructured":"Mastrolilli, M: High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts. In: Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings, pp.\u00a0405\u2013416 (2017)","DOI":"10.1007\/978-3-319-59250-3_33"},{"issue":"3","key":"1542_CR23","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1145\/146637.146684","volume":"39","author":"R Raz","year":"1992","unstructured":"Raz, R., Wigderson, Avi: Monotone circuits for matching require linear depth. J. Assoc. Comput. Mach. 39(3), 736\u2013744 (1992). MR 1177960","journal-title":"J. Assoc. Comput. Mach."},{"key":"1542_CR24","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s10107-012-0574-3","volume":"142","author":"T Rothvo\u00df","year":"2013","unstructured":"Rothvo\u00df, T.: Some 0\/1 polytopes need exponential size extended formulations. Math. Program. A 142, 255\u2013268 (2013)","journal-title":"Math. Program. A"},{"key":"1542_CR25","doi-asserted-by":"crossref","unstructured":"Rothvo\u00df, T.: The matching polytope has exponential extension complexity. J. ACM 64, no.\u00a06, Art. 41, 19 (2017). MR 3713797","DOI":"10.1145\/3127497"},{"key":"1542_CR26","unstructured":"Schrijver, A.: Combinatorial optimization. Polyhedra and efficiency. Vol. A, Algorithms and Combinatorics, vol.\u00a024, Springer-Verlag, Berlin, 2003, Paths, flows, matchings, Chapters 1\u201338. MR 1956924 (2004b:90004a)"},{"issue":"3","key":"1542_CR27","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3), 411\u2013430 (1990). MR 1061981","journal-title":"SIAM J. Discrete Math."},{"key":"1542_CR28","doi-asserted-by":"crossref","unstructured":"Singh, M., Talwar, K.: Improving integrality gaps via Chv\u00e1tal-Gomory rounding. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, pp.\u00a0366\u2013379 (2010)","DOI":"10.1007\/978-3-642-15369-3_28"},{"issue":"1","key":"1542_CR29","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0020-0190(83)90011-X","volume":"16","author":"I Wegener","year":"1983","unstructured":"Wegener, I.: Relating monotone formula size and monotone depth of Boolean functions. Inf. Process. Lett. 16(1), 41\u201342 (1983)","journal-title":"Inf. Process. Lett."},{"key":"1542_CR30","unstructured":"Weltge, S.: Sizes of linear descriptions in combinatorial optimization. dissertation, Otto-von-Guericke-Universit\u00e4t Magdeburg, (2016)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01542-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01542-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01542-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T02:47:30Z","timestamp":1633834050000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01542-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,15]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["1542"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01542-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,7,15]]},"assertion":[{"value":"1 February 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}