{"681567":{"#nid":"681567","#data":{"type":"event","title":"PhD Defense by Prachi Shah","body":[{"value":"\u003Cp\u003ETitle: Closing the Gap: A Theoretical and Practical Exploration of Branch-and-Bound for MIPs\u003C\/p\u003E\u003Cp\u003EDate:\u0026nbsp;April 9th, 2025\u003C\/p\u003E\u003Cp\u003ETime:\u0026nbsp;12 PM \u2013 2:00 PM\u003C\/p\u003E\u003Cp\u003ELocation: Groseclose 303\u003C\/p\u003E\u003Cp\u003EMeeting Link: \u003Ca href=\u0022https:\/\/gatech.zoom.us\/j\/99775221586\u0022\u003Ehttps:\/\/gatech.zoom.us\/j\/99775221586\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003EPrachi Shah\u003C\/p\u003E\u003Cp\u003EOperations Research PhD Student\u003C\/p\u003E\u003Cp\u003EH. Milton Stewart School of Industrial and Systems Engineering\u003C\/p\u003E\u003Cp\u003EGeorgia Institute of Technology\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003ECommittee:\u003C\/p\u003E\u003Cp\u003EDr. Santanu Dey (Advisor), H. Milton Stewart School of Industrial and Systems Engineering\u003C\/p\u003E\u003Cp\u003EDr. Nick Sahinidis, H. Milton Stewart School of Industrial and Systems Engineering\u003C\/p\u003E\u003Cp\u003EDr. Mohit Singh, H. Milton Stewart School of Industrial and Systems Engineering\u003C\/p\u003E\u003Cp\u003EDr. Alejandro Toriello, H. Milton Stewart School of Industrial and Systems Engineering\u003C\/p\u003E\u003Cp\u003EDr. Luke Marshall, Microsoft Research\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EThe branch-and-bound scheme, invented by Land and Doig, is the method of choice for solving mixed integer linear programs (MILP) by all modern state-of-the-art MILP solvers. While the branch-and-bound algorithm has been studied for a long time, a theoretical understanding of its performance guarantees is lacking. Furthermore, in practice, its efficiency relies on the performance of several heuristics whose interactions are not well understood. This thesis is motivated by the goal to improve both theoretical as well as practical understanding of branch-and-bound for MILPs. Given that node selection rules are well-understood, this thesis focuses primarily on branching rules.\u003C\/p\u003E\u003Cp\u003EIn Chapter 2, we consider the lot-sizing problem for which there exists a polynomial time dynamic programming algorithm and prove an (worst case) exponential lower bound on the size of branch-and-bound trees even when branching is considered on general disjunctions. In Chapter 3, we consider the question of whether adding cuts will always lead to smaller trees for a given fixed branching rule. We formally call such a property of a branching rule monotonicity. We prove that most of the standard branching rules used in practice are non-monotonic. We also empirically attempt to estimate the prevalence of non-monotonicity in practice while using full strong-branching and discover that non-monotonicity is surprisingly prevalent. In Chapter 4, we introduce the notion of an \u0027\u0027optimal branch-and-bound tree\u0022, that is, the smallest branch-and-bound tree that solves a given instance. We present a dynamic programming algorithm for generating the optimal trees and use it to evaluate the efficiency of strong-branching on (small) instances from a range of classical problems. In Chapter 5,\u0026nbsp; attempted to better understand the properties and limitations of FSB. We have identified two key factors that significantly impact tree sizes and leveraged them to design new FSB scores.\u003C\/p\u003E","summary":"","format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EClosing the Gap: A Theoretical and Practical Exploration of Branch-and-Bound for MIPs\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"Closing the Gap: A Theoretical and Practical Exploration of Branch-and-Bound for MIPs"}],"uid":"27707","created_gmt":"2025-04-03 18:00:00","changed_gmt":"2025-04-03 18:00:28","author":"Tatianna Richardson","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2025-04-09T12:00:00-04:00","event_time_end":"2025-04-09T14:00:00-04:00","event_time_end_last":"2025-04-09T14:00:00-04:00","gmt_time_start":"2025-04-09 16:00:00","gmt_time_end":"2025-04-09 18:00:00","gmt_time_end_last":"2025-04-09 18:00:00","rrule":null,"timezone":"America\/New_York"},"location":"Groseclose 303","extras":[],"groups":[{"id":"221981","name":"Graduate Studies"}],"categories":[],"keywords":[{"id":"100811","name":"Phd Defense"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1788","name":"Other\/Miscellaneous"}],"invited_audience":[{"id":"78771","name":"Public"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}