Novel Branch & Bound Tree Management for Fast Convergence of MIPs on Parallel Computers

The need for solving mixed integer programming problems (MIPs) is at the core of millions of decision- support systems running mission-critical applications - especially in large networks and supply chains. Due to the mathematical complexity of solving hard MIPs, many practical problems faced by the industry are routinely left unsolved or solved sub-optimally, resulting in millions of dollars of lost profits and productivity. Managing the ôBranch and Boundö tree and ôbranching variable selectionö is crucial to solving hard MIPs rapidly. This project strives to develop a product to rapidly provide optimal solutions to MIPs that are crucial in areas like biology, transportation, electric grids, and facility infrastructure, which are of interest to DOE. Moreover, we aim to utilize DOEĺs investments in high- performance computing systems, which aligns with the DOE's goals. Our product relies on two key innovations: scalable data storage and manipulation customized for solving MIPs and Machine learning-powered branching variable selection. Inspired by large parallel applications like Facebook and Apple Notes, our approach simplifies distributed data management and enhances branch and bound tree handling across a network of computers. It tackles MIP complexity through parallelization and benefits from data collected during branch and bound processing. Our goal in Phases I and II is to introduce a next-gen mixed integer programming solver, leveraging parallel computing for rapid solving. We will demonstrate feasibility by creating an innovative branch and bound tree management and machine learning-based branching variable selection algorithms and evaluating them on MIPLIB 2017 problem instances. We will use suitable data structures to represent the branch and bound tree, develop code for parallel processing on a distributed computing cluster, and optimize branching variable selection strategies. Our academic and industrial partnerships will be valuable in this effort. The planned commercial application will aid quick decision-making in supply chains, leading to improved service quality and safer products. Companies are expected to save millions of dollars annually through enhanced customer service, reduced supply chain costs, and a smaller environmental footprint.