2
$\begingroup$

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? Please help!

$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This was also suggested in the link i provided, but there it is discussed that this is still problematic. $\endgroup$ – user3680510 May 26 at 19:38
  • $\begingroup$ 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). $\endgroup$ – prubin May 27 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.