Exact Complexity Certification of Start Heuristics in Branch-and-Bound Methods for Mixed-Integer Linear Programming

Model predictive control (MPC) with linear performance measure for hybrid systems requires the solution of a mixed-integer linear program (MILP) at each time instance. A well-known method to solve MILP problems is branch-and-bound (B&B). To enhance the performance of B&B, start heuristic methods are often used, where they have shown to be useful supplementary tools to find good feasible solutions early in the B&B search tree, hence, reducing the overall effort in B&B to find optimal solutions. In this work, we extend the recently-presented complexity certification framework for B&B-based MILP solvers to also certify computational complexity of the start heuristics that are integrated into B&B. Therefore, the exact worst-case computational complexity of the three considered start heuristics and, consequently, the B&B method when applying each one can be determined offline, which is of significant importance for real-time applications of hybrid MPC. The proposed algorithms are validated by comparing against the corresponding online heuristic-based MILP solvers in numerical experiments.