Predicting the Solution Time of Branch‐and‐Bound Algorithms for Mixed‐Integer Programs

The most widely used progress measure for branch‐and‐bound (B&B) algorithms when solving mixed‐integer programs (MIPs) is the MIP gap. We introduce a new progress measure that is often much smoother than the MIP gap. We propose a double exponential smoothing technique to predict the solution time of B&B algorithms and evaluate the prediction method using three MIP solvers. Our computational experiments show that accurate predictions of the solution time are possible, even in the early stages of B&B algorithms.