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

Question

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?

Answer 1

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).

This idea has been explored by Fischetti et. al. (see section 4.2 of https://pubsonline.informs.org/doi/10.1287/mnsc.2016.2461), who showed that it works really well for facility location problems.

Answer 2

In addition to the issues it creates (covered by the link @RobPratt provided), it's worth nothing that the upper bound probably contributes nothing to the solver's performance. It will possibly give you a more realistic gap measure (if the solver uses it), but I don't see it guiding the solver's behavior in a useful way.

If you want to test this, introduce a variable z to represent your objective function, maximize z, add a constraint z = original objective function, and use the a priori upper bound as an upper bound on the z variable. I think this will cause fewer problems than the constraint <= UB would cause.