A GPU-Aware Batched Branch and Bound Method for Solving Mixed-Binary MPC Problems

Model Predictive Control is a powerful technique for dynamic optimization in various industrial applications. In many such control applications, some variables are binary in nature, i.e., either on or off. Integrating binary variables into the MPC problem, forming a mixed-binary integer MPC problem, significantly increases the complexity of the problem. A way to handle such problem complexity, the classical mixed integer branch and bound solver algorithm breaks the problem into sub-problems (nodes), forming computational branches to reach a candidate solution, and eliminating all branches that cannot obtain an optimal solution. This approach enables massive parallel processing since the nodes can be computed independently, and the GPU-enabled computing paradigm is thus a natural target. The number of nodes belonging to a specific branch grows exponentially with the number of binary variables. Since a given GPU architecture may tackle a finite number of parallel branches, the node selection procedure is crucial for the actual deployment of such methods. In our proposed method, we exploit the GPU parallelism in two ways to achieve this while explicitly taking into account the maximum feasible parallel branches for a given memory architecture. First, we explore a batch of branches in parallel to identify the branch that results in a good candidate solution. Secondly, at the same time, for a given branch, we traverse over it efficiently by skipping intermediate nodes to reach a candidate solution. Initial comparison of our proposed method with Gurobi in controlling a four-tank system shows promising results.