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

Due to the mathematical complexity of solving hard MIPs (mixed integer programming problems), many practical problems the industry faces are routinely left unsolved or solved sub-optimally, resulting in lost profits and productivity. This project aims to develop a product to solve MIPs rapidly, which is crucial for millions of mission-critical applications, especially in airlines, large networks, and supply chains. Our approach accomplishes this by efficiently managing the Branch and Bound (B&B) tree, a critical factor in accelerating MIP solutions essential to fields like biology, transportation, power plants, and electrical grids, aligning with DOE’s interests. Our product relies on two key innovations: scalable data storage and manipulation customized for solving MIPs and Machine learning (ML)-powered branching variable selection (BVS). Inspired by large parallel applications like Facebook and Apple Notes, our approach simplifies distributed data management and enhances B&B tree handling across a network of computers. It tackles MIP complexity through parallelization and benefits from data collected during B&B processing. Our goal is to introduce a next-gen mixed integer programming solver, leveraging parallel computing for rapid solving. Phase I R&D demonstrated the feasibility of our novel MIP solver, which integrates advanced parallel computing and ML-BVS. Our ML-BVS algorithm delivered efficiency improvements of 2X to 16X on 70% of the tested problems, while the parallel computing approach showed strong, linear, and super-linear scaling on MIPLIB2017 benchmarks. Solve times were drastically reduced: an airline crew scheduling problem dropped from 60 minutes to 3.5 seconds, a facility location problem from 5 minutes to 6 seconds, and a traffic signaling problem from 50 seconds to 1 second. Prospective customers and peers have reviewed our results and endorsed our approach (results presented at the ISMP-2024 conference). Our Phase II efforts include optimizing our code for high-performance computing (HPC) environments, ensuring it runs smoothly on industry-grade, commercially accessible HPC hardware. We will also improve our parallel MIP solver’s performance by 1) enhancing communication and collaboration between workers/cores, 2) upgrading our MIP solver, 3) enhancing our ML-BVS algorithms, and 4) adopting an enterprise-strength application architecture. We will expand our testing to include a broader range of benchmark problems and large-scale industrial applications provided by our partners. By the end of Phase II, we aim to deliver a fully operational prototype of the solver hosted on HPC infrastructure. Our product will enable faster airline operations, better supply chain decisions, enhance service quality and product safety, and potentially save companies millions annually through improved customer service, lower costs, and reduced environmental impact.