乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:52Z","timestamp":1740109312579,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T00:00:00Z","timestamp":1683936000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T00:00:00Z","timestamp":1683936000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["239904186"],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,7]]},"abstract":"Abstract<\/jats:title>This article investigates smallest branch-and-bound trees and their computation. We first revisit the notion of hiding sets to deduce lower bounds on the size of branch-and-bound trees for certain binary programs, using both variable disjunctions and general disjunctions. We then provide exponential lower bounds for variable disjunctions by a disjoint composition of smaller binary programs. Moreover, we investigate the complexity of finding small branch-and-bound trees using variable disjunctions: We show that it is not possible to approximate the size of a smallest branch-and-bound tree within a factor of\u00a0

$$\\smash {2^{\\frac{1}{5}n}}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \n \n 1<\/mml:mn>\n 5<\/mml:mn>\n <\/mml:mfrac>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mpadded>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in time\u00a0

$$O(2^{\\delta n})$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n 2<\/mml:mn>\n \n \u03b4<\/mml:mi>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with

$$\\delta <\\tfrac{1}{5}$$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n <<\/mml:mo>\n \n \n 1<\/mml:mn>\n 5<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:mstyle>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, unless the strong exponential time hypothesis fails. Similarly, for any\u00a0

$$\\varepsilon > 0$$<\/jats:tex-math>\n \n \u03b5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, no polynomial time

$$\\smash {2^{(\\frac{1}{2} - \\varepsilon )n}}$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \n (<\/mml:mo>\n \n 1<\/mml:mn>\n 2<\/mml:mn>\n <\/mml:mfrac>\n -<\/mml:mo>\n \u03b5<\/mml:mi>\n )<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mpadded>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation is possible, unless\u00a0

$$\\text {P} = \\text {NP} $$<\/jats:tex-math>\n \n P<\/mml:mtext>\n =<\/mml:mo>\n NP<\/mml:mtext>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We also show that computing the size of a smallest branch-and-bound tree exactly is\u00a0

$${\\#P} $$<\/jats:tex-math>\n \n #<\/mml:mo>\n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard. Similar results hold for estimating the size of the tree produced by branching rules like most-infeasible branching. Finally, we discuss that finding small branch-and-bound trees generalizes finding short treelike resolution refutations, and thus non-automatizability results transfer from this setting.<\/jats:p>","DOI":"10.1007\/s10107-023-01968-y","type":"journal-article","created":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T09:02:38Z","timestamp":1683968558000},"page":"145-173","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On computing small variable disjunction branch-and-bound trees"],"prefix":"10.1007","volume":"206","author":[{"given":"Max","family":"Gl\u00e4ser","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0947-7193","authenticated-orcid":false,"given":"Marc E.","family":"Pfetsch","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,13]]},"reference":[{"key":"1968_CR1","unstructured":"Achterberg, T.: Constraint integer programming. Dissertation, TU Berlin (2007)"},{"key":"1968_CR2","doi-asserted-by":"publisher","unstructured":"Achterberg, T., Berthold, T.: Hybrid branching. In: van Hoeve, W., Hooker, J. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2009, LNCS, vol. 5547, pp. 309\u2013311. Springer (2009). https:\/\/doi.org\/10.1007\/978-3-642-01929-6_23","DOI":"10.1007\/978-3-642-01929-6_23"},{"issue":"1","key":"1968_CR3","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.orl.2004.04.002","volume":"33","author":"T Achterberg","year":"2005","unstructured":"Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33(1), 42\u201354 (2005). https:\/\/doi.org\/10.1016\/j.orl.2004.04.002","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"1968_CR4","doi-asserted-by":"publisher","first-page":"1347","DOI":"10.1137\/06066850X","volume":"38","author":"M Alekhnovich","year":"2008","unstructured":"Alekhnovich, M., Razborov, A.A.: Resolution is not automatizable unless W[P] is tractable. SIAM J. Comput. 38(4), 1347\u20131363 (2008). https:\/\/doi.org\/10.1137\/06066850X","journal-title":"SIAM J. Comput."},{"key":"1968_CR5","doi-asserted-by":"publisher","unstructured":"Arora, S., Barak, B.: Computational complexity: a modern approach. Cambridge University Press (2009). https:\/\/doi.org\/10.1017\/CBO9780511804090","DOI":"10.1017\/CBO9780511804090"},{"issue":"5","key":"1968_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3409472","volume":"67","author":"A Atserias","year":"2020","unstructured":"Atserias, A., M\u00fcller, M.: Automating resolution is NP-hard. J. ACM 67(5), 1\u201317 (2020). https:\/\/doi.org\/10.1145\/3409472","journal-title":"J. ACM"},{"key":"1968_CR7","doi-asserted-by":"publisher","unstructured":"Basu, A., Conforti, M., Di\u00a0Summa, M., Jiang, H.: Complexity of branch-and-bound and cutting planes in mixed-integer optimization \u2013 II. In: Singh, M., Williamson, D.P. (eds.) Integer Programming and Combinatorial Optimization, LNCS, vol. 12707, pp. 383\u2013398. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-73879-2_27","DOI":"10.1007\/978-3-030-73879-2_27"},{"key":"1968_CR8","doi-asserted-by":"publisher","unstructured":"Beame, P., Fleming, N., Impagliazzo, R., Kolokolova, A., Pankratov, D., Pitassi, T., Robere, R.: Stabbing planes. In: Karlin, A.R. (ed.) 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a094, pp. 10:1\u201310:20. Schloss Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2018.10","DOI":"10.4230\/LIPIcs.ITCS.2018.10"},{"key":"1968_CR9","doi-asserted-by":"publisher","unstructured":"Beame, P., Pitassi, T.: Simplified and improved resolution lower bounds. In: Proceedings of 37th Conference on Foundations of Computer Science (FOCS), pp. 274\u2013282. IEEE (1996). https:\/\/doi.org\/10.1109\/SFCS.1996.548486","DOI":"10.1109\/SFCS.1996.548486"},{"key":"1968_CR10","doi-asserted-by":"publisher","unstructured":"Berthold, T., Salvagnin, D.: Cloud branching. In: Gomes, C., Sellmann, M. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2013, LNCS, vol. 7874, pp. 28\u201343. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-642-38171-3_3","DOI":"10.1007\/978-3-642-38171-3_3"},{"issue":"6","key":"1968_CR11","doi-asserted-by":"publisher","first-page":"1939","DOI":"10.1137\/S0097539798353230","volume":"29","author":"ML Bonet","year":"2000","unstructured":"Bonet, M.L., Pitassi, T., Raz, R.: On interpolation and automatization for Frege systems. SIAM J. Comput. 29(6), 1939\u20131967 (2000). https:\/\/doi.org\/10.1137\/S0097539798353230","journal-title":"SIAM J. Comput."},{"key":"1968_CR12","doi-asserted-by":"publisher","unstructured":"Dadush, D., Tiwari, S.: On the Complexity of Branching Proofs. In: Saraf, S. (ed.) 35th Computational Complexity Conference (CCC 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 169, pp. 34:1\u201334:35. Schloss Dagstuhl, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2020.34","DOI":"10.4230\/LIPIcs.CCC.2020.34"},{"key":"1968_CR13","doi-asserted-by":"publisher","unstructured":"Dey, S.S., Dubey, Y., Molinaro, M.: Branch-and-bound solves random binary IPs in polytime. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 579\u2013591. SIAM (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.35","DOI":"10.1137\/1.9781611976465.35"},{"key":"1968_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01781-z","author":"SS Dey","year":"2022","unstructured":"Dey, S.S., Dubey, Y., Molinaro, M.: Lower bounds on the size of general branch-and-bound trees. Math. Program. (2022). https:\/\/doi.org\/10.1007\/s10107-022-01781-z","journal-title":"Math. Program."},{"key":"1968_CR15","unstructured":"Dey, S.S., Dubey, Y., Molinaro, M., Shah, P.: A theoretical and computational analysis of full strong-branching. arXiv preprint arXiv:2110.10754 (2021)"},{"key":"1968_CR16","doi-asserted-by":"publisher","unstructured":"Eickmeyer, K., Grohe, M., Gr\u00fcber, M.: Approximation of natural W[P]-complete minimisation problems is hard. In: 2008 23rd Annual IEEE Conference on Computational Complexity, pp. 8\u201318. IEEE (2008). https:\/\/doi.org\/10.1109\/CCC.2008.24","DOI":"10.1109\/CCC.2008.24"},{"key":"1968_CR17","doi-asserted-by":"publisher","unstructured":"Gl\u00e4ser, M., Pfetsch, M.E.: On the complexity of finding shortest variable disjunction branch-and-bound proofs. In: Aardal, K., Sanit\u00e0, L. (eds.) Integer Programming and Combinatorial Optimization, pp. 291\u2013304. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-06901-7_22","DOI":"10.1007\/978-3-031-06901-7_22"},{"issue":"2","key":"1968_CR18","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.ipl.2015.09.015","volume":"116","author":"C Haase","year":"2016","unstructured":"Haase, C., Kiefer, S.: The complexity of the kth largest subset problem and related problems. Inf. Process. Lett. 116(2), 111\u2013115 (2016). https:\/\/doi.org\/10.1016\/j.ipl.2015.09.015","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"1968_CR19","doi-asserted-by":"publisher","first-page":"934","DOI":"10.1287\/ijoc.2021.1103","volume":"34","author":"G Hendel","year":"2021","unstructured":"Hendel, G., Anderson, D., Bodic, P.L., Pfetsch, M.E.: Estimating the size of branch-and-bound trees. INFORMS J. Comput. 34(2), 934\u2013952 (2021). https:\/\/doi.org\/10.1287\/ijoc.2021.1103","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"1968_CR20","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1968_CR21","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF01580225","volume":"6","author":"RG Jeroslow","year":"1974","unstructured":"Jeroslow, R.G.: Trivial integer programs unsolvable by branch-and-bound. Math. Program. 6(1), 105\u2013109 (1974). https:\/\/doi.org\/10.1007\/BF01580225","journal-title":"Math. Program."},{"issue":"1","key":"1968_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), 407\u2013425 (2015). https:\/\/doi.org\/10.1007\/s10107-014-0855-0","journal-title":"Math. Program."},{"issue":"129","key":"1968_CR23","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1090\/S0025-5718-1975-0373371-6","volume":"29","author":"DE Knuth","year":"1975","unstructured":"Knuth, D.E.: Estimating the efficiency of backtrack programs. Math. Comput. 29(129), 122\u2013136 (1975). https:\/\/doi.org\/10.1090\/S0025-5718-1975-0373371-6","journal-title":"Math. Comput."},{"key":"1968_CR24","doi-asserted-by":"publisher","unstructured":"Kraj\u00ed\u010dek, J.: Proof complexity. Cambridge University Press (2019). https:\/\/doi.org\/10.1017\/9781108242066","DOI":"10.1017\/9781108242066"},{"issue":"1","key":"1968_CR25","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s10107-016-1101-8","volume":"166","author":"P Le Bodic","year":"2017","unstructured":"Le Bodic, P., Nemhauser, G.: An abstract model for branching and its application to mixed integer programming. Math. Program. 166(1), 369\u2013405 (2017). https:\/\/doi.org\/10.1007\/s10107-016-1101-8","journal-title":"Math. Program."},{"issue":"4","key":"1968_CR26","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1137\/0214060","volume":"14","author":"L Stockmeyer","year":"1985","unstructured":"Stockmeyer, L.: On approximation algorithms for #P. SIAM J. Comput. 14(4), 849\u2013861 (1985). https:\/\/doi.org\/10.1137\/0214060","journal-title":"SIAM J. Comput."},{"issue":"5","key":"1968_CR27","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865\u2013877 (1991). https:\/\/doi.org\/10.1137\/0220053","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1968_CR28","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8(2), 189\u2013201 (1979). https:\/\/doi.org\/10.1016\/0304-3975(79)90044-6","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1968_CR29","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979). https:\/\/doi.org\/10.1137\/0208032","journal-title":"SIAM J. Comput."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01968-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-01968-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01968-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T12:19:45Z","timestamp":1721823585000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-01968-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,13]]},"references-count":29,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["1968"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-01968-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2023,5,13]]},"assertion":[{"value":"16 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}