{"id":45210,"date":"2023-04-10T11:36:38","date_gmt":"2023-04-10T15:36:38","guid":{"rendered":"https:\/\/engineering.jhu.edu\/ams\/?post_type=tribe_events&#038;p=45210"},"modified":"2023-04-26T12:36:42","modified_gmt":"2023-04-26T16:36:42","slug":"ams-seminar-prof-santanu-dey","status":"publish","type":"tribe_events","link":"https:\/\/engineering.jhu.edu\/ams\/event\/ams-seminar-prof-santanu-dey\/","title":{"rendered":"AMS Seminar | Professor Santanu Dey"},"content":{"rendered":"<div>\n<p><strong><span>Location:\u00a0<\/span><\/strong><span>Gilman 132<\/span><\/p>\n<\/div>\n<div>\n<p><strong><span>When: <\/span><\/strong>April 27th\u00a0at 1:30 p.m.<span><\/span><\/p>\n<\/div>\n<div>\n<p><strong><span>Title:<\/span><\/strong> <span>Theoretical and computational analysis of sizes of branch-and-bound trees<\/span><\/p>\n<\/div>\n<div>\n<p><strong><span>Abstract:\u00a0<\/span><\/strong><span>The branch-and-bound algorithm was invented for solving integer programs (IP) in 1960. Since then, there is limited theoretical analysis of the branch-and-bound algorithm, even though the algorithm is the workhorse of all modern IP solvers. We try and answer some of the following basic questions regarding the branch-and-bound algorithm in this talk: (i) While it is known that the size of simple branch-and-bound trees can be exponential in size in the worst case, can we prove smaller size of branch-and-bound tree under a random model for the instances? (ii) Most lower bounds on size of branch-and-bound tree are for simple disjunctions. Can we prove similar lower bounds for general disjunctions? (iii) Can we analyze the performance of well-known branching rules like the full strong branching?<\/span><\/p>\n<p><span>This is joint work with Yatharth Dubey, Marco Molinaro, and Prachi Shah.<\/span><\/p>\n<p><strong>Zoom link:<\/strong> https:\/\/wse.zoom.us\/j\/95738965246<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Location:\u00a0Gilman 132 When: April 27th\u00a0at 1:30 p.m. Title: Theoretical and computational analysis of sizes of branch-and-bound trees Abstract:\u00a0The branch-and-bound algorithm was invented for solving integer programs (IP) in 1960. Since&hellip;<\/p>\n","protected":false},"author":69,"featured_media":0,"template":"","meta":{"_acf_changed":false,"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_tribe_events_status":"","_tribe_events_status_reason":"","footnotes":""},"tags":[],"tribe_events_cat":[260],"class_list":["post-45210","tribe_events","type-tribe_events","status-publish","hentry","tribe_events_cat-seminars-and-endowed-lectures","cat_seminars-and-endowed-lectures"],"acf":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.8 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>AMS Seminar | Professor Santanu Dey | Department of Applied Mathematics and Statistics<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/engineering.jhu.edu\/ams\/event\/ams-seminar-prof-santanu-dey\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"AMS Seminar | Professor Santanu Dey | Department of Applied Mathematics and Statistics\" \/>\n<meta property=\"og:description\" content=\"Location:\u00a0Gilman 132 When: April 27th\u00a0at 1:30 p.m. Title: Theoretical and computational analysis of sizes of branch-and-bound trees Abstract:\u00a0The branch-and-bound algorithm was invented for solving integer programs (IP) in 1960. Since&hellip;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/engineering.jhu.edu\/ams\/event\/ams-seminar-prof-santanu-dey\/\" \/>\n<meta property=\"og:site_name\" content=\"Department of Applied Mathematics and Statistics\" \/>\n<meta property=\"article:modified_time\" content=\"2023-04-26T16:36:42+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"AMS Seminar | Professor Santanu Dey | Department of Applied Mathematics and Statistics","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/engineering.jhu.edu\/ams\/event\/ams-seminar-prof-santanu-dey\/","og_locale":"en_US","og_type":"article","og_title":"AMS Seminar | Professor Santanu Dey | Department of Applied Mathematics and Statistics","og_description":"Location:\u00a0Gilman 132 When: April 27th\u00a0at 1:30 p.m. Title: Theoretical and computational analysis of sizes of branch-and-bound trees Abstract:\u00a0The branch-and-bound algorithm was invented for solving integer programs (IP) in 1960. Since&hellip;","og_url":"https:\/\/engineering.jhu.edu\/ams\/event\/ams-seminar-prof-santanu-dey\/","og_site_name":"Department of Applied Mathematics and Statistics","article_modified_time":"2023-04-26T16:36:42+00:00","twitter_card":"summary_large_image","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/engineering.jhu.edu\/ams\/event\/ams-seminar-prof-santanu-dey\/","url":"https:\/\/engineering.jhu.edu\/ams\/event\/ams-seminar-prof-santanu-dey\/","name":"AMS Seminar | Professor Santanu Dey | Department of Applied Mathematics and Statistics","isPartOf":{"@id":"https:\/\/engineering.jhu.edu\/ams\/#website"},"datePublished":"2023-04-10T15:36:38+00:00","dateModified":"2023-04-26T16:36:42+00:00","breadcrumb":{"@id":"https:\/\/engineering.jhu.edu\/ams\/event\/ams-seminar-prof-santanu-dey\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/engineering.jhu.edu\/ams\/event\/ams-seminar-prof-santanu-dey\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/engineering.jhu.edu\/ams\/event\/ams-seminar-prof-santanu-dey\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/engineering.jhu.edu\/ams\/"},{"@type":"ListItem","position":2,"name":"Events","item":"https:\/\/engineering.jhu.edu\/ams\/events\/"},{"@type":"ListItem","position":3,"name":"AMS Seminar | Professor Santanu Dey"}]},{"@type":"WebSite","@id":"https:\/\/engineering.jhu.edu\/ams\/#website","url":"https:\/\/engineering.jhu.edu\/ams\/","name":"Hopkins Applied Math & Statistics","description":"Department of Applied Mathematics and Statistics","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/engineering.jhu.edu\/ams\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"}]}},"distributor_meta":false,"distributor_terms":false,"distributor_media":false,"distributor_original_site_name":"Department of Applied Mathematics and Statistics","distributor_original_site_url":"https:\/\/engineering.jhu.edu\/ams","push-errors":false,"_links":{"self":[{"href":"https:\/\/engineering.jhu.edu\/ams\/wp-json\/wp\/v2\/tribe_events\/45210","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/engineering.jhu.edu\/ams\/wp-json\/wp\/v2\/tribe_events"}],"about":[{"href":"https:\/\/engineering.jhu.edu\/ams\/wp-json\/wp\/v2\/types\/tribe_events"}],"author":[{"embeddable":true,"href":"https:\/\/engineering.jhu.edu\/ams\/wp-json\/wp\/v2\/users\/69"}],"version-history":[{"count":5,"href":"https:\/\/engineering.jhu.edu\/ams\/wp-json\/wp\/v2\/tribe_events\/45210\/revisions"}],"predecessor-version":[{"id":45362,"href":"https:\/\/engineering.jhu.edu\/ams\/wp-json\/wp\/v2\/tribe_events\/45210\/revisions\/45362"}],"wp:attachment":[{"href":"https:\/\/engineering.jhu.edu\/ams\/wp-json\/wp\/v2\/media?parent=45210"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/engineering.jhu.edu\/ams\/wp-json\/wp\/v2\/tags?post=45210"},{"taxonomy":"tribe_events_cat","embeddable":true,"href":"https:\/\/engineering.jhu.edu\/ams\/wp-json\/wp\/v2\/tribe_events_cat?post=45210"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}