Relationship between number of explored nodes and solution space for a MILP problem

Question

I'm using CPLEX through AMPL to solve a problem using two equivalent formulations. The problem is being solved to global optimality. However, one of the formulations is faster than the other. I have checked CPLEX's stats and I have found that the faster formulation has managed to reduce the number of explored branch-and bound nodes by 50%. My question is, what does such reduction in the number of the explored nodes indicate? Does it indicate a smaller search space for example? I would appreciate your feedback.

Answer 1

I won't address the question of "smaller search space" because I'm not sure the phrase "search space" is well defined. What I will say is that multiple factors go into the number of nodes explored. One is the "tightness" of the model, referring to both the difference between the optimal objective value and the objective value of the LP relaxation and the difference in volume of the LP hull and the integer hull (less being better). Another factor is how quickly the solver finds good solutions (and eventually an optimal solution). A tighter model makes it easier to prune nodes based on objective value ... if you can find good incumbent solutions. Early identification of good incumbents allows you to prune nodes on bound sooner ... provided the model is adequately tight. So those two things interact. Find good solutions early may be attributable to a model characteristic (the most obvious case being a model with the "integrality property", where the LP hull is the integer hull), but it also may be due to luck.

Before concluding that one formulation is faster to solve than the other, you should test it on multiple problem instances, and see if it is consistently faster.