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

Osman Y. Özaltın, Brady Hunsaker, Andrew J. Schaefer

INFORMS Journal on Computing · 2011 · Volume 23 · Issue 3

Abstract

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.

Keywords

solution time prediction, mixed-integer programming, branch-and-bound algorithm

Enable JavaScript for citation tools and additional paper interactions.