# How to use tight upper and lower bounds to get to the optimal value via branch and bound?

I have algorithms that get me a tight upper (UB) and lower (LB) bound to a maximization binary integer program (a routing problem). My formulation is non-compact and requires the addition of sub-tour elimination constraints (SEC) dynamically. I am using CPLEX branch-and-bound and add these constraints via the callback mechanism. The LB solution is provided as incumbent (warm start) and that works fine but as soon as I add the constraint: objective function value <= UB, the CPLEX branch-and-bound seems to add a huge number of SECs and takes much longer time to improve the given UB further and finally to converge.

I thought with a tight UB and LB, the optimal solution could be found faster than usual but it is behaving the other way round. I have no idea what actually is going on. How can I effectively use the bound information to get to the optimal solution using CPLEX branch-and-bound/branch-and-cut?

To add to the linked answers: if the upper bound is obtained by taking a convex relaxation (e.g. a semidefinite relaxation), you could strengthen the formulation by running a cutting-plane method to solve the continuous relaxation and applying the cuts generated from the relaxation before branching. If you do this your initial upper bound should match the relaxation's bound, and the bound will be informative (while applying $$\theta \leq UB$$ wouldn't help the solver decide how to branch). That said, solving the relaxation via a cutting-plane method might be time consuming, especially if there isn't a "nice" way of cheaply generating a cut from the relaxation, so this might do more harm than good (it depends on the problem).
• How problematic may depend on the presolver. If the presolver eliminates the extra variable and you're back to $f(x) \le UB$ then it's definitely problematic. I did a little experimenting a while back, and I believe that I found less dual degeneracy when the variable bound method was used in my test example (although IIRC no bound was still fastest).