  Modern mixed-integer programming solvers use the branch-and-cut framework,
where cutting planes are added to improve the tightness of the linear
programming (LP) relaxation, with the expectation that the tighter formulation
would produce smaller branch-and-bound trees. In this work, we consider the
question of whether adding cuts will always lead to smaller trees for a given
fixed branching rule. We formally call such a property of a branching rule
monotonicity. We prove that any branching rule which exclusively branches on
fractional variables in the LP solution is non-monotonic. Moreover, we present
a family of instances where adding a single cut leads to an exponential
increase in the size of full strong branching trees, despite improving the LP
bound. Finally, we empirically attempt to estimate the prevalence of
non-monotonicity in practice while using full strong branching. We consider
randomly generated multi-dimensional knapsacks tightened by cover cuts as well
as instances from the MIPLIB 2017 benchmark set for the computational
experiments. Our main insight from these experiments is that if the gap closed
by cuts is small, change in tree size is difficult to predict, and often
increases, possibly due to inherent non-monotonicity. However, when a
sufficiently large gap is closed, a significant decrease in tree size may be
expected.
