{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T07:35:58Z","timestamp":1742974558678,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031069000"},{"type":"electronic","value":"9783031069017"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-06901-7_22","type":"book-chapter","created":{"date-parts":[[2022,5,27]],"date-time":"2022-05-27T00:22:30Z","timestamp":1653610950000},"page":"291-304","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the\u00a0Complexity of\u00a0Finding Shortest Variable Disjunction Branch-and-Bound Proofs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6150-9431","authenticated-orcid":false,"given":"Max","family":"Gl\u00e4ser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0947-7193","authenticated-orcid":false,"given":"Marc E.","family":"Pfetsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,27]]},"reference":[{"key":"22_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/978-3-642-01929-6_23","volume-title":"Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems","author":"T Achterberg","year":"2009","unstructured":"Achterberg, T., Berthold, T.: Hybrid branching. In: van Hoeve, W.-J., Hooker, J.N. (eds.) CPAIOR 2009. LNCS, vol. 5547, pp. 309\u2013311. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-01929-6_23"},{"issue":"1","key":"22_CR2","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":"22_CR3","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":"22_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009). https:\/\/doi.org\/10.1017\/CBO9780511804090"},{"issue":"5","key":"22_CR5","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":"22_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/978-3-030-73879-2_27","volume-title":"Integer Programming and Combinatorial Optimization","author":"Amitabh Basu","year":"2021","unstructured":"Basu, Amitabh, Conforti, Michele, Di Summa, Marco, Jiang, Hongyi: Complexity of branch-and-bound and cutting planes in mixed-integer optimization - II. In: Singh, Mohit, Williamson, David P.. (eds.) IPCO 2021. LNCS, vol. 12707, pp. 383\u2013398. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-73879-2_27"},{"key":"22_CR7","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":"22_CR8","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/978-3-642-38171-3_3","volume-title":"Cloud Branching","author":"T Berthold","year":"2013","unstructured":"Berthold, T., Salvagnin, D.: Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. In: Gomes, C., Sellmann, M. (eds.) Cloud Branching. LNCS, vol. 7874, pp. 28\u201343. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-642-38171-3_3"},{"issue":"6","key":"22_CR9","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."},{"issue":"1","key":"22_CR10","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0166-218X(87)90039-4","volume":"18","author":"W Cook","year":"1987","unstructured":"Cook, W., Coullard, C.R., Tur\u00e1n, G.: On the complexity of cutting-plane proofs. Discrete Appl. Math. 18(1), 25\u201338 (1987). https:\/\/doi.org\/10.1016\/0166-218X(87)90039-4","journal-title":"Discrete Appl. Math."},{"key":"22_CR11","doi-asserted-by":"publisher","unstructured":"Dadush, D., Tiwari, S.: On the complexity of branching proofs. In: Proceedings of the 35th Computational Complexity Conference. Schloss Dagstuhl, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2020.34","DOI":"10.4230\/LIPIcs.CCC.2020.34"},{"key":"22_CR12","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":"22_CR13","doi-asserted-by":"crossref","unstructured":"Dey, S.S., Shah, P.: Lower bound on size of branch-and-bound trees for solving lot-sizing problem. arXiv preprint arXiv:2112.03965 (2021)","DOI":"10.1016\/j.orl.2022.04.008"},{"key":"22_CR14","doi-asserted-by":"publisher","unstructured":"Eickmeyer, K., Grohe, M., Gr\u00fcber, M.: Approximation of natural W[P]-complete minimisation problems is hard. In: 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":"22_CR15","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., Le Bodic, P., Pfetsch, M.E.: Estimating the size of branch-and-bound trees. INFORMS J. Comput. 34, 934\u2013952 (2021). https:\/\/doi.org\/10.1287\/ijoc.2021.1103","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"22_CR16","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":"22_CR17","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":"129","key":"22_CR18","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":"22_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/9781108242066","volume-title":"Proof Complexity","author":"J Kraj\u00ed\u010dek","year":"2019","unstructured":"Kraj\u00ed\u010dek, J.: Proof Complexity. Cambridge University Press., Cambridge (2019). https:\/\/doi.org\/10.1017\/9781108242066"},{"issue":"1","key":"22_CR20","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."},{"key":"22_CR21","doi-asserted-by":"publisher","unstructured":"Sipser, M.: A complexity theoretic approach to randomness. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of computing, pp. 330\u2013335 (1983). https:\/\/doi.org\/10.1145\/800061.808762","DOI":"10.1145\/800061.808762"},{"issue":"4","key":"22_CR22","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":"22_CR23","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":"22_CR24","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":"22_CR25","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."},{"key":"22_CR26","doi-asserted-by":"publisher","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 458\u2013463 (1985). https:\/\/doi.org\/10.1016\/0304-3975(86)90135-0","DOI":"10.1016\/0304-3975(86)90135-0"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-06901-7_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,30]],"date-time":"2022-05-30T23:04:02Z","timestamp":1653951842000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-06901-7_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031069000","9783031069017"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-06901-7_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"27 May 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Eindhoven","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.ipco2022.com\/home","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"93","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"35% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}