Using Parallel Branch-and-Bound Method to Accelerate Solving Mixed Integer Linear Programming

The Branch-and-Bound(B&B) algorithm is an effective method for solving the Mixed Integer Linear Programming (MILP) problem. Its performance significantly impacts the overall performance of the MILP solver Additionally, parallelizing the B&B algorithm can further speed up solver efficiency. In this paper, a novel B&B parallel algorithm is proposed to accelerate the solution process of MILP problems. A Master-Worker parallel structure is employed in this algorithm, fully leverages the serial performance of the solver. To minimize overhead, only necessary information is shared between the Master and Worker to utilizing shared memory communication. During the search of the B&B tree, the Master distributes problem nodes to Workers. Workers calculate problem nodes to update the information and subsequently return a sequence of new sub-problem nodes to the Master. Once optimality is achieved or the Master has no more problem nodes, the solution process is concluded. This research demonstrates that the proposed B&B parallel algorithm exhibits excellent acceleration performance. Research indicate that the B&B parallel algorithm presented in this study exhibits a substantial speedup factor of 1.53 for instances with over 10,000 nodes within the MIPLIB2017 benchmark. Furthermore, it demonstrates an even more impressive speedup factor of up to 2.53 for instances with more than 60,000 nodes, thereby underscoring excellent performance. It is noteworthy that the relationship between the speedup factor and the number of threads is predominantly linear.